CRC

循環冗餘檢查 Cyclic Redundancy Check

CRC運算中我們稱除數(或Divisor)為poly。

寬度W就是poly最高位的位置。

CRC計算採互斥或(XOR)運算。{ XOR運算數字相同=0 相異=1(重要) }

Input：

第一列有一正整數N表示測試資料組數

接下來有N組資料，每一組資料內容如下：

第一列有一個二元字串代表待傳資料(被除數)

第二列有一個二元字串代表poly(除數)

Output：

依資料組數分別輸出一個代表CRC code (餘數)的二元字串。

Sample Input：

2 10111 1011 11110 1011

Sample Output ：

CRC code:011 CRC code:101

參考文獻

題目：

假設資料位元為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(重要)※

開始計算

使用長除法取101010100000除以生成多項式10111的餘數

注意：第一個10101 不夠10111 減還是可以做下來,因為他是等同於XOR

CRC碼為上述所求出的餘數1100，而完整訊息則是在原始的資料位元後面加上CRC碼，得到101010101100 ，只要收訊端有正確的接收到訊息，該訊息將能被生成多項式整除。

ANS: 10101010 1100

驗算：101010101100再做一次長除法確實被10111整除證明你剛剛算的沒有錯誤!