左飛飛，杜英森，劉劍霏

(西安機(jī)電信息技術(shù)研究所，陜西 西安 710065)

0 引言

在數(shù)據(jù)的傳輸過程中由于空間電磁環(huán)境復(fù)雜等原因，可能會產(chǎn)生誤碼，即某幾位數(shù)據(jù)0變?yōu)?，或1變?yōu)?，導(dǎo)致接收端得到錯誤的數(shù)據(jù)。為了降低誤碼率，通常對數(shù)據(jù)進(jìn)行特定編碼，在收發(fā)端進(jìn)行額外的驗(yàn)證，使接收端能發(fā)現(xiàn)某些錯誤，進(jìn)而實(shí)現(xiàn)糾錯功能，常用的編碼方法有CRC-32校驗(yàn)碼、CRC-16校驗(yàn)碼、漢明碼、奇偶校驗(yàn)法等[1]。其中32位循環(huán)冗余校驗(yàn)(Cyclic Redundancy Check)簡稱CRC-32校驗(yàn)在性能和資源消耗兩方面都有較大的優(yōu)勢，因而，在無線電通信、SATA硬盤數(shù)據(jù)傳輸?shù)认到y(tǒng)中，CRC-32校驗(yàn)是最常用的檢錯手段之一[2]。

計(jì)算CRC-32校驗(yàn)碼有兩類方法：一類方法是將CRC-32校驗(yàn)碼生成過程轉(zhuǎn)換為對應(yīng)的邏輯門電路，將這樣的門電路固化在系統(tǒng)的整體電路中，它的優(yōu)點(diǎn)是計(jì)算速度快，但由于它是專門為固定的通信系統(tǒng)設(shè)計(jì)的電路，所以無法更改和移植，并且專門設(shè)計(jì)和集成的成本較高[3]；另一類是編程實(shí)現(xiàn)，在眾多編程實(shí)現(xiàn)的途徑中，F(xiàn)PGA和CPLD由于其可并行計(jì)算、可反復(fù)修改的特性使其在CRC-32的計(jì)算中有較大優(yōu)勢。

編程實(shí)現(xiàn)CRC-32校驗(yàn)碼生成程序有兩種傳統(tǒng)方法：一種為串行算法，一種為查表法。這兩種是循環(huán)調(diào)用的函數(shù)，設(shè)置一個CRC寄存器，設(shè)置寄存器初始值后，依次根據(jù)輸入數(shù)據(jù)進(jìn)行計(jì)算，更新CRC寄存器的數(shù)值，直至對數(shù)據(jù)處理完畢，CRC寄存器最終存放的數(shù)據(jù)即為CRC值[4]。這兩種方法都能實(shí)現(xiàn)運(yùn)算目的，但串行算法由于需要一位一位地計(jì)算運(yùn)行結(jié)果，導(dǎo)致運(yùn)行速度過慢，查表法由于需要存儲所有的運(yùn)算結(jié)果，導(dǎo)致占用空間過大。

引信應(yīng)用環(huán)境最大的特點(diǎn)就是過載數(shù)值大、體積小，在這樣的前提下進(jìn)行篩選，現(xiàn)在使用的某品牌QFN封裝CPLD的最小體積可小至5 mm×5 mm，但是由于這樣的FPGA或CPLD一般是入門級產(chǎn)品，寄存器位數(shù)通常只有100～300左右，在這樣的條件限制下，需要提出一種新的CRC-32校驗(yàn)碼生成方法，能夠根據(jù)不同芯片寄存器空間的限制，最大限度的利用存儲空間提升運(yùn)算速度。

在CRC-32校驗(yàn)碼生成方法中，固定電路成本高且缺乏靈活性，傳統(tǒng)按位串行算法計(jì)算速度慢、查表法需要額外占用空間，本文針對此問題，提出了基于遞推法的CRC-32校驗(yàn)碼并行改進(jìn)算法。

1 傳統(tǒng)CRC-32校驗(yàn)碼的生成算法

