艦船動力控制網(wǎng)絡(luò)CRC算法分析及程序?qū)崿F(xiàn)

張曉輝，熊 卿，丁 瑋

(武漢第二船舶設(shè)計研究所，湖北 武漢 430064)

1 概述

在艦船動力控制網(wǎng)絡(luò)中，底層設(shè)備采集信號，并把這些數(shù)據(jù)通過串口向上級設(shè)備傳送。由于通訊線路較長、電磁環(huán)境差，導致通訊過程中誤碼率較高。同時，隨著網(wǎng)絡(luò)節(jié)點及數(shù)據(jù)量的增多，通訊速率也逐步提高，導致數(shù)據(jù)受干擾的機率也在增加。由于這些數(shù)據(jù)是重復發(fā)送的，只要通訊網(wǎng)絡(luò)中的接受方能識別出數(shù)據(jù)有錯誤，丟棄錯誤數(shù)據(jù)即可，重新等待下次數(shù)據(jù)。本文詳細介紹了一種識別通訊數(shù)據(jù)錯誤的方法:循環(huán)冗余校驗(Cyclic Redundancy Check，CRC)及其算法實現(xiàn)。在實現(xiàn)的艦船動力控制網(wǎng)絡(luò)中使用效果良好，達到了預(yù)期目的。

在數(shù)字通信系統(tǒng)中可靠與快速往往是一對矛盾。若要求快速，則必然使得每個數(shù)據(jù)碼元所占的時間縮短、波形變窄、能量減少，從而在受到干擾后產(chǎn)生錯誤的可能性增加，傳送信息的可靠性下降。若要求可靠，則使得傳送消息的速率變慢。因此，如何合理地解決可靠性和速度這一對矛盾，是正確設(shè)計一個通信系統(tǒng)的關(guān)鍵問題之一。為保證傳輸過程的正確性，需要對通信過程進行差錯控制。差錯控制最常用的方法是檢錯重發(fā)方式(ARQ在接收端根據(jù)編碼規(guī)則進行檢查，如果發(fā)現(xiàn)規(guī)則被破壞，則通過反向信道要求發(fā)送端重新發(fā)送，直到接收端檢查無誤為止)、前向糾錯方式(FEC發(fā)送端發(fā)送能糾正錯誤的編碼，在接收端根據(jù)接收到的碼和編碼規(guī)則，能自動糾正傳輸中的錯誤)和混合糾錯(HEC結(jié)合前向糾錯和ARQ的系統(tǒng)，在糾錯能力范圍內(nèi)，自動糾正錯誤，超出糾錯范圍則要求發(fā)送端重新發(fā)送)。在傳輸過程誤碼率比較低時，用FEC方式比較理想。在傳輸過程誤碼率較高時，采用FEC容易出現(xiàn)“亂糾”現(xiàn)象。HEC方式則是ARQ和FEC的結(jié)合。在許多數(shù)字通信中，廣泛采用ARQ方式，此時的差錯控制只需要檢錯功能。實現(xiàn)檢錯功能的差錯控制方法很多，傳統(tǒng)的有:奇偶校驗、重復碼校驗、恒比碼校驗、行列冗余碼校驗等，這些方法都是增加數(shù)據(jù)的冗余量，將校驗碼和數(shù)據(jù)一起發(fā)送到接受端。接受端對接受到的數(shù)據(jù)進行相同校驗，再將得到的校驗碼和接受到的校驗碼比較，如果二者一致則認為傳輸正確。但這些方法都有各自的缺點，誤判的概率比較高。

循環(huán)冗余校驗是由分組線性碼的分支而來，其主要應(yīng)用是二元碼組。編碼簡單且誤判概率很低，在通信系統(tǒng)中得到了廣泛的應(yīng)用。下面重點介紹CRC校驗的原理及其算法實現(xiàn)。

2 循環(huán)冗余校驗碼(CRC)

CRC校驗采用多項式編碼方法。被處理的數(shù)據(jù)塊可以看作是1個n階的二進制多項式，由an－1xn－1+an－2xn－2+ … +a1x+a0。如1個8位二進制數(shù)10110101可表示為:1x7+0x6+1x5+1x4+0x3+1x2+0x+1。多項式乘除法運算過程與普通代數(shù)多項式的乘除法相同。多項式的加減法運算以2為模，加減時不進，錯位，和邏輯異或運算一致。

