王遠(yuǎn)，程明

（鄭州大學(xué) 信息工程學(xué)院，河南 鄭州 450001）

Xmodem協(xié)議是一種被廣泛使用的異步文件傳輸協(xié)議。標(biāo)準(zhǔn)主要由Xmodem和 1k-Xmodem兩種組成，Xmodem以128字節(jié)塊的形式傳輸數(shù)據(jù)，1k-Xmodem字節(jié)塊為1k即1 024字節(jié)，兩種標(biāo)準(zhǔn)都支持一般校驗(yàn)和、CRC兩種校驗(yàn)方式。在傳輸數(shù)據(jù)時(shí)，數(shù)據(jù)包出錯(cuò)，則支持重傳（一般支持 10次）。Xmodem的CRC校驗(yàn)需要對(duì)128字節(jié)（或1 024字節(jié)）數(shù)據(jù)包進(jìn)行整體校驗(yàn)。當(dāng)接收端接收到一個(gè)數(shù)據(jù)包后，如果校驗(yàn)正確，則回送一個(gè)確認(rèn)字符。如果錯(cuò)誤則回送一個(gè)否認(rèn)字符，等待發(fā)送端重發(fā)。對(duì)數(shù)據(jù)包的校驗(yàn)時(shí)間直接影響了Xmodem協(xié)議的數(shù)據(jù)傳輸效率。

數(shù)據(jù)傳輸過(guò)程中的差錯(cuò)檢查方法有很多，常用的有奇偶校驗(yàn)、循環(huán)冗余校驗(yàn)碼（Cyclical Redundancy Check，縮寫(xiě)為CRC）等。奇偶校驗(yàn)一般適用于一個(gè)字節(jié)或一個(gè)字的數(shù)據(jù)校驗(yàn)，CRC不僅適合單個(gè)字節(jié)的校驗(yàn)還適用于數(shù)據(jù)包數(shù)據(jù)的校驗(yàn)。在進(jìn)行大量數(shù)據(jù)傳輸?shù)膽?yīng)用中，CRC必不可少。如Xmodem協(xié)議，HEX文件，RFID協(xié)議，USB通信協(xié)議等，都需要進(jìn)行CRC校驗(yàn)。實(shí)踐證明，CRC得到了越來(lái)越廣范的應(yīng)用。

1 CRC算法原理簡(jiǎn)介

CRC校驗(yàn)的基本思路是利用線性碼原理，對(duì)需要進(jìn)行傳輸?shù)膋位二進(jìn)制數(shù)左移r位，右邊空出的r位補(bǔ)0，這r個(gè)0的位置即CRC碼的位置。通過(guò)以上的k+r位數(shù)據(jù)對(duì)生成多項(xiàng)式取余，所得余數(shù)即為CRC效驗(yàn)碼。

傳輸時(shí)在原始的k位二進(jìn)制數(shù)后加上r位CRC碼一起發(fā)送出去。接收端將接收到的k+r位數(shù)據(jù)對(duì)生成多項(xiàng)式取余，若余數(shù)為0，說(shuō)明傳輸數(shù)據(jù)正確，否則不正確。

下面具體說(shuō)明CRC校驗(yàn)的實(shí)現(xiàn)原理。

設(shè)欲傳送的數(shù)據(jù)為k位二進(jìn)制數(shù)，用M（X）表示，

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

將乘得的結(jié)果 M（x）·xr去模 2除以生成多項(xiàng)式 G（x）。

最后所得余數(shù)R（x）即為所求CRC碼。余數(shù)多項(xiàng)式R（x）可表示為：

最終所要傳輸?shù)臄?shù)據(jù)為：

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

圖1是典型電路，生成多項(xiàng)式G（x）對(duì)應(yīng)位為1時(shí)，D觸發(fā)器的輸入端就接到異或門(mén)的輸出端，為0時(shí)，接到上一級(jí)觸發(fā)器的輸出端，可省去異或門(mén)。所以生成多項(xiàng)式固定的情況下，此圖可以大為簡(jiǎn)化。

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

實(shí)際應(yīng)用中有一些標(biāo)準(zhǔn)的生成多項(xiàng)式，如下：

CRC8：多項(xiàng)式是X8+X5+X4+1，對(duì)應(yīng)的數(shù)字是0x131。