CRC校驗(yàn)的基本原理如下[5]：CRC校驗(yàn)發(fā)收端的首要工作是確認(rèn)系統(tǒng)所采用的生成多項(xiàng)式G(x)，任意一個由二進(jìn)制位串組成的代碼都可以和一個系數(shù)僅為‘0’和‘1’取值的多項(xiàng)式一一對應(yīng)，例如：代碼1010111對應(yīng)的多項(xiàng)式為x6+x4+x2+x+1，而多項(xiàng)式x4+x3+1對應(yīng)的代碼為11001。校驗(yàn)碼的具體生成過程為：假設(shè)要發(fā)送的信息用多項(xiàng)式C(x)表示，將C(x)左移R位(可表示成C(x)×2R)，這樣C(x)的右邊就會空出R位，這就是校驗(yàn)碼的位置。用C(x)×2R除以生成多項(xiàng)式G(x)得到的余數(shù)r(x)就是校驗(yàn)碼，將它們組合起來，變?yōu)閧C(x),r(x)}并發(fā)送出去，這樣發(fā)送的數(shù)據(jù)就是一個能被生成多項(xiàng)式G(x)整除(模2除)的碼多項(xiàng)式。接收端收到{C(x),r(x)}后，用它除以生成多項(xiàng)式G(x)，如果余數(shù)為0，則說明傳輸過程中無錯誤發(fā)生，否則說明傳輸有誤。

由上述可知，生成多項(xiàng)式G(x)是構(gòu)成CRC校驗(yàn)碼的關(guān)鍵。并不是任何一個多項(xiàng)式都可以作為生成多項(xiàng)式，從檢錯與糾錯的要求出發(fā)，生成多項(xiàng)式應(yīng)能滿足下列要求：1)任何一位發(fā)生錯誤都應(yīng)使余數(shù)不為0；2)不同位發(fā)生錯誤應(yīng)當(dāng)使余數(shù)不同；3)應(yīng)滿足余數(shù)循環(huán)規(guī)律。國際上常用的幾種CRC校驗(yàn)碼及其生成多項(xiàng)式如下所示[6]：

CRC-12：x12+x11+x3+x2+x+1，

CRC-16:x16+x15+x2+1，

CRC-CCITT:x16+x12+x5+1，

CRC-32:x32+x26+x23+x22+x16+x12+x11+x10+x8+x7+x5+x4+x2+x+1。

生成多項(xiàng)式的G(x)位數(shù)越高，檢錯能力就越強(qiáng)，由于CRC-32的可靠性，把CRC-32用于重要數(shù)據(jù)傳輸，在通信、計(jì)算機(jī)等領(lǐng)域運(yùn)用十分廣泛。

1.1 串行算法[7]

依據(jù)CRC校驗(yàn)碼的產(chǎn)生原理來設(shè)計(jì)程序，寄存器每輸入8位或16位待計(jì)算數(shù)據(jù)后更新一次，以8位為例說明該算法。

圖1 每次輸入1字節(jié)的CRC-32串行算法Fig.1 Byte-wise serial algorithm for CRC-32 check code

這種方法的思路與CRC校驗(yàn)碼的生成原理一致，優(yōu)點(diǎn)是可讀性強(qiáng)，占用空間小，模塊代碼較少，修改靈活，可移植性較強(qiáng)，缺點(diǎn)也很明顯，每位數(shù)據(jù)都要進(jìn)行一次移位與異或計(jì)算，計(jì)算量大，速度慢。

1.2 查表法[8]

查表法的基本原理是把所有會出現(xiàn)的CRC碼全部計(jì)算出來，放在一個表里，每次進(jìn)數(shù)據(jù)通過查表得到當(dāng)次結(jié)果，省去了計(jì)算時間，可大大提高運(yùn)行速度。對于CRC-32來說，共有256組32位的數(shù)據(jù)需要提前存儲在處理器的寄存器中，寄存器中的一部分?jǐn)?shù)據(jù)如下：