采用CRC校驗時，發(fā)送方和接收方用同1個生成多項式G(x)，并且G(x)的首位和最后1位的系數(shù)必須為1。CRC的處理方法是:發(fā)送方以G(x)去除t(x)，得到余數(shù)作為CRC校驗碼，并把該余數(shù)附加在t(x)后面構(gòu)成 t(x+2)。接收方校驗時，以g(x)/t(x+2)計算出的校正結(jié)果是否為0為依據(jù)，判斷數(shù)據(jù)幀是否出錯。

2.1 基本概念

2.1.1 多項式與二進制數(shù)碼

多項式和二進制數(shù)有直接對應(yīng)關(guān)系:x的最高冪次對應(yīng)二進制數(shù)的最高位，以下各位對應(yīng)多項式的各冪次，有此冪次項對應(yīng)1，無此冪次項對應(yīng)0?？梢钥闯?x的最高冪次為R，轉(zhuǎn)換成對應(yīng)的二進制數(shù)有R+1位。多項式包括生成多項式G(x)和信息多項式C(x)。如生成多項式為G(x)=X4+X3+X1+1，可轉(zhuǎn)換為二進制數(shù)碼11011。而發(fā)送信息位1011，可轉(zhuǎn)換為數(shù)據(jù)多項式C(x)=X3+X2+X+1。這里，X=2。

2.1.2 生成多項式

是接受方和發(fā)送方約定的1個多項式，也就是1個二進制數(shù)，在整個傳輸過程中，這個數(shù)始終保持不變。

在發(fā)送方，利用生成多項式對信息多項式做模2除運算生成校驗碼，而在接受方則利用生成多項式對收到的編碼多項式做模2除運算來檢測錯誤和確定其位置。

生成多項式應(yīng)滿足以下條件:

1)生成多項式的最高位和最低位必須為1。

2)當被傳送信息(信號多項式加上CRC碼)的任何1位發(fā)生錯誤時，被生成多項式做模2除后，余數(shù)不應(yīng)為0。

3)不同位發(fā)生錯誤時，余數(shù)應(yīng)不同。

4)對余數(shù)繼續(xù)做模2除，余數(shù)應(yīng)能循環(huán)。

常用的 CRC生成多項式有 CRC-4，CRC-12，CRC-16，CRC-CCITT，CRC-32 和 CRC-32c幾種，本文選取CRC-CCITT，其生成多項式0x11021，簡記式為0x1021。

2.1.3 模2除(按位除)

模2除法與算術(shù)除法類似，但每一位除(減)的結(jié)果不影響其他位，即不向上一位借位。所以實際上就是異或。然后再移位做下一位的模2減。步驟如下:

1)用除數(shù)對被除數(shù)最高幾位做模2減，沒有借位。

2)除數(shù)右移一位，若余數(shù)最高位為1，商為1，并對余數(shù)做模2減。若余數(shù)最高位為0，商為0，除數(shù)繼續(xù)右移一位。

3)一直做到余數(shù)的位數(shù)小于除數(shù)時，該余數(shù)就是最終余數(shù)。

2.1.4 CRC碼的生成步驟

1)將x的最高冪次為R的生成多項式G(x)轉(zhuǎn)換成對應(yīng)的R+1位二進制數(shù)。

2)將信息碼C(x)左移R位，相當于對應(yīng)的信息多項式C(x)*2R。

3)用生成多項式G(x)(二進制數(shù))對信息碼C(x)*2R做模2除，得到R位的余數(shù)Y(x)。

4)用余數(shù)替代信息碼左移R位后空出的位置，得到完整的CRC碼。

5)發(fā)送方發(fā)送的數(shù)據(jù)就是C(x)*2R+Y(x)。

2.1.5 CRC碼的校驗

接收方收到數(shù)據(jù)C(x)*2R+Y(x)后，用生成多項式G(x)作為除數(shù)去除C(x)*2R+Y(x)，得到的余數(shù)如果為0，表示通訊數(shù)據(jù)正確，否則表示數(shù)據(jù)在通訊過程中出錯了。

2.2 CRC的糾錯能力

