一種位寬可變的CRC校驗算法及硬件實現(xiàn)*

朱正鵬 朱旭鋒 李 賓 劉益華 王 超

北京航天自動控制研究所，北京100854

為保證箭上設(shè)備數(shù)據(jù)傳輸可靠性，箭載計算機設(shè)備普遍采用CRC進行數(shù)據(jù)校驗。箭上各設(shè)備在收到消息字后需要首先進行CRC校驗，校驗正確即認(rèn)為消息正確，然后根據(jù)消息中的指令數(shù)據(jù)控制相應(yīng)設(shè)備輸出，箭上計算機通信系統(tǒng)框圖如圖1所示。

圖1 箭上計算機通信系統(tǒng)框圖

傳統(tǒng)的CRC校驗算法是利用C語言在箭上設(shè)備DSP或者單片機等CPU處理器芯片上實現(xiàn)，隨著可編程邏輯器件性能逐漸強大，很多箭上計算機設(shè)備不再配置處理器芯片，而采用硬件描述語言(HDL)在FPGA上實現(xiàn)實時的CRC校驗算法。具體實現(xiàn)方式為通過各種通信接口(RS422、1553B、RS485和以太網(wǎng))接收的數(shù)據(jù)在FPGA內(nèi)完成CRC實時校驗后將數(shù)據(jù)送到數(shù)據(jù)處理模塊。

目前普遍使用的基于FPGA的CRC校驗算法有傳統(tǒng)串行計算法、查表法和并行計算公式推導(dǎo)法等。傳統(tǒng)串行計算法只能處理固定位寬數(shù)據(jù)流，無法適應(yīng)箭載計算機多種通信接口的需求。查表法優(yōu)點在于易于實現(xiàn)，但是硬件資源耗費巨大，不滿足箭上設(shè)備資源有限的要求[1-2]。而并行計算公式法雖然處理速度快，但也只能處理固定位寬數(shù)據(jù)。以上算法若要滿足箭上快速可變位寬數(shù)據(jù)處理的要求，需要設(shè)置多個硬件模塊，可移植性差，還會增加箭上設(shè)備功耗及硬件實現(xiàn)難度。

為適應(yīng)新一代運載火箭箭上計算機設(shè)備的CRC校驗需求，開發(fā)一種位寬可變的串行CRC校驗算法，以少量硬件資源實現(xiàn)可變位寬輸入數(shù)據(jù)的快速CRC編碼，保證數(shù)據(jù)的快速實時處理以及傳輸可靠性，且模塊化的設(shè)計思路利于程序的重復(fù)利用和不同箭上計算機設(shè)備硬件平臺的移植。

1 算法原理及實現(xiàn)方案

1.1 CRC校驗基本原理

CRC校驗的基本原理是基于串行數(shù)據(jù)傳輸?shù)拈L除法，即將要發(fā)送的信息左移若干位，然后與生成多項式進行模2除法，即按位進行異或計算，得到的余數(shù)即為CRC校驗信息。[3]

將所傳送的數(shù)據(jù)用多項式M(x)表示，其信息長度為n位的二進制，用數(shù)學(xué)方法表達多項式如式(1)：

M(x)=mn-1xn-1+mn-2xn-2+…+m1x1+m0

(1)

根據(jù)要校驗的數(shù)據(jù)長度假定CRC碼長度為k位，則生成多項式的階數(shù)為k，用多項式表示如式(2)：

G(x)=gkxk+gk-1xk-1+…+g1x1+g0

(2)

將式(1)的數(shù)據(jù)序列和式(2)的生成多項式進行如式(3)的計算：

(3)

上式中得到的R(x)即為CRC碼，將其附加在原始數(shù)據(jù)流M(x)后一起發(fā)出，則發(fā)送端發(fā)送的數(shù)據(jù)T(x)為：M(x)×xk+R(x)。

接收端對數(shù)據(jù)CRC的校驗就是將接收的數(shù)據(jù)和CRC多項式進行模2除，用多項式表達如式(4)：

(4)

將式(3)代入式(4)得到：

(5)

相同數(shù)據(jù)流按位異或結(jié)果為0，因此式(5)簡化為：

(6)