查表法的優(yōu)缺點(diǎn)基本與串行計(jì)算法相反，由于每次計(jì)算只需查表即可得到答案，因此它的運(yùn)行速度很快，但是相對的，存儲這樣的一個查找表至少需要占用256×32=8 192位寄存器，占用空間對于寄存器較少的CPLD或入門級FPGA過大，另外這樣的查找表一旦約定的寄存器初始值不同或選擇的特征多項(xiàng)式不同，整個表內(nèi)的所有值都需要重新計(jì)算，幾乎沒有可修改性，移植性較弱。

2 基于遞推法的CRC-32校驗(yàn)碼并行改進(jìn)算法

串行算法雖然速度慢，但其每次計(jì)算過程在邏輯上都完全按照CRC-32校驗(yàn)碼的生成原理，每次串行算法的結(jié)果與初始值之間的邏輯關(guān)系可以由CRC-32校驗(yàn)碼生成原理經(jīng)過簡單的推導(dǎo)轉(zhuǎn)化成并行邏輯關(guān)系。根據(jù)這樣的思路，可以將第一次串行算法的結(jié)果作為第二次串行算法的初始值，再將第二次串行算法的結(jié)果作為第三次串行算法的初始值，按照這樣的規(guī)律層層遞推n次，就可以直接得到并行輸入任意n位數(shù)據(jù)時CRC寄存器中新老數(shù)據(jù)之間的并行邏輯關(guān)系。

(1)

(2)

(3)

(4)

基于遞推法的CRC-32校驗(yàn)碼并行改進(jìn)算法以遞推法為基礎(chǔ)，根據(jù)實(shí)際情況中不同的計(jì)算速度和占用空間的需求，計(jì)算出并行輸入任意n位數(shù)據(jù)時CRC寄存器中新老數(shù)據(jù)之間的并行邏輯關(guān)系，并根據(jù)這一邏輯關(guān)系修改程序，從而達(dá)到在一定占用空間的限制下，最大程度提升運(yùn)算速度的目的。

3 仿真驗(yàn)證

為了具有代表性，本文在仿真驗(yàn)證過程中分別并行輸入16位數(shù)據(jù)、8位數(shù)據(jù)、4位數(shù)據(jù)的遞推并行算法進(jìn)行驗(yàn)證。

基于第2章所使用的CRC-32特征多項(xiàng)式，類似上面的推算，我們可以分別得出并行輸入16位數(shù)據(jù)、8位數(shù)據(jù)、4位數(shù)據(jù)的CRC低6位更新邏輯，其中并行輸入4位的CRC-32更新邏輯(低6位)如下所示：

crc_new[0]=crc_old[28]^data_in[0];

crc_new[1]=crc_old[28]^crc_old[29]^data_in[0]^data_in[1];

crc_new[2]=crc_old[28]^crc_old[29]^crc_old[30]^data_in[0]^data_in[1]^data_in[2];

crc_new[3]=crc_old[29]^crc_old[30]^crc_old[31]^data_in[1]^data_in[2]^data_in[3];

crc_new[4]=crc_old[0]^crc_old[28]^crc_old[30]^crc_old[31]^data_in[0]^data_in[2]^data_in[3];

crc_new[5]=crc_old[1]^crc_old[28]^crc_old[29]^crc_old[31]^data_in[0]^data_in[1]^data_in[3]。

3.1 正確性仿真驗(yàn)證

首先驗(yàn)證本文提出方法的正確性，編寫Verilog程序，在ISE軟件環(huán)境下進(jìn)行編譯后，設(shè)定同樣的初始值、輸入數(shù)據(jù)，如果得到的結(jié)果相同，則證明該算法無誤，反之說明算法不正確。