一般情況下，r位生成多項式產(chǎn)生的CRC碼可檢測出所有的雙錯、奇數(shù)位錯和突發(fā)長度小于等于r的突發(fā)錯以及1－2－(r－1)的突發(fā)長度為r+1的突發(fā)錯和(1－2－r)的突發(fā)長度大于r+1的突發(fā)錯。例如，對上述r=16的情況，就能檢測出所有突發(fā)長度小于等于16的突發(fā)錯以及99.997%的突發(fā)長度為17的突發(fā)錯和99.998%的突發(fā)長度大于17的突發(fā)錯。所以CRC碼的檢錯能力還是很強的。這里，突發(fā)錯誤是指幾乎是連續(xù)發(fā)生的一串錯，突發(fā)長度就是指從出錯的第一位到出錯的最后一位的長度(但是，中間并不一定每一位都錯)。

3 CRC校驗碼的算法分析

從CRC的編碼規(guī)則可以看出，CRC編碼實際上是將代發(fā)送的m位二進制多項式C(x)轉(zhuǎn)換成了可以被G(x)除盡的m+r位二進制多項式C(x)*2R+Y(x)，所以解碼時可以用接受到的數(shù)據(jù)C(x)*2R+Y(x)去除G(x)，如果余數(shù)為0，則表示傳輸過程沒有錯誤;如果余數(shù)不為0，則在傳輸過程中肯定存在錯誤，并且，可以通過該不為0的余數(shù)來判斷究竟是哪一位出錯。許多CRC的硬件解碼電路就是按這種方式進行檢錯的。同時C(x)*2R+Y(x)可以看做是由C(x)和CRC校驗碼的組合，所以解碼時將接收到的二進制數(shù)據(jù)去掉尾部的r位數(shù)據(jù)，得到的就是原始數(shù)據(jù)。

為了更清楚地了解CRC校驗碼的編碼過程，下面用一個簡單的例子來說明。由于 CRC-32，CRC-16，CCITT和CRC-4的編碼過程基本一致，只有位數(shù)和生成多項式不一樣，為了敘述簡單，用1個CRC-4編碼的例子來說明CRC的編碼過程。

設(shè)待發(fā)送的數(shù)據(jù)t(x)為12位的二進制數(shù)據(jù)100100011100;CRC-4的生成多項式為g(x)=，階數(shù)r為4，即10011。首先在t(x)的末尾添加4個0構(gòu)成，數(shù)據(jù)塊就成了1001000111000000。然后用g(x)去除，不用管商是多少，只需要求得余數(shù)y(x)。表1為給出的除法過程。

表1 求余數(shù)過程Tab.1 Diagram of computing the remainder

從表1中可以看出，CRC編碼實際上是1個循環(huán)移位的模2運算。假設(shè)CRC-4有1個5 bits的寄存器，通過反復的移位和進行CRC的除法，那么最終該寄存器中的值去掉最高1位就是我們所要求的余數(shù)。所以可以將上述步驟用下面的算法描述:

算法Ⅰ

//reg是一個5 bits的寄存器

把reg中的值置0.

把原始的數(shù)據(jù)后添加r個0.

While(數(shù)據(jù)未處理完)

Begin

If(reg首位是1)

reg=reg XOR 0011.

把reg中的值左移1位，讀入1個新的數(shù)據(jù)并置于register的0 bit的位置。

End

reg的后4位就是我們所要求的余數(shù)。

這種算法簡單，容易實現(xiàn)，對任意長度生成多項式的G(x)都適用。在發(fā)送的數(shù)據(jù)不長的情況下可以使用。但是如果發(fā)送的數(shù)據(jù)塊很長的話，這種方法就不太適合了。它1次只能處理1位數(shù)據(jù)，效率太低。為了提高處理效率，可以1次處理4位，8位，16位，32位。由于處理器的結(jié)構(gòu)基本上都支持8位數(shù)據(jù)的處理，所以1次處理8位比較合適。

為了對優(yōu)化后的算法有一種直觀的了解，先將上面的算法換個角度理解一下。在上面例子中，可以將編碼過程看作如下過程:

