Xmodem協議中CRC算法的FPAG實現

王遠，程明

（鄭州大學 信息工程學院，河南 鄭州 450001）

Xmodem協議是一種被廣泛使用的異步文件傳輸協議。標準主要由Xmodem和 1k-Xmodem兩種組成，Xmodem以128字節塊的形式傳輸數據，1k-Xmodem字節塊為1k即1 024字節，兩種標準都支持一般校驗和、CRC兩種校驗方式。在傳輸數據時，數據包出錯，則支持重傳（一般支持 10次）。Xmodem的CRC校驗需要對128字節（或1 024字節）數據包進行整體校驗。當接收端接收到一個數據包后，如果校驗正確，則回送一個確認字符。如果錯誤則回送一個否認字符，等待發送端重發。對數據包的校驗時間直接影響了Xmodem協議的數據傳輸效率。

數據傳輸過程中的差錯檢查方法有很多，常用的有奇偶校驗、循環冗余校驗碼（Cyclical Redundancy Check，縮寫為CRC）等。奇偶校驗一般適用于一個字節或一個字的數據校驗，CRC不僅適合單個字節的校驗還適用于數據包數據的校驗。在進行大量數據傳輸的應用中，CRC必不可少。如Xmodem協議，HEX文件，RFID協議，USB通信協議等，都需要進行CRC校驗。實踐證明，CRC得到了越來越廣范的應用。

1 CRC算法原理簡介

CRC校驗的基本思路是利用線性碼原理，對需要進行傳輸的k位二進制數左移r位，右邊空出的r位補0，這r個0的位置即CRC碼的位置。通過以上的k+r位數據對生成多項式取余，所得余數即為CRC效驗碼。

傳輸時在原始的k位二進制數后加上r位CRC碼一起發送出去。接收端將接收到的k+r位數據對生成多項式取余，若余數為0，說明傳輸數據正確，否則不正確。

下面具體說明CRC校驗的實現原理。

設欲傳送的數據為k位二進制數，用M（X）表示，

將此數據序列左移r位，即乘以xr，其中r為生成多項式G（x）的最高次冪。

將乘得的結果 M（x）·xr去模 2除以生成多項式 G（x）。

最后所得余數R（x）即為所求CRC碼。余數多項式R（x）可表示為：

最終所要傳輸的數據為：

從M到M′的過程就是CRC的編碼過程。通過以上公式，可以采用典型的LFSR（線性反饋移位寄存器組）硬件電路來完成[1]，見圖 1。

圖1是典型電路，生成多項式G（x）對應位為1時，D觸發器的輸入端就接到異或門的輸出端，為0時，接到上一級觸發器的輸出端，可省去異或門。所以生成多項式固定的情況下，此圖可以大為簡化。

圖1 線性反饋移位寄存器組LFSRFig.1 Linear feedback shift register group LFSR

實際應用中有一些標準的生成多項式，如下：

CRC8：多項式是X8+X5+X4+1，對應的數字是0x131。

CRC12：多項式是X12+X11+X3+X2+1，對應的數字是0x180D。

CCITT CRC16：多項式是 X16+X12+X5+1，對應的數字是0x11021。

ANSI CRC16：多項式是 X16+X15+X2+1，對應的數字是0x18005。

CRC32：多項式是 X32+X26+X23+X22+X16+X12+X11+X10+X8+X7+X5+X4+X2+X1+1，對應數字是 0x104C11DB7。

在Xmodem協議中，生成多項式用的就是CCITT CRC16標準，其值為X16+X12+X5+1，對應的數是0x11021。所以其CRC硬件電路可簡化為圖2所示。

圖2電路的工作過程概括如下幾步[2]：

1）先通過CR端將觸發器清零，并將要進行校驗數據的高16位（2字節）移入16級的觸發器中。由于觸發器已被清零，所以在移入16位數據時數據流中的高16位不會發生改變。

圖2 CCITT CRC16的LFSR實現電路Fig.2 CCITT CRC16 LFSR circuit

2）數據流繼續移入觸發器，r15級觸發器移出值為“0”時，不進行模2運算，只是右移一位；若為“1”時，則進行模2運算后再右移一位。

3）數據流M（x）全部移入觸發器后，還要再繼續移入16個“0”后，該組數據的CRC計算才結束。

上述電路的設計思路完全采用了一般的模2除法的運算過程。其最大的缺點是在數據流M（x）結束后還需要連續輸入16個“0”，再計算16次后，觸發器的值才是 CRC校驗碼，增加了16個時鐘延時。

2 CRC并行計算及實現

在Xmodem協議中，每個數據包是128個字節（1 024位），當用圖2實現時，就需要1 040（1 024+16）個周期才能把CRC給算出來（或是計算收到的數據是否正確）。為了提高起實時性，本文采用一種并行計算方法及硬件實現方案。

