何秉姣，汪 紅

(中南民族大學(xué)計(jì)算機(jī)科學(xué)學(xué)院，武漢430074)

通信系統(tǒng)遵循公認(rèn)的通信協(xié)議以數(shù)據(jù)包等形式進(jìn)行數(shù)據(jù)交換，實(shí)現(xiàn)資源共享.例如通信系統(tǒng)中有主機(jī)A和主機(jī)B，主機(jī)A將數(shù)據(jù)傳送給主機(jī)B前，兩者必須建立數(shù)據(jù)通信線路，保證高效準(zhǔn)確的數(shù)據(jù)通信.正常情況數(shù)據(jù)包P與數(shù)據(jù)包P'一致，當(dāng)通信受到干擾時(shí)，數(shù)據(jù)包P與數(shù)據(jù)包P'不一致，即數(shù)據(jù)包P'出現(xiàn)差錯(cuò)，必須予以及時(shí)處理.循環(huán)冗余校驗(yàn)碼CRC(Cyclic Redundancy Check)在數(shù)據(jù)通信線路中能很好地校驗(yàn)所傳輸信息的正誤［1，2］.

1 CRC串行算法

1.1 數(shù)據(jù)包格式

主機(jī)A將數(shù)據(jù)傳送給主機(jī)B時(shí)，主機(jī)A先將較長(zhǎng)報(bào)文劃分成一個(gè)個(gè)小的等長(zhǎng)的數(shù)據(jù)段，在每個(gè)數(shù)據(jù)段前加上首部，末尾加上校驗(yàn)碼，就構(gòu)成一個(gè)數(shù)據(jù)包，傳輸?shù)酵ㄐ啪€路上.數(shù)據(jù)包到達(dá)主機(jī)B后，主機(jī)B能從數(shù)據(jù)包中得到所需要的各種控制信息和傳輸?shù)挠行畔?數(shù)據(jù)包的格式如下.

SOH 序號(hào) 長(zhǎng)度 數(shù)據(jù) CRC校驗(yàn)碼

其中，SOH是包頭，序號(hào)是報(bào)文組序，長(zhǎng)度是本數(shù)據(jù)包中數(shù)據(jù)的字節(jié)數(shù)，數(shù)據(jù)是傳輸?shù)挠行畔?，CRC校驗(yàn)碼是通過(guò)CRC算法計(jì)算出來(lái)的本數(shù)據(jù)包中數(shù)據(jù)的CRC碼.

在報(bào)文的數(shù)據(jù)包傳輸協(xié)議中，主機(jī)A算出CRC校驗(yàn)碼，并拼裝在數(shù)據(jù)包尾部.主機(jī)B校驗(yàn)器接收到數(shù)據(jù)包后，用同樣的CRC算法算得新的CRC碼，并與接收到的CRC碼進(jìn)行比較.若兩組CRC碼值相等，則接著傳輸下一個(gè)數(shù)據(jù)包，否則說(shuō)明傳輸中有差錯(cuò)，給予有效處理.

1.2 CRC16串行算法及其實(shí)現(xiàn)

主機(jī)A的CRC編碼器將傳送的32bit數(shù)據(jù)序列D={d31，d30，…，d1，d0}看成是系數(shù)為 0 或 1 的多項(xiàng)式D(x)=d31x31+d30x30+…+d1x+d0，用預(yù)定的生成多項(xiàng)式G(x)=x16+x12+x5+1，將D按照模運(yùn)算法則產(chǎn)生一個(gè)長(zhǎng)度為16bit的兩字節(jié)序列R={r15，r14，…，r1，r0}，R 即為 D 的 CRC 碼，計(jì)算 R(x)的步驟如下.

(i)形成被除數(shù)方程:

(ii)構(gòu)造余數(shù)R(x)方程為:

其中Q(x)為多項(xiàng)式運(yùn)算的商，R(x)即為數(shù)據(jù)序列D的余式多項(xiàng)式.

(iii)M多項(xiàng)式方程為:

主機(jī)B的校驗(yàn)碼將收到的M'(x)采用以上同樣的方式計(jì)算出余數(shù)R'，與R比較，根據(jù)結(jié)果是否為零來(lái)判斷傳輸過(guò)程是否無(wú)誤.

