何秉姣，汪 紅

(中南民族大學計算機科學學院，武漢430074)

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

1 CRC串行算法

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

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

SOH 序號 長度 數(shù)據(jù) CRC校驗碼

其中，SOH是包頭，序號是報文組序，長度是本數(shù)據(jù)包中數(shù)據(jù)的字節(jié)數(shù)，數(shù)據(jù)是傳輸?shù)挠行畔?，CRC校驗碼是通過CRC算法計算出來的本數(shù)據(jù)包中數(shù)據(jù)的CRC碼.

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

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

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

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

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

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

(iii)M多項式方程為:

主機B的校驗碼將收到的M'(x)采用以上同樣的方式計算出余數(shù)R'，與R比較，根據(jù)結果是否為零來判斷傳輸過程是否無誤.

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

圖1 CRC16串行移位結構Fig.1 Serial shift structure of CRC16

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

2 通信系統(tǒng)中CRC16并行算法及其實現(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'異或再移位，否則與零異或再移位，由于與零異或等于不做異或運算，另外，由于余數(shù)最高位為零的情況至少占一半，那么設計新算法可省去至少一半的異或運算，當余數(shù)最高位為零時，直接移位，這加快CRC碼的形成.

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

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

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

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

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

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

3 CRC16并行算法仿真結果分析

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

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

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

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

4 結語

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

［1］王新梅，馬文平，武傳坤.糾錯密碼理論［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海明校驗碼算法研究及其FPGA實現(xiàn)［J］.中南民族大學學報:自然科學版，2012(3):89-92.

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

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

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