左飛飛，杜英森，劉劍霏

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

0 引言

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

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

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

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

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

1 傳統CRC-32校驗碼的生成算法

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

由上述可知，生成多項式G(x)是構成CRC校驗碼的關鍵。并不是任何一個多項式都可以作為生成多項式，從檢錯與糾錯的要求出發，生成多項式應能滿足下列要求：1)任何一位發生錯誤都應使余數不為0；2)不同位發生錯誤應當使余數不同；3)應滿足余數循環規律。國際上常用的幾種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)位數越高，檢錯能力就越強，由于CRC-32的可靠性，把CRC-32用于重要數據傳輸，在通信、計算機等領域運用十分廣泛。

1.1 串行算法[7]

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

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

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

1.2 查表法[8]

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

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

2 基于遞推法的CRC-32校驗碼并行改進算法

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

(1)

(2)

(3)

(4)

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

3 仿真驗證

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

基于第2章所使用的CRC-32特征多項式，類似上面的推算，我們可以分別得出并行輸入16位數據、8位數據、4位數據的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軟件環境下進行編譯后，設定同樣的初始值、輸入數據，如果得到的結果相同，則證明該算法無誤，反之說明算法不正確。

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

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

3.3.1占用空間對比

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

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

3.3.2計算速度對比

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

圖2 16位、8位、4位并行算法占用空間統計Fig.2 Numbers of slice registers of 16/8/4 bits parallel algorithm

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

3.3 仿真結果分析

根據3.1節、3.2節，將仿真數據匯總在表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(寄存器個數)處理時間t(時鐘周期)16位遞推并行算法4491068位遞推并行算法2251904位遞推并行算法68315串行算法322 107查表法2 09559

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

4 結論

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