如果接收碼流沒有出現(xiàn)誤碼，接收碼應(yīng)當(dāng)?shù)扔谏鲜街邪l(fā)送碼T(x)，此時接收碼可以被生成多項式G(x)整除。反之，若無法整除，則在傳輸中發(fā)生誤碼。另外在信息傳輸中還有一種校驗方法，CRC碼直接被用于監(jiān)測通信過程中的誤碼。傳輸數(shù)據(jù)期間，發(fā)送端計算每個數(shù)據(jù)塊的CRC，數(shù)據(jù)塊發(fā)送完畢后，CRC校驗碼也發(fā)送出去。接收端用同樣的生成多項式處理接收到的數(shù)據(jù)塊，若接收的數(shù)據(jù)無誤，則接收端計算得到的CRC碼應(yīng)當(dāng)和發(fā)送端的CRC碼一致。

1.2 CRC校驗算法硬件實現(xiàn)方法及比較

傳統(tǒng)箭載計算機設(shè)備主要采用CPU芯片執(zhí)行C語言軟件算法來完成箭上總線通信過程中的CRC校驗。本文研究重點是如何使CRC校驗從CPU功能模塊中剝離出來，可以獨立運行于可編程邏輯器件上，并且不同的箭載計算機設(shè)備可以通過該算法模塊預(yù)留的配置接口計算不同位寬消息字的CRC校驗結(jié)果。

CRC硬件校驗方法有傳統(tǒng)串行計算法、查表法和并行計算法3種實現(xiàn)方式。本文依據(jù)新一代運載火箭箭上計算機設(shè)備需求，基于傳統(tǒng)的串行計算法提出一種位寬可變的串行CRC校驗算法，下面對這幾種實現(xiàn)方法進行分析比較。

1.2.1 傳統(tǒng)串行計算法

傳統(tǒng)串行計算法是根據(jù)CRC碼多項式定義，采取除法硬件電路實現(xiàn)，按照一組線性反饋移位寄存器和模2加單元完成硬件除法功能。對于固定位寬的待校驗數(shù)據(jù)，傳統(tǒng)串行計算法是按位產(chǎn)生CRC，也就是通過一個線性反饋一位寄存器(LFSR)按每次輸入一位的方式產(chǎn)生CRC。該方法原理清晰、實現(xiàn)簡單，但是每個時鐘周期僅能處理1bit數(shù)據(jù)，速度較慢，且只能處理固定位寬數(shù)據(jù)流，可移植性差。

以CRC-CCCITT為例，使用多項式x16+x12+x5+1(簡記為0x11021)的串行電路如圖2所示，圖中G[0]=G[5]=G[12]=1[4-5]。

圖2 串行計算法硬件回路

1.2.2 按字節(jié)處理的查表法

利用查表法計算CRC時，讓數(shù)據(jù)字節(jié)與累加器中的高位字節(jié)“異或”，得到組合值(該組合值CRC值已建立并存在表中)，組合值再與累加器中的低位字節(jié)“異或”。由于移位操作少，因此在用查表法計算時，速度比串行計算法快4～10倍。查表法是目前使用較多的一種CRC校驗實現(xiàn)方式，代碼量少，但是需要硬件提供一個較大的查找表(LUT，Look-Up Table)。當(dāng)以8位的傳送信息字節(jié)與16位累加器高8位異或時，累加器中的新值為異或后的組合值加上未改變的低8位值，因此只有28=256種可能組合值，可以事先計算好組合值并存入查找表中。

1.2.3 多比特并行計算法

并行計算法可以根據(jù)生成多項式的反饋特性，將串行的比特反饋等效成并行計算等式。由圖2可以看出，各移位寄存器的存數(shù)即為CRC余數(shù)值，當(dāng)進行串行CRC運算時，當(dāng)前的CRC余數(shù)值僅與當(dāng)前信息碼的最前一位輸入值和前一狀態(tài)的CRC余數(shù)值相關(guān)。因此，在進行多比特并行CRC運算時，多比特信息碼一次輸入并行運算電路產(chǎn)生的CRC值應(yīng)當(dāng)和多比特信息碼一次輸入串行運算電路產(chǎn)生的CRC值相同?；谠撍枷?，文獻[3-4]將串行計算法改為并行計算法，并給出并行數(shù)據(jù)的CRC-CCITT編碼電路結(jié)構(gòu)圖(圖3)。