CRC12：多項(xiàng)式是X12+X11+X3+X2+1，對(duì)應(yīng)的數(shù)字是0x180D。

CCITT CRC16：多項(xiàng)式是 X16+X12+X5+1，對(duì)應(yīng)的數(shù)字是0x11021。

ANSI CRC16：多項(xiàng)式是 X16+X15+X2+1，對(duì)應(yīng)的數(shù)字是0x18005。

CRC32：多項(xiàng)式是 X32+X26+X23+X22+X16+X12+X11+X10+X8+X7+X5+X4+X2+X1+1，對(duì)應(yīng)數(shù)字是 0x104C11DB7。

在Xmodem協(xié)議中，生成多項(xiàng)式用的就是CCITT CRC16標(biāo)準(zhǔn)，其值為X16+X12+X5+1，對(duì)應(yīng)的數(shù)是0x11021。所以其CRC硬件電路可簡(jiǎn)化為圖2所示。

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

1）先通過(guò)CR端將觸發(fā)器清零，并將要進(jìn)行校驗(yàn)數(shù)據(jù)的高16位（2字節(jié)）移入16級(jí)的觸發(fā)器中。由于觸發(fā)器已被清零，所以在移入16位數(shù)據(jù)時(shí)數(shù)據(jù)流中的高16位不會(huì)發(fā)生改變。

圖2 CCITT CRC16的LFSR實(shí)現(xiàn)電路Fig.2 CCITT CRC16 LFSR circuit

2）數(shù)據(jù)流繼續(xù)移入觸發(fā)器，r15級(jí)觸發(fā)器移出值為“0”時(shí)，不進(jìn)行模2運(yùn)算，只是右移一位；若為“1”時(shí)，則進(jìn)行模2運(yùn)算后再右移一位。

3）數(shù)據(jù)流M（x）全部移入觸發(fā)器后，還要再繼續(xù)移入16個(gè)“0”后，該組數(shù)據(jù)的CRC計(jì)算才結(jié)束。

上述電路的設(shè)計(jì)思路完全采用了一般的模2除法的運(yùn)算過(guò)程。其最大的缺點(diǎn)是在數(shù)據(jù)流M（x）結(jié)束后還需要連續(xù)輸入16個(gè)“0”，再計(jì)算16次后，觸發(fā)器的值才是 CRC校驗(yàn)碼，增加了16個(gè)時(shí)鐘延時(shí)。

2 CRC并行計(jì)算及實(shí)現(xiàn)

在Xmodem協(xié)議中，每個(gè)數(shù)據(jù)包是128個(gè)字節(jié)（1 024位），當(dāng)用圖2實(shí)現(xiàn)時(shí)，就需要1 040（1 024+16）個(gè)周期才能把CRC給算出來(lái)（或是計(jì)算收到的數(shù)據(jù)是否正確）。為了提高起實(shí)時(shí)性，本文采用一種并行計(jì)算方法及硬件實(shí)現(xiàn)方案。

由于Xmodem協(xié)議是以字節(jié)傳送得，以下主要敘述8位的CRC并行計(jì)算。如圖1所示，各觸發(fā)器的狀態(tài)即CRC余數(shù)值，當(dāng)進(jìn)行串行運(yùn)算時(shí)，當(dāng)前的CRC余數(shù)值只與信息碼的前一位的輸入值和前一狀態(tài)的余數(shù)值有關(guān)。若進(jìn)行并行運(yùn)算，如8位并行運(yùn)算，即8位信息碼同時(shí)輸入并行運(yùn)算電路所產(chǎn)生的CRC余數(shù)與串行運(yùn)算時(shí)連續(xù)8位信息碼相繼輸入串行運(yùn)算電路所產(chǎn)生的CRC余數(shù)相同。由此產(chǎn)生出CRC并行計(jì)算方法。其計(jì)算過(guò)程如下：

類似的可推導(dǎo)出其他各項(xiàng)：

根據(jù)上述邏輯關(guān)系很容易直接實(shí)現(xiàn)8位并行CCITTCRC16模式的硬件運(yùn)算電路[3]。如圖3所示。

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

3 多字節(jié)CRC算法實(shí)現(xiàn)

