循環冗餘校驗碼

循環冗餘校驗碼(cyclic redundancy check)簡稱CRC（循環碼），是一種能力相當強的檢錯、糾錯碼，並且實現編碼和檢碼的電路比較簡單，常用於串行傳送（二進制位串沿一條信號線逐位傳送）的輔助存儲器與主機的數據通信和計算機網絡中。 ^[3] 

循環碼是指通過某種數學運算實現有效信息與校驗位之間的循環校驗（而海明碼是一種多重校驗）。 ^[3] 

這種編碼基本思想是將要傳送的信息M(X)表示為一個多項式L，用L除以一個預先確定的多項式G(X)，得到的餘式就是所需的循環冗餘校驗碼。 ^[3] 

這種校驗又稱多項式校驗。 ^[3] 

理論上可以證明循環冗餘校驗碼的檢錯能力有以下特點：①可檢測出所有奇數位錯；②可檢測出所有雙比特的錯；③可檢測出所有小於、等於校驗位長度的突發錯。 ^[3] 

循環冗餘校驗碼由信息碼n位和校驗碼k位構成。k位校驗位拼接在n位數據位後面，n+k為循環冗餘校驗碼的字長，又稱這個校驗碼（n+k,n）碼。 ^[4] 

n位信息位可以表示成為一個報文多項式M(x)，最高冪次是x^n-1。約定的生成多項式G(x)是一個k+1位的二進制數，最高冪次是x^k。將M(x)乘以x^k，即左移k位後，除以G(x)，得到的k位餘數就是校驗位。這裏的除法運算是模2除法，即當部分餘數首位是1時商取1，反之商取0。然後每一位的減法運算是按位減，不產生借位。 ^[4] 

CRC碼存儲或傳送後，在接收方進行校驗過程，以判斷數據是否有錯，若有錯則進行糾錯。一個CRC碼一定能被生成多項式整除，所以在接收方對碼字用同樣的生成多項式相除，如果餘數為0，則碼字沒有錯誤；若餘數不為0，則説明某位出錯，不同的出錯位置餘數不同。對（n，k）碼制，在生成多項式確定時，出錯位置和餘數的對應關係是確定的。 ^[4] 

實際的CRC校驗碼生成是採用二進制的模2算法（即減法不借位、加法不進位）計算出來的，這是一種異或操作。下面通過一些例子來進一步解釋CRC的基本工作原理。假設： ^[5] 

(1)設約定的生成多項式為G(x)=x⁴+x+1，其二進制表示為10011，共5位，其中k=4。 ^[5] 

(2)假設要發送數據序列的二進制為101011(即f(x))，共6位。 ^[5] 

(3)在要發送的數據後面加4個0(生成f(x)*x^k)，二進制表示為1010110000，共10位。 ^[5] 

(4)用生成多項式的二進制表示10011去除乘積1010110000，按模2算法求得餘數比特序列為0100（注意餘數一定是k位的）。 ^[5] 

(5)將餘數添加到要發送的數據後面，得到真正要發送的數據的比特流：1010110100，其中前6位為原始數據，後4位為CRC校驗碼。 ^[5] 

(6)接收端在接收到帶CRC校驗碼的數據後，如果數據在傳輸過程中沒有出錯，將一定能夠被相同的生成多項式G(x)除盡，如果數據在傳輸中出現錯誤，生成多項式G(x)去除後得到的結果肯定不為0。 ^[5]