圖3 并行計算編碼電路結(jié)構(gòu)圖

圖3中，R0～R15作為存放余數(shù)的寄存器，輸入待校驗的數(shù)據(jù)位N位并行數(shù)據(jù)D(N-1 downto 0)。并行數(shù)據(jù)通過一個并行運算電路和余數(shù)寄存器中的數(shù)據(jù)進行運算，得到的結(jié)果依然保存在余數(shù)寄存器中。每個時鐘周期完成N位的CRC運算并將結(jié)果保存在CRC(N-1 downto 0)中，在下一個時鐘對后續(xù)并行數(shù)據(jù)繼續(xù)運算。對應(yīng)不同的輸入數(shù)據(jù)位寬N，并行計算法的推導(dǎo)公式是不一樣的，需要根據(jù)輸入數(shù)據(jù)位寬改變推導(dǎo)算法。

1.2.4 位寬可變的串行計算法

從圖2傳統(tǒng)的串行計算法硬件電路的實現(xiàn)不難看出，電路的主要結(jié)構(gòu)是寄存器和異或門。而針對不同位寬的待校驗數(shù)據(jù)的主要差別在于寄存器個數(shù)、初始化值、異或門輸入位及最后待校驗值的處理上。如果每種位寬的數(shù)據(jù)都按傳統(tǒng)計算實現(xiàn)，雖然功能沒有問題，但從硬件資源上造成一定程度的浪費。

本文提出的位寬可變的串行計算法將不同位寬的校驗編碼進行一體化設(shè)計，控制通道由moor狀態(tài)機實現(xiàn)，控制不同位寬的編碼校驗操作。如圖4流程圖所示，硬件模擬算法如下：

a)首先在要傳輸?shù)臄?shù)據(jù)塊之后補2個字節(jié)的零；

b)設(shè)置一個CRC寄存器，并賦初值為0；

c)將數(shù)據(jù)塊第一個8位字符與16位CRC寄存器低8位進行異或，并將結(jié)果存入CRC寄存器；

d)將CRC寄存器右移一位，并給最高位補0，移出并檢查最低位的值；

e)若最低位值為0，則重復(fù)d步驟；若為1，CRC寄存器與多項式碼進行異或；

f)重復(fù)d步和e步直到8次移位全部完成，此時一個8位數(shù)據(jù)處理完畢；

g)重復(fù)c到f直到所有數(shù)據(jù)全部處理完成；

h)CRC寄存器最終的內(nèi)容即為CRC值。

圖4 位寬可變的串行計算法流程圖

1.2.5 實現(xiàn)方法比較

如表1所示，對于硬件實現(xiàn)來說，查表法需要占用芯片面積構(gòu)造一個ROM實現(xiàn)的表，在硬件資源緊張的情況下，CRC計算可以有2種方式:1)本文提出的位寬可變的串行方式；2)并行公式推導(dǎo)計算的方式。位寬可變的串行計算算法結(jié)構(gòu)規(guī)則，程序模塊可移植性強，硬件資源耗費少，可靠性高，缺點是每個時鐘周期只能計算1位的結(jié)果，速度較慢，適用于數(shù)據(jù)位寬多變的通訊模式。并行方式是每次輸入一組并行數(shù)據(jù)，同時產(chǎn)生出CRC結(jié)果。并行方式處理速度較快，但是需要根據(jù)數(shù)據(jù)位寬改變算法，適合用于傳輸固定位寬數(shù)據(jù)的高速通訊模式。

表1 實現(xiàn)方法比較

*注：T表示FPGA本地時鐘周期。

2 數(shù)據(jù)位寬可變的CRC編碼的HDL實現(xiàn)

根據(jù)1.2.4節(jié)所述位寬可變的串行計算法實現(xiàn)方案，模塊設(shè)計利用VHDL語言進行硬件描述，標(biāo)識符為crc16_dataN.vhd，并通過ModelSim SE PLUS 6.5a進行仿真。