設(shè)定初始值32′hFFFFFFFF，取輸入數(shù)據(jù)為32′h12345678，使用并行輸入16位、8位、4位數(shù)據(jù)的遞推并行算法運(yùn)行程序，輸出結(jié)果為32′h4A090E98，再通過查表法與串行算法分別進(jìn)行計(jì)算，發(fā)現(xiàn)三者得到的結(jié)果一致，證明本文提出的計(jì)算數(shù)據(jù)無誤。

3.2 占用空間與計(jì)算速度的仿真驗(yàn)證

3.3.1占用空間對比

在ISE軟件中，程序設(shè)計(jì)占用寄存器數(shù)量等片上資源在Design Summary中可以直觀的看到，分別截取16位、8位、4位遞推并行算法、串行算法和查表法的界面即可做出比較。

根據(jù)圖2、圖3可以看到：并行輸入16位、8位、4位數(shù)據(jù)的遞推并行算法占用寄存器分別為449個、225個和68個；查表法占用寄存器2 095個；串行算法占用寄存器32個。

3.3.2計(jì)算速度對比

隨機(jī)輸入一串長度為1 000位的數(shù)據(jù)，在ISE自帶仿真器中對比得出最后結(jié)果的時刻數(shù)字，如圖4、圖5所示。根據(jù)圖4、圖5可以看到：本文提出的遞推并行算法與查表法、串行算法所得結(jié)果相同并且均為正確結(jié)果，其中并行輸入16位、8位、4位數(shù)據(jù)的遞推并行算法分別在第106、190、315個時鐘周期得出正確結(jié)果，查表法在第59個時鐘周期得出正確結(jié)果，串行算法在第2 107個時鐘周期得出正確結(jié)果。

圖2 16位、8位、4位并行算法占用空間統(tǒng)計(jì)Fig.2 Numbers of slice registers of 16/8/4 bits parallel algorithm

圖3 串行算法和查表法占用空間統(tǒng)計(jì)Fig.3 Numbers of slice registers of serial algorithm and the look-up table method

3.3 仿真結(jié)果分析

根據(jù)3.1節(jié)、3.2節(jié)，將仿真數(shù)據(jù)匯總在表1中做比對，其中，占用空間s越小越好，處理時間t越短越好。

圖4 并行輸入16位、8位、4位遞推并行輸入算法計(jì)算時間Fig.4 Time consumptions of slice registers of 16/8/4 bits parallel algorithm

圖5 查表法與串行算法計(jì)算時間Fig.5 Time consumptions of slice registers of serial algorithm and the look-up table method

算法占用空間s(寄存器個數(shù))處理時間t(時鐘周期)16位遞推并行算法4491068位遞推并行算法2251904位遞推并行算法68315串行算法322 107查表法2 09559

通過比較數(shù)據(jù)可以看出，本文提出的算法在不同寄存器數(shù)量的限制下，比傳統(tǒng)方法計(jì)算速度更快。并行輸入16位、8位、4位數(shù)據(jù)的遞推并行算法的仿真結(jié)果說明，本文提出的基于遞推法的CRC-32校驗(yàn)碼并行改進(jìn)算法速度快于按位串行計(jì)算的方法，存儲空間小于查表法，有利于小型化、快速化的硬件實(shí)現(xiàn)。

4 結(jié)論

本文提出的基于遞推法的CRC-32校驗(yàn)碼并行改進(jìn)算法以遞推法為基礎(chǔ)，根據(jù)實(shí)際情況中不同的計(jì)算速度和占用空間的需求，計(jì)算出并行輸入任意n位數(shù)據(jù)時CRC寄存器中新老數(shù)據(jù)之間的并行邏輯關(guān)系，并根據(jù)這一邏輯關(guān)系修改程序，從而達(dá)到在一定占用空間的限制下，最大程度提升運(yùn)算速度的目的。仿真結(jié)果表明，本文提出的基于遞推法的CRC-32校驗(yàn)碼并行改進(jìn)算法速度快于按位串行計(jì)算的方法，存儲空間小于查表法，有利于小型化、快速化的硬件實(shí)現(xiàn)。