由于最后只需要余數(shù)，所以我們只看后4位。構(gòu)造1個4位的寄存器reg，初值為0，數(shù)據(jù)依次移入reg 0(reg的0位)，同時reg 3的數(shù)據(jù)移出reg。由上面的算法可以知道，只有當移出的數(shù)據(jù)為1時，reg才和G(x)進行XOR運算;移出的數(shù)據(jù)為0時，reg不與G(x)進行XOR運算，其實相當于與0000進行XOR運算。就是說，reg和什么樣的數(shù)據(jù)進行XOR運算由移出的數(shù)據(jù)決定。由于只有1個bit，所以有21種選擇。上述算法可以描述如下，

算法Ⅱ

//reg是1個4 bits的寄存器

初始化 t［］={0000，0011}

把reg中的值置0.

在原始的數(shù)據(jù)后添加4個0.

While(數(shù)據(jù)未處理完)

Begin

把reg中的值左移1位，讀入1個新的數(shù)據(jù)并置于register的0 bit的位置。

reg=reg XOR t［移出的位］

End

上面算法是以bit為單位進行處理的，可以將上述算法擴展到8位，以 Byte為單位進行處理，即CRC-CCITT。構(gòu)造1個2個Byte的寄存器reg，初值為0x0000，數(shù)據(jù)依次移入reg 0(reg的0字節(jié)，以下類似)，同時reg 1的數(shù)據(jù)移出reg。用上面的算法類推可知，移出的數(shù)據(jù)字節(jié)決定reg和什么樣的數(shù)據(jù)進行XOR。由于有8個bit，所以有28種選擇。上述算法可以描述如下:

算法Ⅲ

//reg是1個2字節(jié)的寄存器

初始化CRC余式表t［］={…}//共有28=256項

把reg中的值置0.

在原始的數(shù)據(jù)后添加2個0字節(jié).

While(len——)

Begin

把reg中的值左移1個字節(jié)，讀入1個新的字節(jié)并置于reg的第0個byte的位置。

reg=reg XOR t［移出的字節(jié)］

End

這里，len是追加了2個0字節(jié)的數(shù)據(jù)的長度。這個算法很清晰，但經(jīng)過仔細分析，我們發(fā)現(xiàn)，算法Ⅲ為了處理數(shù)據(jù)項C(x)，首先要在其末尾追加2個字節(jié)的0。對發(fā)送方而言，C(x)本身就給CRC碼留有2個字節(jié)的空間，問題倒不大;可對接收方就很容易引起數(shù)組下標越界的問題。一個可替代的不用追加2個0字節(jié)的方法是，在算法Ⅲ中，不在C(x)后追加2個0字節(jié)，而是在循環(huán)語句后，再加上下面2行語句:

For(i=0;i＜2;i++)

Reg=(reg ＜＜8)^t［r ＞＞8］＆ 0xff］，

這樣的代碼就完善了。但還可作進一步的分析，找到1個既不用在數(shù)據(jù)末尾追加2字節(jié)的0，也不用在程序后面專門處理2個0字節(jié)的辦法。

請注意以下2個事實:

1)追加到數(shù)據(jù)末尾的2個0字節(jié)，也會像其他數(shù)據(jù)一樣，從寄存器reg的右端移入，但它們的值(0)對reg中的原值沒有影響，因為

①任何變量與0異或不改變原值。

②追加的2個0字節(jié)也不會從reg的左端移出，也就不會參加查表運算，不會對reg的值產(chǎn)生影響。

這樣，追加2個字節(jié)的0的惟一作用就是使移位運算多兩次循環(huán)，以便真正的數(shù)據(jù)能移出寄存器去參加查表運算。

2)如果寄存器reg的初始值是0，那么算法中的前面2次循環(huán)的惟一作用是把真正的數(shù)據(jù)從右移到寄存器的高位來。這是因為前16個控制位都是0，所以沒有什么值異或到reg中。

這就意味著，數(shù)據(jù)字節(jié)不必從寄存器的左端移到右再移出。相反，他們可直接與寄存器的高字節(jié)異或，其結(jié)果再作為索引去查表。下面舉例說明。首先根據(jù) CRC的定義求 0x22335A的 CRC碼，得到0x43DF。

圖1 根據(jù)定義求CRC碼Fig.1 CRC computation based on its definition

根據(jù)異或運算的屬性:(A xor B)xor C=A xor(B xor C)，這里，A是生成多項式，B是reg的高字節(jié)，C是新移入的字節(jié)。把上面的運算過程再細化一下，得到下面的改進算法。

