艦船動力控制網絡CRC算法分析及程序實現

2011-08-20 08:40:58張曉輝

艦船科學技術 2011年8期

張曉輝，熊卿，丁瑋

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

1 概述

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

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

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

2 循環冗余校驗碼(CRC)

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

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

2.1 基本概念

2.1.1 多項式與二進制數碼

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

2.1.2 生成多項式

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

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

生成多項式應滿足以下條件:

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

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

3)不同位發生錯誤時，余數應不同。

4)對余數繼續做模2除，余數應能循環。

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

2.1.3 模2除(按位除)

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

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

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

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

2.1.4 CRC碼的生成步驟

1)將x的最高冪次為R的生成多項式G(x)轉換成對應的R+1位二進制數。

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

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

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

5)發送方發送的數據就是C(x)*2R+Y(x)。

2.1.5 CRC碼的校驗

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

2.2 CRC的糾錯能力

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

3 CRC校驗碼的算法分析

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

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

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

表1 求余數過程Tab.1 Diagram of computing the remainder

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

算法Ⅰ

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

把reg中的值置0.

把原始的數據后添加r個0.

While(數據未處理完)

Begin

If(reg首位是1)

reg=reg XOR 0011.

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

End

reg的后4位就是我們所要求的余數。

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

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

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

算法Ⅱ

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

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

把reg中的值置0.

在原始的數據后添加4個0.

While(數據未處理完)

Begin

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

reg=reg XOR t［移出的位］

End

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

算法Ⅲ

//reg是1個2字節的寄存器

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

把reg中的值置0.

在原始的數據后添加2個0字節.

While(len——)

Begin

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

reg=reg XOR t［移出的字節］

End

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

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

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

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

請注意以下2個事實:

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

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

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

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

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

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

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

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

算法Ⅳ:

把reg中的值置0.

While(len——)

Begin

reg中的值左移1個字節，

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

reg=reg XOR t［index］

End

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

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

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

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

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

While(len——)

Begin

reg中的值左移1個字節，

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

reg=reg XOR t［index］

End

return reg

這里，len是數據序列本身的長度。