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

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

2 北京電子科技學(xué)院 北京 100070

3 北京中電華大電子設(shè)計(jì)有限責(zé)任公司 北京 100102

0 引言

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

1 CRC算法基本原理

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

設(shè)每個(gè)信號(hào)碼元的序列為m={mn-1mn-2…m1m0}用多項(xiàng)式表示為：

CRC編碼步驟可歸納如下：

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

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

編出的碼為：

可得輸出碼序列為：

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

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

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

2 CRC的INTI和XOROUT值

定義 1：函數(shù)CRC(INIT,m)表示以INIT為寄存器初始值，輸入數(shù)據(jù)為 m計(jì)算 CRC校驗(yàn)值，默認(rèn)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算法雖然選擇相同的生成多項(xiàng)式，但開(kāi)始時(shí)寄存器中設(shè)置的初始值不同得到的CRC結(jié)果也不同。初始值對(duì)CRC算法的結(jié)構(gòu)性能沒(méi)有任何影響，可以任意設(shè)置，通常為了使得傳輸數(shù)據(jù)最前面的 0能夠正確傳輸，會(huì)將 INIT設(shè)置為0xFFFF同時(shí)，出于相同的目的會(huì)在CRC計(jì)算完成后將寄存器中的結(jié)果異或上一個(gè)XOROUT=0x FFFF值，然后結(jié)果輸出，函數(shù)表示為：CRC(m)=CRC(INIT,m)⊕XOROUT 。

3 CRC的生成多項(xiàng)式

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

4 CRC可校驗(yàn)數(shù)據(jù)長(zhǎng)度和性能

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

4.1 縮短循環(huán)碼

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

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

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

4.2 擴(kuò)展縮短碼

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

5 CRC算法性能

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

(1) 能糾正1bit的隨機(jī)差錯(cuò)；

(2) 能100%檢測(cè)出奇數(shù)個(gè)差錯(cuò)；

(3) 能100%檢測(cè)出任意的2bit的隨機(jī)差錯(cuò)；

(4) 能 100%檢測(cè)出小于等于生成多項(xiàng)式碼重dmin-1的隨機(jī)差錯(cuò)；

(5) 能l00%檢測(cè)出長(zhǎng)度小于等于校驗(yàn)位長(zhǎng)r的單個(gè)突發(fā)差錯(cuò)；

(6) 能以1-2-(r+1)的概率檢出長(zhǎng)度為r+1的單個(gè)突發(fā)差錯(cuò)；

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

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

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

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

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

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

表1 CRC16-CCITT

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

Name：名稱(chēng)。

Alias：別名。

Width：校驗(yàn)位長(zhǎng)度，設(shè)為r。

Poly：生成多項(xiàng)式，以十六進(jìn)制表示，最高位省略。

Init：初始化值，以十六進(jìn)制表示。

Refin：設(shè)置為布爾值。

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

(2) True正常輸入。

Refout：設(shè)置為布爾值。

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

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

Xorout：一個(gè)r比特長(zhǎng)的十六進(jìn)制值，在Refout步驟進(jìn)行后與寄存器中CRC值進(jìn)行異或操作。

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

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

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

7 結(jié)束語(yǔ)

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

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

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

[2] 楊杰,朱建鋒,安建平.無(wú)線傳輸中的循環(huán)冗余校驗(yàn)碼糾錯(cuò)應(yīng)用擴(kuò)展.北京理工大學(xué)學(xué)報(bào).2005.

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

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

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

[6] 朱榮華.一種 CRC并行計(jì)算原理及實(shí)現(xiàn)方法.電子學(xué)報(bào).1999.

[7] 蔣安平.循環(huán)冗余校驗(yàn)碼(CRC)的硬件并行實(shí)現(xiàn).微電子學(xué)與計(jì)算機(jī).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.