一種并行數(shù)據(jù)輸入的循環(huán)冗余校驗(yàn)碼算法設(shè)計(jì)

1、計(jì)算機(jī)工程與應(yīng)用2006.27博士論壇!"!"!"!"隨著計(jì)算機(jī)技術(shù)的不斷發(fā)展,數(shù)據(jù)通訊的應(yīng)用越來越廣泛。在數(shù)據(jù)傳輸過程中,由于傳輸距離、突發(fā)的干擾信號(hào)等許多可能出現(xiàn)的因素影響,數(shù)據(jù)在傳輸過程中常會(huì)發(fā)生無(wú)法預(yù)測(cè)的錯(cuò)誤。為防止這些錯(cuò)誤所帶來的影響,一般在通訊時(shí)采取數(shù)據(jù)校驗(yàn)的辦法,而循環(huán)冗余碼校驗(yàn)(Cyclical Redundancy Check ,簡(jiǎn)稱CRC 是最常用的一種校驗(yàn)方法1,2。本文討論了一種利于硬件實(shí)現(xiàn)的并行數(shù)據(jù)輸入的CRC 算法及其實(shí)現(xiàn)方法。并且采用本文提出的算法,設(shè)計(jì)實(shí)現(xiàn)了CRC-6運(yùn)算模塊,在測(cè)試中達(dá)到600Mbps 的峰值數(shù)據(jù)吞吐率。

2、1CRC 生成的代數(shù)描述CRC 校驗(yàn)的基本原理是采用線性編碼理論,其數(shù)學(xué)基礎(chǔ)是多項(xiàng)式代數(shù)。在運(yùn)算中,使用多項(xiàng)式來表示要處理的數(shù)據(jù),其中每一組二進(jìn)制碼均被看作多項(xiàng)式的系數(shù)1,3。例如,二進(jìn)制碼110011可以使用一個(gè)6次多項(xiàng)式A (x 表示,具體表示方法如式(1所示。A (x =1x 5+1x 4+0x 3+0x 2+1x 1+1x 0(1公式(2為生成r 位CRC 校驗(yàn)碼的生成基本表達(dá)式。為了便于實(shí)現(xiàn),規(guī)定算法中的加法采用的是無(wú)進(jìn)位模2加法。B (x x r G (x =Q (x +R (x G (x (2在公式(2中,B (x 表示發(fā)送端要發(fā)送的一組k 位的二進(jìn)制碼序列。G (x 為生成多項(xiàng)

3、式,在CRC 碼的計(jì)算中,將要發(fā)送的數(shù)據(jù)B (x 左移r 位,與生成多項(xiàng)式G (x 做除法運(yùn)算。在公式(2的左項(xiàng)中,Q (x 代表除法操作后的整數(shù)商部分,而R (x 代表的是除法操作后的余數(shù)部分。其中R (x 即為需要求得的r 位CRC 校驗(yàn)碼。在數(shù)據(jù)發(fā)送的時(shí)候,將r 位的校驗(yàn)碼R (x 附著在k 位的二進(jìn)制碼原始信息后面,生成發(fā)送序列T (x ,如式(3所示,并將生成的T (x 發(fā)送出去。T (x =B (x x r +R (x (3在接收端,通過除法運(yùn)算T (x /G (x ,計(jì)算并求其余數(shù),如果最終的余數(shù)為0則表示所發(fā)送的數(shù)據(jù)沒有差錯(cuò),否則認(rèn)為所發(fā)送的數(shù)據(jù)包含錯(cuò)誤3。CRC 通常分為以下

4、幾種標(biāo)準(zhǔn):CRC-8、CRC-16、CRC-CCITT 、CRC-32等4。但在一些嵌入式或者移動(dòng)計(jì)算環(huán)境中,通訊協(xié)議可能更多的是采用自定義的通訊格式,要生成的CRC 碼并非是常用的標(biāo)準(zhǔn)的8位16位的CRC 碼,例如需要生成一個(gè)7位的或者15位的CRC 校驗(yàn)碼。對(duì)于采用基于數(shù)字邏輯電路方式設(shè)計(jì)的CRC 生成模塊,同時(shí)要求并行輸入數(shù)據(jù)的情況下,并沒有一個(gè)通用的設(shè)計(jì)方法可以生成這些特定位數(shù)的CRC 模塊。下面介紹硬件實(shí)現(xiàn)CRC 算法的基本方法,基于串行移位寄存器的CRC 生成原理。一種并行數(shù)據(jù)輸入的循環(huán)冗余校驗(yàn)碼算法設(shè)計(jì)尹震宇趙海孫佩剛林愷羅玎玎(東北大學(xué)信息科學(xué)與工程學(xué)院,沈陽(yáng)110004摘要文

5、章首先介紹了CRC 的數(shù)學(xué)原理,繼而討論了一種利于硬件實(shí)現(xiàn)的并行數(shù)據(jù)輸入CRC 算法的推導(dǎo)方法及其實(shí)現(xiàn)方法。最后,采用該文提出的設(shè)計(jì)算法,使用VHDL 設(shè)計(jì)并實(shí)現(xiàn)了CRC-6運(yùn)算模塊,與其它算法實(shí)現(xiàn)的CRC 模塊相比,在使用的資源增加不大的情況下,可以獲得較高的性能。關(guān)鍵詞循環(huán)冗余碼校驗(yàn)多項(xiàng)式運(yùn)算線性編碼數(shù)據(jù)校驗(yàn)文章編號(hào)1002-8331-(200627-0001-02文獻(xiàn)標(biāo)識(shí)碼A中圖分類號(hào)TP302.7;TP316.2The Design of Cyclical Redundancy Check ArithmeticBased on Parallel Data InputYIN Zhen-y

6、u ZHAO Hai SUN Pei-gang LIN Kai LUO Ding-ding(School of Information Science &Engineering ,Northeastern University ,Shenyang 110004Abstract :In this paper ,the principle of Cyclical Redundancy Check (CRC is described.Furthermore ,the CRC arithmetic with the parallel data input structure is descri

7、bed.It can be easily implemented by using VLSI.Also ,in this paper ,a CRC-6module is designed and implemented by using VHDL as the example.The CRC module which is designed by using this method has high performance.Keywords :Cyclical Redundancy Check ,polynomial arithmetic ,linear coder ,data error c

8、heck基金項(xiàng)目:國(guó)家高技術(shù)研究發(fā)展計(jì)劃資助項(xiàng)目(編號(hào):2001AA415320;國(guó)家自然科學(xué)基金資助項(xiàng)目(編號(hào):69873007作者簡(jiǎn)介:尹震宇(1979-,男,博士研究生。趙海(1959-,男,教授,博士,博士生導(dǎo)師。12006.27計(jì)算機(jī)工程與應(yīng)用CRC0CRC1CRCr-2CRCr-1數(shù)據(jù)輸入D QR 0D QR 1DQR r-2D QR r-1G r-1G 2G 1圖1LFSR 邏輯原理圖CRC0D QR 0G 2G 1CRC1D QR 1CRC2D QR 2CRC3D QR 3CRC4D QR 4CRC5D QR 5數(shù)據(jù)輸入圖2CRC-6運(yùn)算的邏輯原理圖吞吐率峰值/Mbps 最大工

9、作頻率/MHz 使用的SliceCRC-6600150136LFSR 20020062表1本設(shè)計(jì)和LFSR 實(shí)現(xiàn)的CRC 性能比較2基于串行移位寄存器的CRC 實(shí)現(xiàn)由于CRC 計(jì)算公式中的加法采用的是無(wú)進(jìn)位的模2加法,因而,對(duì)于CRC 的實(shí)現(xiàn)上可以使用一個(gè)線性反饋的移位寄存器(LFSR 來實(shí)現(xiàn)57,其電路邏輯結(jié)構(gòu)圖如圖1所示。在圖1中,每一個(gè)鎖存器代表一個(gè)CRC 碼位,例如,要生成r 位的CRC 碼,整個(gè)邏輯電路中就要有R 0、R 1、R r-1一共r 個(gè)鎖存器。G i 為生成多項(xiàng)式G (x 的系數(shù),當(dāng)G (x 中的第i 位取1的時(shí)候,表示這個(gè)地方是個(gè)通路,將數(shù)據(jù)與R i 的輸出數(shù)據(jù)做異或運(yùn)算

10、;當(dāng)取0的時(shí)候,表示在R i 的輸出端不需要異或操作,R i 的輸出數(shù)據(jù)直接傳送給R i+1。下面以生成一個(gè)6位的CRC-6為例進(jìn)行分析,在這里,首先規(guī)定生成多項(xiàng)式G (x 為:G (x =x 6+x 2+x 1+1其中,圖2所示為其運(yùn)算的邏輯原理圖:從圖2中可以看出,要發(fā)送的n 位數(shù)據(jù)B (x ,在時(shí)鐘的驅(qū)動(dòng)下,每個(gè)時(shí)鐘將一位數(shù)據(jù)送入這個(gè)電路中,經(jīng)過n 個(gè)時(shí)鐘的處理,就可以在鎖存器中得到要求的CRC 碼。上面提到的方法在硬件上設(shè)計(jì)簡(jiǎn)單,但是此種方法實(shí)際上僅僅適用于串行數(shù)據(jù)進(jìn)行CRC 校驗(yàn)計(jì)算。由于每一位需要一個(gè)時(shí)鐘周期進(jìn)行移位和計(jì)算,這對(duì)于并行數(shù)據(jù)而言是不適合的。對(duì)于采用硬件方法進(jìn)行并行數(shù)據(jù)

11、輸入的CRC 校驗(yàn)計(jì)算也有很多解決方式,但對(duì)于一些“非標(biāo)準(zhǔn)”的CRC 校驗(yàn)沒有一種通用的方法。因而,需要通過CRC 的基本數(shù)學(xué)關(guān)系尋找實(shí)現(xiàn)的方法。3CRC 并行算法的實(shí)現(xiàn)下文將以4位并行輸入的CRC-6為例說明將串行CRC算法向并行CRC 算法的轉(zhuǎn)換過程。由CRC 串行運(yùn)算的邏輯結(jié)構(gòu)圖中可以得到公式(4、(5和(6。R (x =r-1a=0!r a x a(4R b =r-1a=0!r a ,b x a(5r a ,b =r a-1,b-1"(g a &(b b "r r-1,b-1(6這里,R b 表示的是在計(jì)算第b 位原始數(shù)據(jù)后,其CRC 的值。r a ,b 表

12、示R b 的第a 位寄存器的內(nèi)容。b b 表示要輸入的第b 位原始數(shù)據(jù)。在串行實(shí)現(xiàn)中可以推導(dǎo)出公式(7、(8:r 0.2b =r r-1.2b-1"b 2b(7r a-1.2b =r a-2.2b-1"(g a-1&(b 2b "r r-1.2b-1(8其中a-1=1,2,r-1。通過對(duì)其進(jìn)行并行化的擴(kuò)展,可以推導(dǎo)出并行輸入的CRC 計(jì)算公式為:r 0.2j+1=b 2j-2"r 2.2j-3(9r 1.2j+1=b 2j-1"b 2j-2"r 2.2j-3"r 3.2j-3(10r 2.2j+1=b 2j &quo

13、t;b 2j-1"b 2j-2"r 2.2j-3"r 3.2j-3"r 4.2j-3(11r 3.2j+1=b 2j+1"b 2j "b 2j-1"r 3.2j-3"r 4.2j-3"r 5.2j-3(12r 4.2j+1=b 2j+1"b 2j "r 0.2j-3"r 4.2j-3"r 5.2j-3(13r 5.2j+1=b 2j+1"r 1.2j-3"r 5.2j-3(14上述公式將CRC 計(jì)算的數(shù)據(jù)輸入由按位串行輸入的變換為4位并行輸入,其

14、輸出CRC 位數(shù)為6位。利用公式(9公式(14,就可以實(shí)現(xiàn)一個(gè)并行數(shù)據(jù)輸入的CRC 模塊,下面是使用VHDL 語(yǔ)言的CRC 生成電路描述:function CRC6(Data :std_logic_vector (3downto 0;CIN :std_logic_vector (5downto 0return std_logic_vector isvariable B :std_logic_vector (3downto 0;variable R :std_logic_vector (5downto 0;variable CRC :std_logic_vector (5downto 0;beg

15、in B :=Data ;R :=CIN ;CRC (0:=B (0xor R (2;CRC (1:=B (1xor B (0xor R (2xor R (3;CRC (2:=B (2xor B (1xor B (0xor R (2xor R (3xor R (4;CRC (3:=B (3xor B (2xor B (1xor R (3xor R (4xor R (5;CRC (4:=B (3xor B (2xor R (0xor R (4xor R (5;CRC (5:=B (3xor R (1xor R (5;return CRC ;end CRC6;4性能與評(píng)價(jià)通過本文所討論的CRC 推

16、導(dǎo)方法,可以很容易地推導(dǎo)出不同的并行輸入位寬以及生成CRC 碼位寬的并行輸入的CRC 碼算法,并且推導(dǎo)出的公式利于采用VHDL 或者VerilogHDL 等硬件描述語(yǔ)言的編程實(shí)現(xiàn)。本文所描述的設(shè)計(jì),最終下載到Xilinx 公司的Spartan2系列的FPGA 芯片中運(yùn)行,用來完成一套嵌入式系統(tǒng)的通訊協(xié)議模塊的CRC 校驗(yàn)工作。表1中列出了本設(shè)計(jì)(CRC-6和通過LFSR 實(shí)現(xiàn)的CRC 校驗(yàn)?zāi)K的性能比較。表2中列出了原系統(tǒng)中通過軟件實(shí)現(xiàn)的CRC 校驗(yàn)?zāi)K(CRCS-6和本次設(shè)計(jì)的CRC 校驗(yàn)?zāi)K(CRC-6的性能比較。其中CRCS-6的運(yùn)行環(huán)境在ATMEL 公司的AVR 系列處理器上,處理器的

17、主頻為16MHz 。(下轉(zhuǎn)5頁(yè)2表2本設(shè)計(jì)和軟件實(shí)現(xiàn)的CRC性能比較吞吐率峰值/Mbps 工作頻率/MHz占用資源CRC-6600150MHz136SlicesCRCS-61.2處理器主頻16MHz約50行匯編(上接2頁(yè)通過比較可以得出,本文提出的設(shè)計(jì),可以達(dá)到600Mbps 的峰值吞吐率,而和LFSR相比,占用的Slices資源僅僅提高了約一倍。5總結(jié)本文提出了一種并行輸入結(jié)構(gòu)的CRC校驗(yàn)碼電路的推導(dǎo)方法,并給出了由此算法實(shí)現(xiàn)的4位輸入的CRC-6的代碼設(shè)計(jì)例子。通過與LFSR方法和基于AVR RISC處理器匯編語(yǔ)言實(shí)現(xiàn)的CRC運(yùn)算模塊的性能作比較,最終得出,采用此種設(shè)計(jì)方法設(shè)計(jì)的CRC模塊

18、,可以在使用資源增加不大的情況下,獲得較高的性能。此外,通過本文描述的推導(dǎo)算法所生成的CRC計(jì)算公式,便于使用VHDL、VerilogHDL等硬件描述語(yǔ)言描述。并且,本文所設(shè)計(jì)的模塊也適于封裝成庫(kù)應(yīng)用于VLSI或者SoC環(huán)境。(收稿日期:2006年8月參考文獻(xiàn)1.Telecommunications and information exchange between system local and metropolitan area networks specific requirements Part3S.IEEE Std802.3,Institute of Electrical and E

19、lectronics Engineers,Inc,1998: 62652.Rajesh Nair.A symbol based algorithm for hardware implementation of cyclic redundancy check(CRCC.In:Proceedings of the1997 VHDL International Users Forum(VIUF97,1997:81823.William S Shay.Understanding Data Communications and NetworksM. 3rd,Toronto:Thomson Learnin

20、g,2003:4214464.Simon Haykin.Communication SystemsM.4th,New York:John Wiley &Sons Inc,2001:5315346.James R Armstrong,F Gail Gray.VHDL Design Representation and SynthesisM.Second Edition,New York:Prentice-Hall International, Inc,2000:1501627.Charles H Roth.Fundamentals of Logic DesignM.5th,Tornoto

21、:Thom-son Learning,2003:213226表1一個(gè)不對(duì)稱網(wǎng)絡(luò)的性能參數(shù)工作站12345類別實(shí)時(shí)非實(shí)時(shí)實(shí)時(shí)非實(shí)時(shí)實(shí)時(shí)非實(shí)時(shí)實(shí)時(shí)非實(shí)時(shí)實(shí)時(shí)非實(shí)時(shí)w ri0.26270.98500.28480.52720.28340.52640.28400.52610.28380.5243!i2r0.03321.07390.03980.26480.03960.26460.03940.25970.03920.2620w ri0.27500.52640.29700.58010.29670.57730.29600.57840.29560.5753!i2r0.04030.21490.04780.36680

22、.04760.35840.04710.36250.04680.3553w ri0.28080.44160.30240.60560.30260.60050.30290.60680.30190.6027!i2r0.04450.10840.05230.42510.05190.41450.05170.43260.05140.4149k1=2,k i=1(i=2, (5k1=3,k i=1(i=2, (5k1=4,k i=1(i=2, (5s1 i =s2i=0.1,ai"i1=0.75,=0.85,u=0.15,ui=0.2u,i=1,5表2一個(gè)對(duì)稱網(wǎng)絡(luò)實(shí)時(shí)幀的等待時(shí)間上界k i(i=1,

23、(5仿真結(jié)果解析結(jié)果11.04991.450021.62002.350042.64034.150083.79486.9500s1 i =s2i=0.1,ai"i1=0.75,=0.85,u=0.15,ui=0.2u,i=1,5的等待隊(duì)列會(huì)變得不穩(wěn)定。可以看出隨著k1的增大,站1非實(shí)時(shí)幀的等待時(shí)間減小,但是所有站的實(shí)時(shí)幀的平均等待時(shí)間和方差都在增大。所以網(wǎng)絡(luò)設(shè)計(jì)者應(yīng)當(dāng)根據(jù)對(duì)兩類幀不同側(cè)重,選擇合適的服務(wù)參數(shù)。表2是個(gè)對(duì)稱的網(wǎng)絡(luò)例子,即5個(gè)站平均分配總負(fù)荷,但兩類幀承擔(dān)工作站的負(fù)荷比仍然為23。仿真1×106s后發(fā)現(xiàn)實(shí)時(shí)幀的等待時(shí)間都低于由(5式計(jì)算出的上界值,而非實(shí)時(shí)幀的等待

24、時(shí)間則沒有呈現(xiàn)確定的上界。同本文網(wǎng)絡(luò)介質(zhì)訪問方法相比,實(shí)時(shí)環(huán)7有著類似之處在于每一個(gè)工作站也生成實(shí)時(shí)與非實(shí)時(shí)兩類幀。在每次SAT信息(環(huán)控制信息到達(dá)后兩類幀被授權(quán)傳輸,被授權(quán)的數(shù)目均被限制,然而這只能使實(shí)時(shí)幀一部分等待時(shí)間有上限,即從被授權(quán)到被傳輸之間的時(shí)間段。5結(jié)論本文仿照工業(yè)實(shí)時(shí)系統(tǒng)提出了受限泊松幀到達(dá)過程,使相鄰幀到達(dá)時(shí)刻的間距不小于一個(gè)固定值。并且提出了一種新的基于輪詢的網(wǎng)絡(luò)模型,其中每一個(gè)工作站都到達(dá)兩類數(shù)據(jù)幀,一類是實(shí)時(shí)幀到達(dá)服從受限泊松分布,一類是非實(shí)時(shí)幀到達(dá)服從標(biāo)準(zhǔn)泊松分布。本文采用窮盡式策略傳輸實(shí)時(shí)幀,而用k-有限式策略傳輸非實(shí)時(shí)幀。通過計(jì)算機(jī)仿真的方法為一個(gè)給定的網(wǎng)絡(luò)選擇合

25、適的服務(wù)參數(shù)。本文分析了實(shí)時(shí)幀的等待時(shí)間上界,仿真結(jié)果表明實(shí)時(shí)幀的等待時(shí)間總是低于它的上界。所以研究結(jié)果可以應(yīng)用在安全關(guān)鍵領(lǐng)域,如運(yùn)輸和工業(yè)自動(dòng)化。(收稿日期:2006年8月參考文獻(xiàn)1.Stefano Vitturi,Daniele Miorandi.Hybrid ethernet/IEEE802.11net-works for real-time industrial communicationsC.In:ETFA10th IEEE Conference on,2005:4434493.Decotignie J D.Ethernet-based real-time and industrial communica-tio