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

張曉輝，熊 卿，丁 瑋

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

1 概述

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

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

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

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

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

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

2.1 基本概念

2.1.1 多項(xiàng)式與二進(jìn)制數(shù)碼

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

2.1.2 生成多項(xiàng)式

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

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

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

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

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

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

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

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

2.1.3 模2除(按位除)

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

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

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

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

2.1.4 CRC碼的生成步驟

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

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

3)用生成多項(xiàng)式G(x)(二進(jìn)制數(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碼的校驗(yàn)

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

2.2 CRC的糾錯(cuò)能力

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

3 CRC校驗(yàn)碼的算法分析

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

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

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

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

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

算法Ⅰ

//reg是一個(gè)5 bits的寄存器

把reg中的值置0.

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

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

Begin

If(reg首位是1)

reg=reg XOR 0011.

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

End

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

這種算法簡單，容易實(shí)現(xiàn)，對任意長度生成多項(xiàng)式的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)化后的算法有一種直觀的了解，先將上面的算法換個(gè)角度理解一下。在上面例子中，可以將編碼過程看作如下過程:

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

算法Ⅱ

//reg是1個(gè)4 bits的寄存器

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

把reg中的值置0.

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

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

Begin

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

reg=reg XOR t［移出的位］

End

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

算法Ⅲ

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

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

把reg中的值置0.

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

While(len——)

Begin

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

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

End

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

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

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

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

請注意以下2個(gè)事實(shí):

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

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

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

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

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

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

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

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

算法Ⅳ:

把reg中的值置0.

While(len——)

Begin

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

Reg左移出的字節(jié)與新讀入的1個(gè)字節(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í)上，如果數(shù)據(jù)序列有一長串前導(dǎo)0字節(jié)(這在實(shí)際通訊是可能發(fā)生的)，其CRC計(jì)算結(jié)果將是這些前導(dǎo)0好像不存在，也就是說計(jì)算出的CRC碼與前導(dǎo)0無關(guān)(見表2)。因此，聰明一點(diǎn)的做法是設(shè)置初始值為1個(gè)非0值，通常設(shè)為0xFFFF。注:括號中的數(shù)字表示數(shù)據(jù)序列的字節(jié)長度。

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

While(len——)

Begin

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

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

reg=reg XOR t［index］

End

return reg

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

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

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

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

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

3)生成多項(xiàng)式:0x1021;

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

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

4.1 C語言

4.2 8051匯編語言

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

發(fā)送和接收都使用同一個(gè)程序，只是其入口參數(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個(gè)字節(jié)的數(shù)，調(diào)用CRC_CCITT(DataBuf，11)，如果返回值是0，表示通訊是正確的，否則表示通訊中數(shù)據(jù)出錯(cuò)了。

5 結(jié)語

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

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

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

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

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

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