一種位寬可變的CRC校驗算法及硬件實現*

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

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

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

圖1 箭上計算機通信系統框圖

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

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

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

1 算法原理及實現方案

1.1 CRC校驗基本原理

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

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

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

(1)

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

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

(2)

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

(3)

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

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

(4)

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

(5)

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

(6)

如果接收碼流沒有出現誤碼，接收碼應當等于上式中發送碼T(x)，此時接收碼可以被生成多項式G(x)整除。反之，若無法整除，則在傳輸中發生誤碼。另外在信息傳輸中還有一種校驗方法，CRC碼直接被用于監測通信過程中的誤碼。傳輸數據期間，發送端計算每個數據塊的CRC，數據塊發送完畢后，CRC校驗碼也發送出去。接收端用同樣的生成多項式處理接收到的數據塊，若接收的數據無誤，則接收端計算得到的CRC碼應當和發送端的CRC碼一致。

1.2 CRC校驗算法硬件實現方法及比較

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

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

1.2.1 傳統串行計算法

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

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

圖2 串行計算法硬件回路

1.2.2 按字節處理的查表法

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

1.2.3 多比特并行計算法

并行計算法可以根據生成多項式的反饋特性，將串行的比特反饋等效成并行計算等式。由圖2可以看出，各移位寄存器的存數即為CRC余數值，當進行串行CRC運算時，當前的CRC余數值僅與當前信息碼的最前一位輸入值和前一狀態的CRC余數值相關。因此，在進行多比特并行CRC運算時，多比特信息碼一次輸入并行運算電路產生的CRC值應當和多比特信息碼一次輸入串行運算電路產生的CRC值相同。基于該思想，文獻[3-4]將串行計算法改為并行計算法，并給出并行數據的CRC-CCITT編碼電路結構圖(圖3)。

圖3 并行計算編碼電路結構圖

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

1.2.4 位寬可變的串行計算法

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

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

a)首先在要傳輸的數據塊之后補2個字節的零；

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

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

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

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

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

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

h)CRC寄存器最終的內容即為CRC值。

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

1.2.5 實現方法比較

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

表1 實現方法比較

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

2 數據位寬可變的CRC編碼的HDL實現

根據1.2.4節所述位寬可變的串行計算法實現方案，模塊設計利用VHDL語言進行硬件描述，標識符為crc16_dataN.vhd，并通過ModelSim SE PLUS 6.5a進行仿真。

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

圖5 狀態機流程圖

IDLE_ST：crc_r賦值為全’0’。跳轉條件：當data_valid為’1’，跳轉到START_CAL_ST。

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

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

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

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

2.1 實現說明

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

表2 模塊信號說明表

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

表3 模塊內部寄存器說明表

2.2 仿真驗證

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

3 結果分析

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

圖6 CRC碼為x"344F"

圖7 CRC碼為x"6D75"

圖8 CRC碼為x"3F2E"

表4 不同FPGA平臺資源耗費統計

4 結論

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