常見CRC檢查碼 Common CRC codes
最常見的CRC檢查碼位元數目有8、16、32,一般表示都是CRC-8、CRC-16、CRC-32,CRC編碼越長偵測能力越強大,然而得更多時間傳送更長CRC檢查碼,CRC-16能偵測一個區塊內一或兩個位元錯誤,或是奇數個位元錯誤,當資料位元長度超過17個時,偵錯率可高達99.9969%,而網路七層OSI模型第二層傳送的訊框(Frame)採用則是更高檢查碼位元CRC-32。
----------------------------------------------------------------------------------------------
題目:
假設資料位元為10101010,生成多項式為x4+x2+x1+1 (10111)
問CRC碼以及加上CRC碼後的完整訊息為何?
問CRC碼以及加上CRC碼後的完整訊息為何?
解法:(使用長除法解題)
步驟 1.
由於生成多項式x4+x2+x1+1 (10111) 的羃次為4 (因為最高 x4)
,故先在資料位元10101010的後面加上四個0 (0000) (若生成多項式是x3則補3個0的意思,此處是4,所以補4個0)
,故先在資料位元10101010的後面加上四個0 (0000) (若生成多項式是x3則補3個0的意思,此處是4,所以補4個0)
,得到被除數為101010100000。
步驟 2.
以長除法求取101010100000除以生成多項式x4+x2+x1+1 (10111) 的餘數
CRC用的是二進位除法,不能化為十進位做減法運算,相減時
1-1=0,0-0=0,1-0=1,0-1=1(不要借位)
等同XOR運算 數字相同=0 相異=1(重要)
XOR
|
結果
| |
0
|
0
|
0
|
0
|
1
|
1
|
1
|
0
|
1
|
1
|
1
|
0
|
開始計算
使用長除法取101010100000除以生成多項式10111的餘數
注意:第一個10101 不夠10111 減 還是可以做下來,因為他是等同於XOR
CRC碼為上述所求出的餘數1100,而完整訊息則是在原始的資料位元後面加上CRC碼,得到101010101100 ,只要收訊端有正確的接收到訊息,該訊息將能被生成多項式整除。
ANS: 10101010 1100
驗算:101010101100再做一次長除法確實被10111整除 證明你剛剛算的沒有錯誤!