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

左飛飛，杜英森，劉劍霏

(西安機(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)行額外的驗證，使接收端能發(fā)現(xiàn)某些錯誤，進(jìn)而實現(xiàn)糾錯功能，常用的編碼方法有CRC-32校驗碼、CRC-16校驗碼、漢明碼、奇偶校驗法等[1]。其中32位循環(huán)冗余校驗(Cyclic Redundancy Check)簡稱CRC-32校驗在性能和資源消耗兩方面都有較大的優(yōu)勢，因而，在無線電通信、SATA硬盤數(shù)據(jù)傳輸?shù)认到y(tǒng)中，CRC-32校驗是最常用的檢錯手段之一[2]。

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

編程實現(xiàn)CRC-32校驗碼生成程序有兩種傳統(tǒng)方法：一種為串行算法，一種為查表法。這兩種是循環(huán)調(diào)用的函數(shù)，設(shè)置一個CRC寄存器，設(shè)置寄存器初始值后，依次根據(jù)輸入數(shù)據(jù)進(jìn)行計算，更新CRC寄存器的數(shù)值，直至對數(shù)據(jù)處理完畢，CRC寄存器最終存放的數(shù)據(jù)即為CRC值[4]。這兩種方法都能實現(xiàn)運(yùn)算目的，但串行算法由于需要一位一位地計算運(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校驗碼生成方法，能夠根據(jù)不同芯片寄存器空間的限制，最大限度的利用存儲空間提升運(yùn)算速度。

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

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

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

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

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

1.1 串行算法[7]

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

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

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

1.2 查表法[8]

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

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

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

串行算法雖然速度慢，但其每次計算過程在邏輯上都完全按照CRC-32校驗碼的生成原理，每次串行算法的結(jié)果與初始值之間的邏輯關(guān)系可以由CRC-32校驗碼生成原理經(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校驗碼并行改進(jìn)算法以遞推法為基礎(chǔ)，根據(jù)實際情況中不同的計算速度和占用空間的需求，計算出并行輸入任意n位數(shù)據(jù)時CRC寄存器中新老數(shù)據(jù)之間的并行邏輯關(guān)系，并根據(jù)這一邏輯關(guān)系修改程序，從而達(dá)到在一定占用空間的限制下，最大程度提升運(yùn)算速度的目的。

3 仿真驗證

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

基于第2章所使用的CRC-32特征多項式，類似上面的推算，我們可以分別得出并行輸入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 正確性仿真驗證

首先驗證本文提出方法的正確性，編寫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)行計算，發(fā)現(xiàn)三者得到的結(jié)果一致，證明本文提出的計算數(shù)據(jù)無誤。

3.2 占用空間與計算速度的仿真驗證

3.3.1占用空間對比

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

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

3.3.2計算速度對比

隨機(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)計Fig.2 Numbers of slice registers of 16/8/4 bits parallel algorithm

圖3 串行算法和查表法占用空間統(tǒng)計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位遞推并行輸入算法計算時間Fig.4 Time consumptions of slice registers of 16/8/4 bits parallel algorithm

圖5 查表法與串行算法計算時間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)方法計算速度更快。并行輸入16位、8位、4位數(shù)據(jù)的遞推并行算法的仿真結(jié)果說明，本文提出的基于遞推法的CRC-32校驗碼并行改進(jìn)算法速度快于按位串行計算的方法，存儲空間小于查表法，有利于小型化、快速化的硬件實現(xiàn)。

4 結(jié)論

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