※此筆記可能會有一些錯誤, 歡迎大家指正:)※
今天晚上突然被一個同學用MSN問了有關CRC的問題, 一時之間還想不太起來CRC在幹嘛, 只記得之前Aizu修課時有講到(感謝筑波大學的木村老師, 雖然你上課上超快的…<( _ _ )>), 所以就把上課的投影片翻出來看.
I. Introduction
CRC的全名是Cyclic Redundancy Check, 中文翻譯成"循環冗餘核對碼"(這不是我翻的吶, 而Google翻譯的結果也和這個一樣:s).
首先, 先從一個簡單的概念說起,
"除法"
在除法的整除式子中,
其中,
是商數,
是除數,c 是被除數.
如果是另一個有餘數d且相等的式子就變成,
將其調整一下位置,
整合兩個式子為,
那麼…, 究~竟~~CRC跟除法有什麼關係呢?!
(小羊眉頭一皺發現內情並不單純…)
在CRC碼中主要分成兩個部份,
1. data
2. check bits
例如:
一個CRC碼總共有n個bits, 其中data的長度為n-k個bits及check bits的長度為k個bits. 如下所示,
當我們要把CRC碼傳送出去的時候, 就會把data後面加上check bits就變成,
11101100100010110.
II. Cyclic Redundancy Check
從另一方面的除法來想, 假設CRC碼是一個多項式
, 把除上一個為除數的多項式
(假設是給定的, 此時就變成了被除數的多項式), 則會得到一個為商數的多項式
. 如下所示,
將其調整一下位置,
當我們手中有一個data的多項式
並且將其提高k次方, 再加上一個餘數的多項式
之後, 會和CRC 碼的多項式相等. 如下所示,
整合兩個式子為,
(似乎好像有點眉目了! :o)
接下來有一個問題是, 要怎麼在data後面加上check bits?! 而且data又是個多項式(或2進位的編碼)!! 如果我們把data往左移(即提高k 次方)是不是就空出位置, 然後可以把check bits加上去了?!
例如:data往左移4個位置
1110110010001 -> 1110110010001****
如果把星號換成0(即補0),
1110110010001 -> 11101100100010000
再加上check bits,
哦哦~~!!(好像有點像樣了) 那check bits又是怎麼來的?!(7-11有在賣嗎?!) 在前面有提到給定的除數的多項式
, 我們可以利用來找出餘數例如: 假設
, 將其編碼為11001(其中2次方及1次方的係數為0), 接下來求餘數的過程如下所示,
在求餘數的過程中所利用的操作方式為XOR, 最後就可以得到check bits了(也就是餘數
). 需要注意的是在中的最高次為4 次方, 所以我們要在check bits前面補一個0就變成0110. 還有商數其實就是101110100010.III. Summary
在第II 章所描述的程過其實把除法和CRC做個比較, 用以大致上了解整個CRC碼產生過程. 最後我們再將其過程整理一下,
如果把CRC碼中的data和check bits用多項式來表示的話就變成,
將每一項的係數拿來作編碼的使用時CRC碼可以表示成,
接下來我們把所有已知的多項式整理一下,
CRC碼(或被除數):
data:
check bits(或餘數):
除數:
商數:
將
及其套入除法的整除式子中,把位置調整一下,
再將
提高k次方及套入有餘數的除法式子中,其中
表示data要補k個0(即多項式中的每一項之次方都提高了k次方, 例如:
; 同時也表示餘數的長度為k=4 bits, 所以要將的長度補齊為4 bits).最終CRC碼的式子就變成,
(怎麼好像變的很複雜的樣子… -0-")
最後, 當我們收到一個CRC碼
要怎麼確認它在傳送的過程中有沒有發生錯誤呢?! 其實只要做一個動作就可以了,
只要對
做mod的結果為0就表示所收到的CRC碼沒有錯誤, 反之則有錯誤!!:)
--
參考資料:
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
