CRC算法的應用理論研究

歐海文 李起瑞, 胡曉波 趙靜

1 西安電子科技大學通信工程學院 陜西 710071

2 北京電子科技學院 北京 100070

3 北京中電華大電子設計有限責任公司 北京 100102

0 引言

在通信領域，由于數(shù)據(jù)在傳輸和存儲過程中受到各種干擾，使信號碼元發(fā)生變化，所以需要進行數(shù)據(jù)校驗以確保數(shù)據(jù)的完整性。循環(huán)冗余校驗CRC(Cyclic Redundancy Code)由于其具有檢錯效率高、原理簡單、易于實現(xiàn)的特點得到了廣泛的應用。

1 CRC算法基本原理

CRC校驗碼由分組線性碼的分支而來，其應用主要為二元碼組，由一個生成多項式(最高次冪為 r)產(chǎn)生，r次的生成多項式可產(chǎn)生r位的冗余碼，所有碼字的運算是封閉的。

設每個信號碼元的序列為m={mn-1mn-2…m1m0}用多項式表示為：

CRC編碼步驟可歸納如下：

設生成多項式g(x)的最高次冪為r，上式兩端乘以xr得：

用 g(x)模 2 除xrm(x)，得商Q(x)和余式r(x)：

編出的碼為：

可得輸出碼序列為：

接收方校驗數(shù)據(jù)有兩種方法：

(1) 對原始數(shù)據(jù)采用與發(fā)送方同樣的生成CRC校驗碼的方法生成r'(x)，然后與r(x)比較，相等則校驗通過，否則認為數(shù)據(jù)傳輸出現(xiàn)差錯。

(2) 對接收的數(shù)據(jù)計算m'(x)≡0modg(x)是否成立，成立則校驗通過，否則認為數(shù)據(jù)傳輸出現(xiàn)差錯。

2 CRC的INTI和XOROUT值

定義 1：函數(shù)CRC(INIT,m)表示以INIT為寄存器初始值，輸入數(shù)據(jù)為 m計算 CRC校驗值，默認CRC(m)=CRC(0,m)。

性質(zhì)1：?m∈{0,1}r,CRC(m,m)=0

性質(zhì)2：?mi∈{0,1}r,?ai∈{0,1}?

性質(zhì)3：?m，a∈{0,1}r,CRC(m,a)=CRC(a,m)

CRC算法雖然選擇相同的生成多項式，但開始時寄存器中設置的初始值不同得到的CRC結(jié)果也不同。初始值對CRC算法的結(jié)構(gòu)性能沒有任何影響，可以任意設置，通常為了使得傳輸數(shù)據(jù)最前面的 0能夠正確傳輸，會將 INIT設置為0xFFFF同時，出于相同的目的會在CRC計算完成后將寄存器中的結(jié)果異或上一個XOROUT=0x FFFF值，然后結(jié)果輸出，函數(shù)表示為：CRC(m)=CRC(INIT,m)⊕XOROUT 。

3 CRC的生成多項式

生成多項式在 CRC校驗中具有決定性的作用，應該指出并非任何一個多項式都可以作為生成多項式，文獻[1, 2, 3]等給出了選擇生成多項式的具體要求和準則。目前國際上已經(jīng)公布了幾種 CRC生成多項式的標準供我們使用，例如CRC-CCITT=x16+x12+x5+1，通常國際上用其反射多項式表示為0x8404，且已證明好的生成多項式的反射生成多項式也是好的生成多項式。

4 CRC可校驗數(shù)據(jù)長度和性能

CRC可校驗的數(shù)據(jù)位的長度是可變的，生成多項式g(x)或其某個因子為 t次本原多項式時，我們將數(shù)據(jù)位長度以2t-1為界分兩種情況討論。

4.1 縮短循環(huán)碼

CRC在本質(zhì)上是一種縮短循環(huán)碼，在(n-i,k-i)循環(huán)碼的2k個碼字中挑選出前i bit為0的碼字作為(n-i,k-i)縮短循環(huán)碼的碼字，它的碼集是(n, k)循環(huán)碼集的子集，所以它是一種系統(tǒng)循環(huán)碼，當數(shù)據(jù)位長 n小于 2t- 1時，除了不具有循環(huán)碼的循環(huán)性外具有循環(huán)碼的全部特性。

根據(jù)有限域相關(guān)知識，生成多項式g(x)或其某個因子為t次本原多項式時，這個本原多項式能夠整除的xn+1中，n的最小值是2t-1，它能產(chǎn)生的循環(huán)碼長就為 2t-1。

以 CRC16為例，它的生成多項式g(x)=x16+x12+x5+1=(x+1)(x15+x +1)其中(x15+x+1)是本原多項式，能夠整除的xn+1中，n的最小值是 215-1=32767，所以原始循環(huán)碼是(32767, 32751)循環(huán)碼。它保留了原始循環(huán)碼除循環(huán)性的特性，也決定了用 CRC16校驗時的最大信息長度平凡情況下不超過32751。

4.2 擴展縮短碼

在GF(2)上，生成多項式g(x)或其某個因子為t次本原多項式時，這個本原多項式能夠整除的xn+1中，n的最小值nmin=2t-1，當g(x)能整除xnmin+ 1時，g(x)定能整除xn+ 1，其中n=m?nmin，這樣由g(x)生成了一個碼長大于2t-1的(n,k, r)循環(huán)碼，然后從中挑選出前n-N位為全0的信息位得到(N, N-r, r)擴展縮短碼，其中(m-1)nmin?N≤n 。

5 CRC算法性能