其實(shí)現(xiàn)方法包括軟硬兩類(lèi)方法.一般采用硬件方法實(shí)現(xiàn).以往CRC硬件實(shí)現(xiàn)一般采用串行移位異或算法，其電路結(jié)構(gòu)如圖1所示.

圖1 CRC16串行移位結(jié)構(gòu)Fig.1 Serial shift structure of CRC16

圖1中包括16個(gè)保存中間結(jié)果的D觸發(fā)器和15個(gè)異或門(mén)，在48個(gè)時(shí)鐘里Din端輸入數(shù)據(jù)序列x16·D(x)48位，前32位是原始數(shù)據(jù)，后16位是0.D 觸發(fā)器輸出 R15，R14，…，R1，R0就是要求的 CRC值［3-5］.數(shù)位越長(zhǎng)，求CRC碼時(shí)間越長(zhǎng)，這種通過(guò)時(shí)間換空間循環(huán)逐位實(shí)現(xiàn)的算法難以滿(mǎn)足日益高速的數(shù)據(jù)通信需要.為了適應(yīng)現(xiàn)代通信高速傳輸數(shù)據(jù)，本文設(shè)計(jì)了一種新的并行輸入CRC16校驗(yàn)算法.

2 通信系統(tǒng)中CRC16并行算法及其實(shí)現(xiàn)

基于 R(x)算法，用數(shù)據(jù)為 D(x)=11010111011，G'(x)=10011列豎式模2除如圖2所示.

圖2 模2除Fig.2 Division of mode 2

據(jù)圖2，余數(shù)最高位為1，則余數(shù)與G'異或再移位，否則與零異或再移位，由于與零異或等于不做異或運(yùn)算，另外，由于余數(shù)最高位為零的情況至少占一半，那么設(shè)計(jì)新算法可省去至少一半的異或運(yùn)算，當(dāng)余數(shù)最高位為零時(shí)，直接移位，這加快CRC碼的形成.

先設(shè)計(jì)第i位處理方法.令余數(shù)最高位R高，對(duì)應(yīng)除數(shù)Gi，時(shí)鐘到來(lái)前第i－1位余數(shù)的現(xiàn)態(tài)Ri－1，時(shí)鐘到來(lái)后第i位次態(tài)Rn+1i，可列出其邏輯關(guān)系如表1所示.

表1 第i位次態(tài)邏輯關(guān)系Tab.1 Logical relationship of next state the i bit

根據(jù)表1，用卡諾圖化簡(jiǎn)法得第i位的次態(tài)方程為:

據(jù)此推導(dǎo)出通信系統(tǒng)中CRC16的次態(tài)方程組為:

上述邏輯關(guān)系表明當(dāng)R最高位為1時(shí)，Rn+1i是異或求得，否則直接移位;CRC的值只與當(dāng)時(shí)輸入的16位生成表達(dá)式G和電路現(xiàn)態(tài)Ri有關(guān).因此采用層次結(jié)構(gòu)模式可實(shí)現(xiàn)通信系統(tǒng)中CRC16并行算法.

基于公式(4)設(shè)計(jì)的CRC16模塊被重用17次，由公式(4)推導(dǎo)式設(shè)計(jì)的CRC165被重用3次，再組合成圖4實(shí)現(xiàn)通信系統(tǒng)中CRC16校驗(yàn)編碼電路，系統(tǒng)層次設(shè)計(jì)模式能實(shí)現(xiàn)模塊化和元件重用.根據(jù)實(shí)際需要用CRC165可以組裝成任意生成多項(xiàng)式，也能并行處理任意長(zhǎng)度的數(shù)據(jù)序列.

3 CRC16并行算法仿真結(jié)果分析

在硬件系統(tǒng)設(shè)計(jì)中，主要進(jìn)行3次仿真:行為仿真、RTL仿真和門(mén)級(jí)仿真.一般前兩種為功能仿真，后一種為時(shí)序仿真.功能仿真驗(yàn)證設(shè)計(jì)模塊的邏輯功能，時(shí)序仿真驗(yàn)證設(shè)計(jì)模塊的時(shí)序關(guān)系.對(duì)于CRC模塊的仿真采用的是功能仿真，主要是驗(yàn)證該模塊是否可以正常工作.