算法Ⅳ:

把reg中的值置0.

While(len——)

Begin

reg中的值左移1個字節(jié)，

Reg左移出的字節(jié)與新讀入的1個字節(jié)XOR得到index，

reg=reg XOR t［index］

End

根據(jù)算法Ⅳ，重新分析0x22335A求CRC碼的過程，見圖2。

圖2 根據(jù)算法Ⅳ求CRC碼Fig.2 CRC computation based on algonithm IV

從圖1和圖2可以看出，算法Ⅲ和算法Ⅳ的結(jié)果是一樣的。

再來看看寄存器初始值的設(shè)置。大多數(shù)的CRC算法都把寄存器的初始值設(shè)為0。理論上(比如，不對欲處理的數(shù)據(jù)作任何假設(shè))，寄存器的初始值對CRC算法應(yīng)該沒有什么影響。事實上，如果數(shù)據(jù)序列有一長串前導0字節(jié)(這在實際通訊是可能發(fā)生的)，其CRC計算結(jié)果將是這些前導0好像不存在，也就是說計算出的CRC碼與前導0無關(guān)(見表2)。因此，聰明一點的做法是設(shè)置初始值為1個非0值，通常設(shè)為0xFFFF。注:括號中的數(shù)字表示數(shù)據(jù)序列的字節(jié)長度。

綜上所述，得到算法Ⅴ:把reg中的值置0xFFFF.

While(len——)

Begin

reg中的值左移1個字節(jié)，

Reg左移出的字節(jié)與新讀入的1個字節(jié)XOR得到index，

reg=reg XOR t［index］

End

return reg

這里，len是數(shù)據(jù)序列本身的長度。

表2 不同初始的計算結(jié)果Tab.2 CRC codes generated from different number sequences

4 CRC-CCITT的程序?qū)崿F(xiàn)

根據(jù)前面的分析并參照CRC_CCITT標準，給出如下條件:

1)算法名:CRC_CCITT;2)CRC寬度:16位;

3)生成多項式:0x1021;

4)檢查值:29B1(字符串“123456789”的 CRC碼，用于檢查算法是否正確)。

根據(jù)算法Ⅴ和上面的條件，下面給出了求CRCCCITT校驗碼的程序片段。

4.1 C語言

4.2 8051匯編語言

4.3 發(fā)送和接收的處理方法

發(fā)送和接收都使用同一個程序，只是其入口參數(shù)稍有不同。以對字符串“123456789”的處理為例具體說明如下:

發(fā)送方的處理:

DataBuf［11］={0x31，0x32，0x33，0x34，0x35，0x36，0x37，0x38，0x39，0，0}

調(diào)用 CRC_CCITT(DataBuf，9)，其返回值是0x29B1。把 29B1追加到數(shù)組 DataBuf的后面，DataBuf變成

DataBuf［11］={0x31，0x32，…，0x39，0x29，0xB1}，現(xiàn)在的DataBuf就是要發(fā)送的數(shù)據(jù)。

接收方的處理:

接收方收到11個字節(jié)的數(shù)，調(diào)用CRC_CCITT(DataBuf，11)，如果返回值是0，表示通訊是正確的，否則表示通訊中數(shù)據(jù)出錯了。

5 結(jié)語

CRC校驗由于實現(xiàn)簡單，檢錯能力強，被廣泛使用在各種數(shù)據(jù)校驗應(yīng)用中。占用系統(tǒng)資源少，用軟硬件均能實現(xiàn)，是進行數(shù)據(jù)傳輸差錯檢測的一種很好的手段。特別是匯編語言的實現(xiàn)，通過查表計算，對每個字節(jié)的處理僅需要22條語句就完成，節(jié)省了處理時間，在艦船動力控制網(wǎng)絡(luò)中的實際應(yīng)用中滿足響應(yīng)時間的要求。

［1］吳偉陵.信息處理與編碼［M］.北京:人民郵電出版社，2003.

［2］沈世鎰，陳魯生.信息論與編碼理論［M］.北京:科學出版社，2003.

［3］張宗橙.糾錯編碼原理和應(yīng)用［M］.北京:電子工業(yè)出版社，2003.

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

［5］ITU-T V.41，Code independent error control system［Z］.1989.