如圖5所示，模塊使用5個狀態(tài)的狀態(tài)機完成一次計算過程：IDLE_ST，START_CAL_ST，CHECK_BIT_ST，XOR_ST和DONE_ST。

圖5 狀態(tài)機流程圖

IDLE_ST：crc_r賦值為全’0’。跳轉(zhuǎn)條件：當(dāng)data_valid為’1’，跳轉(zhuǎn)到START_CAL_ST。

START_CAL_ST：data_tmp賦值為data_latch & x"0000"，crc_tmp高17位賦值為生成多項式，低位全補’0’，MSB賦值為N+15。跳轉(zhuǎn)條件：直接跳轉(zhuǎn)到CHECK_BIT_ST。

CHECK_BIT_ST：如果MSB>15 并 data_tmp(MSB)=’0’,則將MSB減1，并把crc_tmp右移1位，高位補’0’。跳轉(zhuǎn)條件：如果MSB小于或等于15，跳轉(zhuǎn)到DONE_ST；如果MSB>15并且data_tmp(MSB) =’1’，跳轉(zhuǎn)到XOR_ST。

XOR_ST：data_tmp與crc_tmp異或并存入data_tmp；crc_tmp右移，高位補’0’；MSB減1。跳轉(zhuǎn)條件：直接跳轉(zhuǎn)到CHECK_BIT_ST。

DONE_ST：crc_valid置’1’,crc_r賦值為data_tmp的低16位。跳轉(zhuǎn)條件：完成了一次計算，跳轉(zhuǎn)到IDLE_ST。

2.1 實現(xiàn)說明

模塊的管腳特性及信號說明如表2所示，表中data信號的位寬N為外部用戶可配置參數(shù)，該參數(shù)為需要進行CRC校驗數(shù)據(jù)的位寬，N必須為8的倍數(shù)，類型為整數(shù)。

表2 模塊信號說明表

表3列出模塊實現(xiàn)所需的內(nèi)部寄存器，N為外部輸入信號data的位寬。當(dāng)data_valid=’1’時，data_latch將輸入的data鎖存。本模塊CRC生成多項式用"10001000000100001"來表示。

表3 模塊內(nèi)部寄存器說明表

2.2 仿真驗證

根據(jù)模塊接口特性編寫TestBench仿真文件，利用ModelSim對模塊進行仿真驗證。仿真思路為：分別選取16bit、32bit和64bit隨機數(shù)據(jù)作為待編碼數(shù)據(jù)，工作頻率選為25MHz，驗證所編寫的IP核的有效性和參數(shù)可擴展性。如圖6所示，當(dāng)輸入16bit并行數(shù)據(jù)x"ABFE"時，輸出CRC碼為x"344F"；如圖7所示，當(dāng)輸入32bit并行數(shù)據(jù)x"FFFFABFE"時，輸出CRC碼為x"6D75"；如圖8所示，當(dāng)輸入64bit并行數(shù)據(jù)x"00000000FFFFFFFF"時，輸出CRC碼為x"3F2E"。

3 結(jié)果分析

設(shè)計采用VHDL硬件描述語言實現(xiàn)，可以很好地應(yīng)用于各類FPGA平臺的工程實踐上。如表4所示，分別用Xilinx的XQV600系列芯片、Actel的A3P1000系列芯片、Altera的EP2C35系列芯片對該模塊進行硬件實現(xiàn)，資源耗費統(tǒng)計結(jié)果與器件型號及綜合使用的工具有很大的關(guān)系。

圖6 CRC碼為x"344F"

圖7 CRC碼為x"6D75"

圖8 CRC碼為x"3F2E"

表4 不同F(xiàn)PGA平臺資源耗費統(tǒng)計

4 結(jié)論

分析了CRC計算原理的基礎(chǔ)上，用VHDL硬件語言實現(xiàn)一種輸入數(shù)據(jù)位寬可變的CRC校驗算法。該方法較其他實現(xiàn)方式具有可配置、可靠性高及占用資源少的優(yōu)點，方便在各類FPGA平臺上實現(xiàn)。目前該算法模塊已應(yīng)用于我國新一代運載火箭箭上計算機系統(tǒng)，并在多次正式飛行試驗中得到成功應(yīng)用及驗證。