循環冗餘校驗碼（CRC），簡稱循環碼，是一種常用的、具有檢錯、糾錯能力的校驗碼，在早期的通信中運用廣泛。循環冗餘校驗碼常用於外存儲器和計算機同步通信的數據校驗。奇偶校驗碼和海明校驗碼都是採用奇偶檢測為手段檢錯和糾錯的，而循環冗餘校驗則是通過某種數學運算來建立數據位和校驗位的約定關係的。
基本介紹
校驗,編碼規則,套用,
校驗
對通信的可靠性檢查就需要‘校驗’，校驗是從數據本身進行檢查，它依靠某種數學上約定的形式進行檢查，校驗的結果是可靠或不可靠，如果可靠就對數據進行處理，如果不可靠，就丟棄重發或者進行修復。
（倒推法）：傳送方傳送的是T(x)，接收方接收到的是R(x)，若T(x)和R(X)相等，則傳輸的過程中沒有出現錯誤。如何判斷T(x)和R(X)是否相等？若R(X)能夠被g(x)整除，則接收方認為T(x)和R(X)相等，即傳輸的過程中沒有出現錯誤。傳送方要傳輸的信息info包含在T(x)里，info是T(x)的一部分，但不能說info就是T(x)。實際套用中，g(x)的取值是有限制的，它受限於以下國際標準：
CRC-CCITT=x^16+x^12+x^5+1
CRC-16=x^16+x^15+x^2+1
CRC-12=x^12+x^11+x^3+x^2+x+1
關於g(x)的國際標準還有一些，這裡不一一介紹。
人工計算循環冗餘校驗碼需要先弄清的知識：多項式除法、異或運算。
編碼規則
CRC碼是由兩部分組成，前部分是信息碼，就是需要校驗的信息，後部分是校驗碼，如果CRC碼共長n個bit，信息碼長k個bit，就稱為（n,k）碼。它的編碼規則是：
- 移位
將原信息碼（kbit）左移r位（k+r=n)
- 相除
運用一個生成多項式g(x)（也可看成二進制數）用模2除上面的式子，得到的餘數就是校驗碼。
非常簡單，要說明的：模2除就是在除的過程中用模2加，模2加實際上就是我們熟悉的異或運算，就是加法不考慮進位，公式是：
0+0=1+1=0,1+0=0+1=1
即‘異’則真，‘非異’則假。
由此得到定理：a+b+b=a 也就是‘模2減’和‘模2加’真值表完全相同。
有了加減法就可以用來定義模2除法，於是就可以用生成多項式g(x）生成CRC校驗碼。
- 生成多項式應滿足以下原則
a、生成多項式的最高位和最低位必須為1。
b、當被傳送信息（CRC碼）任何一位發生錯誤時，被生成多項式做模2除後應該使餘數不為0。
c、不同位發生錯誤時，應該使餘數不同。
d、對餘數繼續做模2除，應使餘數循環。
套用
- 舉例一
例如：g(x)=x^4+x^3+x^2+1，（7,3）碼，信息碼110產生的CRC碼就是：
對於g(x)=x^4+x^3+x^2+1的解釋：（都是從右往左數）x4就是第五位是1，因為沒有x1所以第2位就是0。
11101 | 110,0000（設a=11101 ，b=1100000）
用b除以a做模2運算得到餘數：1001
餘數是1001，所以CRC碼是1001，傳輸碼為：110,1001
- 舉例二
紅軍和藍軍通信聯合進攻山下的敵軍的例子
第一天紅軍發了條信息要藍軍第二天一起進攻，藍軍收到之後，發一條確認信息，但是藍軍擔心的是‘確認信息’如果也不可靠而沒有成功到達紅軍那裡，那自己不是很危險？於是紅軍再發一條‘對確認的確認信息’，但同樣的問題還是不能解決，紅軍仍然不敢貿然行動。
