※此筆記可能會有一些錯誤, 歡迎大家指正:)※
今天晚上突然被一個同學用MSN問了有關CRC的問題, 一時之間還想不太起來CRC在幹嘛, 只記得之前Aizu修課時有講到(感謝筑波大學的木村老師, 雖然你上課上超快的…<( _ _ )>), 所以就把上課的投影片翻出來看.
I. Introduction
CRC的全名是Cyclic Redundancy Check, 中文翻譯成"循環冗餘核對碼"(這不是我翻的吶, 而Google翻譯的結果也和這個一樣:s).
首先, 先從一個簡單的概念說起,
"除法"
在除法的整除式子中,
![](https://lh3.ggpht.com/_UYnTwy0IiJY/S2mEuFotz-I/AAAAAAAAFKI/UYslgMAJpSc/s800/eq1.png.jpg)
其中,
![](https://lh5.ggpht.com/_UYnTwy0IiJY/S2mEuVR-wOI/AAAAAAAAFKM/XMeqwdAQaZk/s800/eq_a0.png.jpg)
![](https://lh5.ggpht.com/_UYnTwy0IiJY/S2mEwNwnI2I/AAAAAAAAFKs/pPSgdGLEHCk/s800/eq_b0.png.jpg)
c 是被除數.
如果是另一個有餘數d且相等的式子就變成,
![](https://lh5.ggpht.com/_UYnTwy0IiJY/S2mEui1x9jI/AAAAAAAAFKQ/N_DiwCT8XWQ/s800/eq2.png.jpg)
將其調整一下位置,
![](https://lh6.ggpht.com/_UYnTwy0IiJY/S2mEuy-N-eI/AAAAAAAAFKU/Fw4oQ4oxDuU/s800/eq3.png.jpg)
整合兩個式子為,
![](https://lh6.ggpht.com/_UYnTwy0IiJY/S2mEvKEIF3I/AAAAAAAAFKY/q9qfm6Iv1SE/s800/eq4.png.jpg)
那麼…, 究~竟~~CRC跟除法有什麼關係呢?!
(小羊眉頭一皺發現內情並不單純…)
在CRC碼中主要分成兩個部份,
1. data
2. check bits
例如:
![](https://lh4.ggpht.com/_UYnTwy0IiJY/S2mEy29fWXI/AAAAAAAAFLk/3HhgovuYCjU/s800/crc1.png.jpg)
一個CRC碼總共有n個bits, 其中data的長度為n-k個bits及check bits的長度為k個bits. 如下所示,
![](https://lh6.ggpht.com/_UYnTwy0IiJY/S2mEywvhuZI/AAAAAAAAFLo/JPpAIA8Ev2c/s800/crc2.png.jpg)
當我們要把CRC碼傳送出去的時候, 就會把data後面加上check bits就變成,
11101100100010110.
II. Cyclic Redundancy Check
從另一方面的除法來想, 假設CRC碼是一個多項式
![](https://lh4.ggpht.com/_UYnTwy0IiJY/S2mEwIp2OVI/AAAAAAAAFKw/jWuxrwR0JDc/s800/eq_cx.png.jpg)
![](https://lh4.ggpht.com/_UYnTwy0IiJY/S2mEwIp2OVI/AAAAAAAAFKw/jWuxrwR0JDc/s800/eq_cx.png.jpg)
![](https://lh4.ggpht.com/_UYnTwy0IiJY/S2mEwZdtV0I/AAAAAAAAFK0/XJzkx0xFESQ/s800/eq_gx.png.jpg)
![](https://lh4.ggpht.com/_UYnTwy0IiJY/S2mEwZdtV0I/AAAAAAAAFK0/XJzkx0xFESQ/s800/eq_gx.png.jpg)
![](https://lh4.ggpht.com/_UYnTwy0IiJY/S2mEwIp2OVI/AAAAAAAAFKw/jWuxrwR0JDc/s800/eq_cx.png.jpg)
![](https://lh3.ggpht.com/_UYnTwy0IiJY/S2mEw2ESrTI/AAAAAAAAFK8/0DhPAWos31E/s800/eq_qx.png.jpg)
![](https://lh4.ggpht.com/_UYnTwy0IiJY/S2mEvGCyKYI/AAAAAAAAFKc/yCDTK7rMnYI/s800/eq5.png.jpg)
將其調整一下位置,
![](https://lh4.ggpht.com/_UYnTwy0IiJY/S2mEvU2lOQI/AAAAAAAAFKg/8-uDw55i7Mo/s800/eq6.png.jpg)
當我們手中有一個data的多項式
![](https://lh4.ggpht.com/_UYnTwy0IiJY/S2mEwp24FQI/AAAAAAAAFK4/DPBsUZ8WT9s/s800/eq_ix.png.jpg)
項式
![](https://lh4.ggpht.com/_UYnTwy0IiJY/S2mExO1qjkI/AAAAAAAAFLA/561sggcK-Lk/s800/eq_rx.png.jpg)
![](https://lh4.ggpht.com/_UYnTwy0IiJY/S2mEwIp2OVI/AAAAAAAAFKw/jWuxrwR0JDc/s800/eq_cx.png.jpg)
![](https://lh5.ggpht.com/_UYnTwy0IiJY/S2mEvwp8sBI/AAAAAAAAFKk/QDxesHSjlJo/s800/eq7.png.jpg)
整合兩個式子為,
![](https://lh6.ggpht.com/_UYnTwy0IiJY/S2mEv22NwTI/AAAAAAAAFKo/xUEc3iR71gU/s800/eq8.png.jpg)
(似乎好像有點眉目了! :o)
接下來有一個問題是, 要怎麼在data後面加上check bits?! 而且data又是個多項式(或2進位的編碼)!! 如果我們把data往左移(即提高k 次方)是不是就空出位置, 然後可以把check bits加上去了?!
例如:data往左移4個位置
1110110010001 -> 1110110010001****
如果把星號換成0(即補0),
1110110010001 -> 11101100100010000
再加上check bits,
![](https://lh3.ggpht.com/_UYnTwy0IiJY/S2mExc_IURI/AAAAAAAAFLE/gv6_vARw__w/s800/crc3.png.jpg)
哦哦~~!!(好像有點像樣了) 那check bits又是怎麼來的?!(7-11有在賣嗎?!) 在前面有提到給定的除數的多項式
![](https://lh4.ggpht.com/_UYnTwy0IiJY/S2mEwZdtV0I/AAAAAAAAFK0/XJzkx0xFESQ/s800/eq_gx.png.jpg)
![](https://lh4.ggpht.com/_UYnTwy0IiJY/S2mEwZdtV0I/AAAAAAAAFK0/XJzkx0xFESQ/s800/eq_gx.png.jpg)
例如: 假設
![](https://lh6.ggpht.com/_UYnTwy0IiJY/S2mEx4KxpvI/AAAAAAAAFLM/jEbcAn6P3ZU/s800/eq9.png.jpg)
在求餘數的過程中所利用的操作方式為XOR, 最後就可以得到check bits了(也就是餘數
![](https://lh4.ggpht.com/_UYnTwy0IiJY/S2mExO1qjkI/AAAAAAAAFLA/561sggcK-Lk/s800/eq_rx.png.jpg)
![](https://lh4.ggpht.com/_UYnTwy0IiJY/S2mEwZdtV0I/AAAAAAAAFK0/XJzkx0xFESQ/s800/eq_gx.png.jpg)
![](https://lh3.ggpht.com/_UYnTwy0IiJY/S2mEw2ESrTI/AAAAAAAAFK8/0DhPAWos31E/s800/eq_qx.png.jpg)
III. Summary
在第II 章所描述的程過其實把除法和CRC做個比較, 用以大致上了解整個CRC碼產生過程. 最後我們再將其過程整理一下,
如果把CRC碼中的data和check bits用多項式來表示的話就變成,
![](https://lh4.ggpht.com/_UYnTwy0IiJY/S2mEyLVKeOI/AAAAAAAAFLQ/IeI5Yd8FwgE/s800/eq10.png.jpg)
![](https://lh4.ggpht.com/_UYnTwy0IiJY/S2mEyHS6_tI/AAAAAAAAFLU/y-6CklLZUoo/s800/eq11.png.jpg)
將每一項的係數拿來作編碼的使用時CRC碼可以表示成,
![](https://lh5.ggpht.com/_UYnTwy0IiJY/S2mEzPJvkSI/AAAAAAAAFLs/dsxCKsgsNkA/s400/crc5.png.jpg)
接下來我們把所有已知的多項式整理一下,
CRC碼(或被除數):
![](https://lh4.ggpht.com/_UYnTwy0IiJY/S2mEwIp2OVI/AAAAAAAAFKw/jWuxrwR0JDc/s800/eq_cx.png.jpg)
data:
![](https://lh4.ggpht.com/_UYnTwy0IiJY/S2mEwp24FQI/AAAAAAAAFK4/DPBsUZ8WT9s/s800/eq_ix.png.jpg)
check bits(或餘數):
![](https://lh4.ggpht.com/_UYnTwy0IiJY/S2mExO1qjkI/AAAAAAAAFLA/561sggcK-Lk/s800/eq_rx.png.jpg)
除數:
![](https://lh4.ggpht.com/_UYnTwy0IiJY/S2mEwZdtV0I/AAAAAAAAFK0/XJzkx0xFESQ/s800/eq_gx.png.jpg)
商數:
![](https://lh3.ggpht.com/_UYnTwy0IiJY/S2mEw2ESrTI/AAAAAAAAFK8/0DhPAWos31E/s800/eq_qx.png.jpg)
將
![](https://lh4.ggpht.com/_UYnTwy0IiJY/S2mEwZdtV0I/AAAAAAAAFK0/XJzkx0xFESQ/s800/eq_gx.png.jpg)
![](https://lh3.ggpht.com/_UYnTwy0IiJY/S2mEw2ESrTI/AAAAAAAAFK8/0DhPAWos31E/s800/eq_qx.png.jpg)
![](https://lh4.ggpht.com/_UYnTwy0IiJY/S2mEvGCyKYI/AAAAAAAAFKc/yCDTK7rMnYI/s800/eq5.png.jpg)
把位置調整一下,
![](https://lh4.ggpht.com/_UYnTwy0IiJY/S2mEvU2lOQI/AAAAAAAAFKg/8-uDw55i7Mo/s800/eq6.png.jpg)
再將
![](https://lh4.ggpht.com/_UYnTwy0IiJY/S2mEwp24FQI/AAAAAAAAFK4/DPBsUZ8WT9s/s800/eq_ix.png.jpg)
![](https://lh4.ggpht.com/_UYnTwy0IiJY/S2mExO1qjkI/AAAAAAAAFLA/561sggcK-Lk/s800/eq_rx.png.jpg)
![](https://lh5.ggpht.com/_UYnTwy0IiJY/S2mEvwp8sBI/AAAAAAAAFKk/QDxesHSjlJo/s800/eq7.png.jpg)
其中
![](https://lh4.ggpht.com/_UYnTwy0IiJY/S2mEydKprRI/AAAAAAAAFLY/2bCw3SroDgw/s800/eq12.png.jpg)
![](https://lh3.ggpht.com/_UYnTwy0IiJY/S2mEyYi4dSI/AAAAAAAAFLc/VT7d4i6atYg/s800/eq13.png.jpg)
![](https://lh4.ggpht.com/_UYnTwy0IiJY/S2mExO1qjkI/AAAAAAAAFLA/561sggcK-Lk/s800/eq_rx.png.jpg)
![](https://lh4.ggpht.com/_UYnTwy0IiJY/S2mExO1qjkI/AAAAAAAAFLA/561sggcK-Lk/s800/eq_rx.png.jpg)
最終CRC碼的式子就變成,
![](https://lh6.ggpht.com/_UYnTwy0IiJY/S2mEv22NwTI/AAAAAAAAFKo/xUEc3iR71gU/s800/eq8.png.jpg)
(怎麼好像變的很複雜的樣子… -0-")
最後, 當我們收到一個CRC碼
![](https://lh4.ggpht.com/_UYnTwy0IiJY/S2mEwIp2OVI/AAAAAAAAFKw/jWuxrwR0JDc/s800/eq_cx.png.jpg)
![](https://lh3.ggpht.com/_UYnTwy0IiJY/S2mEyuIfk6I/AAAAAAAAFLg/jvgQYVFug3k/s800/eq14.png.jpg)
只要對
![](https://lh4.ggpht.com/_UYnTwy0IiJY/S2mEwIp2OVI/AAAAAAAAFKw/jWuxrwR0JDc/s800/eq_cx.png.jpg)
:)
--
參考資料:
Lecture - Personal Communication Systems and Mobile Networks, The University of Aizu.
Lecturer - Shigetomo Kimura, University of Tsukuba.
Wikipedia - 除法
Wikipedia – Exclusive OR
Wikipedia - Cyclic Redundancy Check
Example - 臺灣菸酒公司99年第2職業人員甄試試題第16題
20180212 updated
有感!
回覆刪除感謝
回覆刪除很詳細唷
很詳細的解說~謝謝你
回覆刪除好文章 推
回覆刪除感謝您的解說!!^^
回覆刪除很感謝大大您的教學
回覆刪除請問既然這麼符雜怎麼不用錯誤更正碼就好, 更簡單還可以容錯, 雖然看起來bit數變長? 謝謝
回覆刪除你好,CRC沒有包含錯誤更正的部份,如果有錯誤更正的需要,使用你所說的方法會更好! :)
刪除不對啊,11101100100010110不能被11001整除啊?然後我翻其他文章看長除那裡做的不是減法而是異或運算的樣子
回覆刪除感謝大大的提醒,內容有做些修正!:)
刪除