整個(gè)設(shè)計(jì)是在 Quartus 9.0 平臺(tái)下進(jìn)行［6，7］，設(shè)計(jì)輸入編譯后仿真.仿真目錄包含以下文件:輸入輸出、并行文件、配置文件等.主機(jī)A向主機(jī)B發(fā)送數(shù)據(jù)包前，用CRC1616編碼器模塊形成CRC碼.其仿真結(jié)果如圖3所示.

圖3 CRC16仿真波形圖Fig.3 Simulation waveform of CRC16

其中 D(x)=8D6F646Eh，G(x)=11021h，首先初始化8D6Fh，第一個(gè)時(shí)鐘上跳沿到來(lái)后R中的值依次為1ADEh，15FFh，2BFF，…，1962h 等直到 CRC 碼32C4h的形成，最后M(x)=8D6F646E32C4h發(fā)往通信網(wǎng)絡(luò).主機(jī)B的校驗(yàn)器也采用同樣的過(guò)程計(jì)算CRC碼，如果等于32C4h，則數(shù)據(jù)包正確，否則反饋重發(fā).在Alterra的EP1S25F672C6芯片下通過(guò)綜合與仿真驗(yàn)證，CRC模塊的最大時(shí)鐘頻率Fmax達(dá)到425.56MHz，能夠滿(mǎn)足高速通信系統(tǒng)的需要.

4 結(jié)語(yǔ)

本文通過(guò)分析CRC串行算法，得出了CRC并行實(shí)現(xiàn)的推理公式，與已有的方法［8］相比具有以下3個(gè)優(yōu)點(diǎn):(1)理論推導(dǎo)與現(xiàn)有的方法不同，本文推導(dǎo)過(guò)程清楚明了;(2)CRC碼編碼器模塊采用層次結(jié)構(gòu)，在硬件結(jié)構(gòu)上很容易實(shí)現(xiàn)任意長(zhǎng)度CRC碼的形成，可適用于任意長(zhǎng)度的生成多項(xiàng)式和并行處理位寬，即并行處理位寬可以小于、等于或大于CRC16的階數(shù)16，而目前公開(kāi)發(fā)表的文獻(xiàn)多集中在并行處理小于、等于生成多項(xiàng)式的階數(shù)的情況下進(jìn)行討論;(3)充分利用了數(shù)據(jù)0信息，減少至少一半的異或運(yùn)算，加快了CRC的形成，電路綜合結(jié)果具有很好的性能.該系統(tǒng)自成一體，用戶(hù)只需對(duì)接口進(jìn)行操作.因此，它既可獨(dú)立使用，亦可配合其他系統(tǒng)作為其校驗(yàn)?zāi)K使用.

［1］王新梅，馬文平，武傳坤.糾錯(cuò)密碼理論［M］.北京:人民郵電出版社，2001:48-73.

［2］Campobello G，Patane G.Parallel CRC realization［J］.IEEE Trans-Action on Computers，2003，52(10):1312-1319.

［3］Pei Tongbi，Zukowski C .High-speed parallel CRC circuits in VLSI［J］.IEEE Transations on Communications 1992，40(4):653-657.

［4］Lrvin D R.Cyclic redundancy checks with factorable generator［J］.IEEE.Proc-Commun，2003，150(1):179-191.

［5］何秉姣，劉 科.SEC-DED海明校驗(yàn)碼算法研究及其FPGA實(shí)現(xiàn)［J］.中南民族大學(xué)學(xué)報(bào):自然科學(xué)版，2012(3):89-92.

［6］俞建新，王 建，宋健建.嵌入式系統(tǒng)基礎(chǔ)教程［M］.北京:機(jī)械工業(yè)出版社，2009:23-30.

［7］潘 松，黃繼業(yè).EDA技術(shù)與 VHDL［M］.3版.北京:清華大學(xué)出版社，2010:182-210.

［8］Robert H M.糾錯(cuò)編碼的藝術(shù)［M］.2版.張立軍，譯.北京:北京交通大學(xué)出版社，2007:8-32.