CRC作為縮短循環(huán)碼時的性能研究已經(jīng)得到了較好的解決，CRC的檢錯性能由最小碼距和編碼本身的特性決定，以CRC-CCITT為例，由于其最小碼距為4，則：

(1) 能糾正1bit的隨機差錯；

(2) 能100%檢測出奇數(shù)個差錯；

(3) 能100%檢測出任意的2bit的隨機差錯；

(4) 能 100%檢測出小于等于生成多項式碼重dmin-1的隨機差錯；

(5) 能l00%檢測出長度小于等于校驗位長r的單個突發(fā)差錯；

(6) 能以1-2-(r+1)的概率檢出長度為r+1的單個突發(fā)差錯；

(7) 能以1-2-r概率檢出長度大于r+1的單個突發(fā)差錯；

擴展縮短碼和縮短循環(huán)碼一樣是線性分組碼，易知它們具有相同的平均不可檢錯誤概率，但二者的差錯檢測性能仍有稍微不同。

漢明碼校驗矩陣包含r重的所有碼，任何兩列是線性無關(guān)的，校驗矩陣的線性相關(guān)性決定了(n, k)線性碼分組碼的最小距離，漢明碼最小距離等于 3?？s短碼校驗多項式的列數(shù)小于漢明碼校驗多項式的列數(shù)，在此情況下縮短循環(huán)碼的最小距離不小于 3。擴展縮短碼校驗多項式的列數(shù)大于漢明碼校驗多項式的列數(shù)，其校驗矩陣至少有兩列是線性相關(guān)的，所以擴展縮短碼的最小距離一定等于2。

所以，CRC作為擴展循環(huán)碼時將不能100%檢測隨機2bit錯誤，同樣也不能糾正隨機1bit錯誤。

6 CRC的實現(xiàn)及應用規(guī)范

目前，CRC的計算方法主要有串行和并行兩種，實現(xiàn)方式也可分為軟件實現(xiàn)和硬件實現(xiàn)，大量的文獻對此進行了研究，但鮮有文獻介紹CRC的應用規(guī)范，這里以CRC-CCITT為例對各個參數(shù)進行說明(如表1)。

表1 CRC16-CCITT

其中各參數(shù)意義為：

Name：名稱。

Alias：別名。

Width：校驗位長度，設為r。

Poly：生成多項式，以十六進制表示，最高位省略。

Init：初始化值，以十六進制表示。

Refin：設置為布爾值。

(1) False取信息多項式的反射多項式，即將信息位反序輸入；

(2) True正常輸入。

Refout：設置為布爾值。

(1) False運算完畢后寄存器中的 CRC值直接進行Xorout步操作；

(2) True運算完畢后寄存器中的CRC值進行反序操作；

Xorout：一個r比特長的十六進制值，在Refout步驟進行后與寄存器中CRC值進行異或操作。

Check：ASCII字符串“123456789”即[31 32 33 34 35 36 37 38 39]的CRC校驗值，主要用于驗證以上參數(shù)設置的正確性。

Lcheck：ASCII字符串“123456789”后面附加上“9”的二進制形式即[31 32 33 34 35 36 37 38 39 09]的CRC校驗值。

Xcheck：ASCII字符串“123456789”的CRC輸出值，但高低位字節(jié)交換順序。

7 結(jié)束語

CRC作為一種在通信領域中廣泛應用的檢錯方案，之前被大量文獻進行了較好的研究，本文補充了現(xiàn)有文獻中的空白，解決了在實際應用中常碰到的如何設置寄存器的初始值及如何選取生成多項式的問題；同時，通過分析不同長度下算法性能差異提出了 CRC算法對校驗數(shù)據(jù)長度沒有限制的觀點，進一步指出 CRC作為擴展循環(huán)碼時平均漏檢概率上限值雖未改變，但由于最小碼間距改變成 2，因此將不能100%檢測隨機2bit錯誤，也不能糾正隨機1bit錯誤的觀點。

CRC曾被考慮作為一種Hash算法，但由于它具有一定的漏檢概率而未被采用。其實，CRC也存在著逆運算，即由校驗碼可以倒推出信息碼或信息碼的部分信息。對于CRC(INIT,m)=r，若INIT和r已知，顯然，當信息碼長度小于等于校驗碼長度時，二者成一一對應關(guān)系，此時可以通過查表法倒推出信息碼，否則不能惟一確定信息碼。因此，已知INIT和r求解m或已知r, m求解INIT是一個值得我們?nèi)パ芯康挠腥栴}。

[1] 馬吉明,魏艷.探究縮短循環(huán)碼性能與生成多項式的選取.通信技術(shù).2008.

[2] 楊杰,朱建鋒,安建平.無線傳輸中的循環(huán)冗余校驗碼糾錯應用擴展.北京理工大學學報.2005.

[3] 瞿中,袁威,徐問之.CRC算法在計算機網(wǎng)絡通信中的應用.微機發(fā)展.2002.

[4] 王新梅,肖國鎮(zhèn).糾錯碼－原理與方法[M].西安：西安電子科技大學出版社.2001.

[5] 周秦英,王新梅,葛暉.CRC在中擴展縮短碼的設計與性能分析.西北工業(yè)大學學報.2004.

[6] 朱榮華.一種 CRC并行計算原理及實現(xiàn)方法.電子學報.1999.

[7] 蔣安平.循環(huán)冗余校驗碼(CRC)的硬件并行實現(xiàn).微電子學與計算機.2007.

[8] Martin Stigge, Henryk Plotz, Wolf Muller. Reversing CRCTheory and Practice.HU Berlin Public Report.2006.

[9] Ross N. Williams. A painless guide to CRC error detection algorithms.www.cse.sc.edu/~jimdavis/Courses//crc-Ross.pdf.1993.