Xmodem協(xié)議是以128字節(jié)或1 k字節(jié)做為數(shù)據(jù)包發(fā)送的，要完成協(xié)議就需要128個(gè)（或1024個(gè)）上面的8位并行CRC電路，這樣所需的邏輯資源就會(huì)很多，因?yàn)閿?shù)據(jù)包是以字節(jié)為最小單位發(fā)送的，下面就以字節(jié)為單位分析多字節(jié)數(shù)據(jù)包CRC算法的實(shí)現(xiàn)。設(shè)數(shù)據(jù)包有n個(gè)字節(jié)，計(jì)為[Dn，Dn-1，Dn-2，…，D3，D2，D1]。

其實(shí)現(xiàn)方法概括為如下幾步[4]：

1）取第一個(gè)字節(jié)Dn，計(jì)算出CRC碼。將CRC碼的高8位與Dn-1進(jìn)行模2運(yùn)算，其結(jié)果為新的Dn-1，低8位與Dn-2進(jìn)行模2運(yùn)算，其結(jié)果為新的Dn-2。至此數(shù)據(jù)包就成為[Dn-1，Dn-2，…，D2，D1]。

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

3）依次類推，直到只剩下兩個(gè)字節(jié)[D2，D1]為止，此時(shí)在這兩個(gè)字節(jié)后補(bǔ)兩個(gè)字節(jié)的 0，即對(duì)[D2，D1，0，0]按上面的方法計(jì)算余式，當(dāng)剩下最后兩個(gè)字節(jié)時(shí)[C2，C1]，此兩個(gè)字節(jié)就是最終的CRC碼。

用這種方法就可以用較少的邏輯資源實(shí)現(xiàn)多字節(jié)的CRC算法。雖然在最后要補(bǔ)兩個(gè)字節(jié)0，增加了兩次運(yùn)算，但是每次的運(yùn)算卻是并行的，其運(yùn)算時(shí)間只與觸發(fā)器的傳遞時(shí)間有關(guān)。在時(shí)間的消耗上遠(yuǎn)遠(yuǎn)低于LFSR電路。與完全并行電路比雖然多了兩次的運(yùn)算時(shí)間，但所需邏輯資源卻大大節(jié)省，對(duì)于字節(jié)數(shù)比較多得情況，優(yōu)勢(shì)就更能明顯。

4 并行算法的VHDL實(shí)現(xiàn)

以上研究在Altera公司的cyclone系列的FPGA芯片EP1C3 T144上驗(yàn)證并實(shí)現(xiàn)。以下是字節(jié)CRC并行算法的VHDL主要代碼。

5 結(jié)束語(yǔ)

本文通過(guò)CRC計(jì)算原理的分析，用按字節(jié)的并行計(jì)算方法對(duì)CCITT CRC16校驗(yàn)碼進(jìn)行了設(shè)計(jì)，并提出了一種推導(dǎo)和實(shí)現(xiàn)CRC并行計(jì)算的通用方法，以及數(shù)據(jù)包CRC算法的解決方案。在此基礎(chǔ)上用FPGA實(shí)現(xiàn)了Xmodem協(xié)議的CRC校驗(yàn)。通過(guò)試驗(yàn)得出多字節(jié)循環(huán)并行CRC算法能夠滿足高速實(shí)時(shí)性要求。

[1]李永忠.通用并行CRC計(jì)算原理及其硬件實(shí)現(xiàn)方法 [J].西北民族學(xué)院學(xué)報(bào):自然科學(xué)版，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編碼算法研究與實(shí)現(xiàn)[J].西北大學(xué)學(xué)報(bào):自然科學(xué)版，2006，36（6）:895-898.

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

[3]朱榮華.一種CRC并行計(jì)算原理及實(shí)現(xiàn)方法[J].電子學(xué)報(bào)，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]季上滿，李偉，沈科杰，等.改進(jìn)CRC算法及其單片機(jī)實(shí)現(xiàn)[J].工業(yè)控制計(jì)算機(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].北京:清華大學(xué)出版社，2004.

[6]王新梅，肖國(guó)鎮(zhèn).糾錯(cuò)碼——原理與方法[M].西安:西安電子科技大學(xué)出版社，2003.