循環冗餘檢查CRC(Cyclic Redundancy Check)是網路通訊中一種常見的傳輸錯誤檢查技術。 CRC的計算方式是將待傳輸的資料區塊視為一堆連續位元所構成的一整個數值，並將此數值除以一特定的除數，兩數相除後得到的餘數即為循環冗餘檢查碼(CRC code)，除數值的位元數目視欲得到的循環冗餘檢查碼的位元長度而定，目前較常使用的CRC code位元長度有 8、16及32。傳送方會將計算所得的循環冗餘檢查碼附在待傳資料之後一併送出，當接收方收到資料後以相同方式計算CRC code，比較收到的循環冗餘檢查碼與自己計算的循環冗餘檢查碼是否相同，便可以判斷出資料在傳輸過程中是否遭到干擾而產生錯誤。
在CRC運算中我們稱除數(或Divisor)為poly，而寬度W就是poly最高位的位置。例如poly 1001的W是3，而不是4，請注意poly最高位總是1。假如我們想計算一個資料區塊的CRC code，並要保證每一位元都要被處理，因此我們需要在資料區塊後面加上W個0。CRC計算與普通的除法計算有所不同。普通的除法計算是借位相減的，而CRC計算則是互斥或(XOR)運算。以下面例子展示CRC算法的過程，請注意每個除法步驟的細節，此例中待傳輸資料為11110後面補上W(=3)個0，而poly(或除數)為1011，計算得到的餘數(Remainder)則做為待傳輸資料的CRC code，此例為101。
Input：
接下來有N組資料，每一組資料內容如下：
第一列有一個二元字串代表待傳資料(被除數)
第二列有一個二元字串代表poly(除數)
Output：
Sample Input：
2 10111 1011 11110 1011
Sample Output ：
CRC code:011 CRC code:101
Hint ：
Author ：
[教學] CRC(循環冗餘碼)長除法 教你如何算CRC長除法(附題目跟解法)
題目：
假設資料位元為10101010，生成多項式為x4+x2+x1+1 (10111)
問CRC碼以及加上CRC碼後的完整訊息為何？
解法：（使用長除法解題）
步驟 1.
由於生成多項式x4+x2+x1+1 (10111) 的羃次為4 (因為最高 x4)
，故先在資料位元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整除 證明你剛剛算的沒有錯誤!
留言列表