由于Xmodem協議是以字節傳送得，以下主要敘述8位的CRC并行計算。如圖1所示，各觸發器的狀態即CRC余數值，當進行串行運算時，當前的CRC余數值只與信息碼的前一位的輸入值和前一狀態的余數值有關。若進行并行運算，如8位并行運算，即8位信息碼同時輸入并行運算電路所產生的CRC余數與串行運算時連續8位信息碼相繼輸入串行運算電路所產生的CRC余數相同。由此產生出CRC并行計算方法。其計算過程如下：

類似的可推導出其他各項：

根據上述邏輯關系很容易直接實現8位并行CCITTCRC16模式的硬件運算電路[3]。如圖3所示。

圖3 8位并行CCITT CRC16硬件電路Fig.3 8-bit parallel CCITT CRC16 hardware circuit

3 多字節CRC算法實現

Xmodem協議是以128字節或1 k字節做為數據包發送的，要完成協議就需要128個（或1024個）上面的8位并行CRC電路，這樣所需的邏輯資源就會很多，因為數據包是以字節為最小單位發送的，下面就以字節為單位分析多字節數據包CRC算法的實現。設數據包有n個字節，計為[Dn，Dn-1，Dn-2，…，D3，D2，D1]。

其實現方法概括為如下幾步[4]：

1）取第一個字節Dn，計算出CRC碼。將CRC碼的高8位與Dn-1進行模2運算，其結果為新的Dn-1，低8位與Dn-2進行模2運算，其結果為新的Dn-2。至此數據包就成為[Dn-1，Dn-2，…，D2，D1]。

2）再取此數據包的第一個字節Dn-1，計算出CRC碼。將CRC碼的高8位與Dn-2進行模2運算，其結果為新的Dn-2，低8位與Dn-3進行模2運算，其結果為新的Dn-3。至此數據包就成為[Dn-2，Dn-3，…，D2，D1]。

3）依次類推，直到只剩下兩個字節[D2，D1]為止，此時在這兩個字節后補兩個字節的 0，即對[D2，D1，0，0]按上面的方法計算余式，當剩下最后兩個字節時[C2，C1]，此兩個字節就是最終的CRC碼。

用這種方法就可以用較少的邏輯資源實現多字節的CRC算法。雖然在最后要補兩個字節0，增加了兩次運算，但是每次的運算卻是并行的，其運算時間只與觸發器的傳遞時間有關。在時間的消耗上遠遠低于LFSR電路。與完全并行電路比雖然多了兩次的運算時間，但所需邏輯資源卻大大節省，對于字節數比較多得情況，優勢就更能明顯。

4 并行算法的VHDL實現

以上研究在Altera公司的cyclone系列的FPGA芯片EP1C3 T144上驗證并實現。以下是字節CRC并行算法的VHDL主要代碼。

5 結束語

本文通過CRC計算原理的分析，用按字節的并行計算方法對CCITT CRC16校驗碼進行了設計，并提出了一種推導和實現CRC并行計算的通用方法，以及數據包CRC算法的解決方案。在此基礎上用FPGA實現了Xmodem協議的CRC校驗。通過試驗得出多字節循環并行CRC算法能夠滿足高速實時性要求。

[1]李永忠.通用并行CRC計算原理及其硬件實現方法 [J].西北民族學院學報:自然科學版，2002，23（43）:33-37.

LI You-zhong.The generic parallel CRC calculation principle and its hardware implementation[J].Northwest Minorities University（Natural Science） 2002，23（43）:33-37.

[2]李宥謀，房鼎益.CRC編碼算法研究與實現[J].西北大學學報:自然科學版，2006，36（6）:895-898.

LI You-mou，FANG Ding-yi.CRC coding algorithm research and Realization[J].Journal of Northwest University：Natural Science Edition，2006，36（6）:895-898.

[3]朱榮華.一種CRC并行計算原理及實現方法[J].電子學報，1999，27（4）：144-146.

ZHU Rong-hua.The Principle and Implementation of a Parallel CRC Computing[J].Acta Electronica Sinica，1999，27（4）：144-146.

[4]季上滿，李偉，沈科杰，等.改進CRC算法及其單片機實現[J].工業控制計算機，2009，22（11）:76-77.

JI Shang-man， LI Wei， SHEN Ke-jie，et al.Improved CRC Arithmetic and Implementation by SCM[J].Industrial Control Computer，2009，22（11）:76-77.

[5]曹雪紅，張宗橙.信息論與編碼[M].北京:清華大學出版社，2004.

[6]王新梅，肖國鎮.糾錯碼——原理與方法[M].西安:西安電子科技大學出版社，2003.