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

北京航天自動(dòng)控制研究所，北京100854

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

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

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

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

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

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

1.1 CRC校驗(yàn)基本原理

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

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

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

(1)

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

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

(2)

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

(3)

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

接收端對(duì)數(shù)據(jù)CRC的校驗(yàn)就是將接收的數(shù)據(jù)和CRC多項(xiàng)式進(jìn)行模2除，用多項(xiàng)式表達(dá)如式(4)：

(4)

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

(5)

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

(6)

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

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

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

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

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

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

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

圖2 串行計(jì)算法硬件回路

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

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

1.2.3 多比特并行計(jì)算法

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

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

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

1.2.4 位寬可變的串行計(jì)算法

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

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

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

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

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

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

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

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

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

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

圖4 位寬可變的串行計(jì)算法流程圖

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

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

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

*注：T表示FPGA本地時(shí)鐘周期。

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

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

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

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

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位賦值為生成多項(xiàng)式，低位全補(bǔ)’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位，高位補(bǔ)’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右移，高位補(bǔ)’0’；MSB減1。跳轉(zhuǎn)條件：直接跳轉(zhuǎn)到CHECK_BIT_ST。

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

2.1 實(shí)現(xiàn)說(shuō)明

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

表2 模塊信號(hào)說(shuō)明表

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

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

2.2 仿真驗(yàn)證

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

3 結(jié)果分析

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

圖6 CRC碼為x"344F"

圖7 CRC碼為x"6D75"

圖8 CRC碼為x"3F2E"

表4 不同F(xiàn)PGA平臺(tái)資源耗費(fèi)統(tǒng)計(jì)

4 結(jié)論

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