CRC編碼算法研究與實(shí)現(xiàn)_圖文

1、西北大學(xué)學(xué)報(bào)(自然科學(xué)版2006年12月,第36卷第6期,Dec.,2006,V01.36,No.6Joumal of Nonhwest University(Natural Science EditionCRC編碼算法研究與實(shí)現(xiàn)李宥謀1,房鼎益2(1.西安郵電學(xué)院專用集成電路設(shè)計(jì)中心,陜西西安710061;2.西北大學(xué)信息科學(xué)與技術(shù)學(xué)院,陜西西安710061摘要:目的研究cRc編碼中模2除法運(yùn)算的規(guī)則,解決cRC編解碼過程中的延時(shí)問題。方法對(duì)CRC編碼中模2除法進(jìn)行變換,得出一種無延時(shí)、簡單、實(shí)用的編碼算法。結(jié)果采用Verilog 語言設(shè)計(jì)一個(gè)經(jīng)過驗(yàn)證的16位無延時(shí)的cRC一16軟核。結(jié)論該

2、軟核可直接應(yīng)用到具有CRC.16校驗(yàn)電路的收發(fā)器中。關(guān)鍵詞:CRC碼;CRC.16;Ve訂109HDL語言中圖分類號(hào):TN911.22文獻(xiàn)標(biāo)識(shí)碼:A文章編號(hào):1000-274X(200606一0895旬4在串行數(shù)據(jù)傳輸中廣泛采用循環(huán)冗余校驗(yàn)碼CRC(cyclic redundancy check來測試一個(gè)數(shù)據(jù)包是否有錯(cuò)誤發(fā)生,雖然循環(huán)冗余校驗(yàn)碼的理論較為復(fù)雜,但實(shí)現(xiàn)檢錯(cuò)的基本原理十分簡單。在m位信息碼后再拼接r位的校驗(yàn)碼,整個(gè)編碼長度為n位,因此這種編碼又叫(n,南碼。對(duì)于一個(gè)給定的(n,庇碼,可以證明存在一個(gè)最高次冪為挖一露=r的多項(xiàng)式g(戈。根據(jù)g(z可以生成后位信息的校驗(yàn)碼,而g(石叫做

3、這個(gè)CRc碼的生成多項(xiàng)式。校驗(yàn)碼的具體生成過程為:假設(shè)發(fā)送信息用數(shù)據(jù)多項(xiàng)式m(戈表示,將m(z左移n一五位,則可表示成,n(z×2”。這樣m(尤的右邊就會(huì)空出n一露位,即校驗(yàn)碼的位置。通過m(戈×2”除以生成多項(xiàng)式g(戈得到的商Q(戈和余數(shù)r(戈,其中余數(shù)r(戈就是校驗(yàn)碼。即/、一,、叢孕善=Q(戈+興。(1g L石/g k咒/在發(fā)送端發(fā)送數(shù)據(jù)時(shí)余數(shù)加到信息碼之后一同發(fā)出,將一組信息碼和余數(shù)組成的數(shù)據(jù)塊稱為一個(gè)碼元,設(shè)為r(戈,則有丁(石=m(咒×2“一8+r(戈。(2在接收端任一組多項(xiàng)式r(z都應(yīng)被生成多項(xiàng)式g(戈整除,如果傳輸中未發(fā)生錯(cuò)誤,則接收碼元與發(fā)送碼元

4、相同,故接收的碼元必定能被g(戈整除;若碼元在傳輸中發(fā)生錯(cuò)誤,則接收的碼元可能除不盡而有余數(shù),因此我們就以余數(shù)是否為零來判斷接收碼元中有無錯(cuò)誤?？赡苡绣e(cuò)誤的碼元正好也被g(咒整除,這是CRC校驗(yàn)無力消除的,但通過選擇多項(xiàng)式g(戈和增加冗余位數(shù),使余數(shù)r(戈多項(xiàng)式的位數(shù)增多,來降低發(fā)生這種錯(cuò)誤的概率。l CRC碼的計(jì)算方法按照一般的模2除法過程設(shè)汁cflc邏輯電路(見圖1。其生成多項(xiàng)式為g(戈=戈6+x5+z4+z3 +1。邏輯電路由6個(gè)移位寄存器和4個(gè)異或門組成,完成模2除法運(yùn)算。第6級(jí)寄存器的輸出就是模2除法的商,一個(gè)時(shí)鐘周期右移一次,如果除法商“l(fā)”時(shí)(即第6級(jí)寄存器的輸出為“1”時(shí),移位

5、寄存器輸出與生成多項(xiàng)式g(石進(jìn)行模2運(yùn)算,然后右移一收稿日期:20051011基金項(xiàng)目:國家863基金資助項(xiàng)目(2003AAlzll90;陜西省科研發(fā)展基金資助項(xiàng)目(2004K05一G4作者簡介:李宥謀(1959一,男,陜西西安人,西安郵電學(xué)院副教授,從事網(wǎng)絡(luò)通信、集成電路研究。西北大學(xué)學(xué)報(bào)(自然科學(xué)版第36卷位。否則直接右移一位。對(duì)于一個(gè)14位數(shù)據(jù)流和6位14位數(shù)據(jù)流的CRC校驗(yàn)碼。CRc碼組成的碼元,需要20個(gè)時(shí)鐘周期才能計(jì)算出輸CLK清零圖l有延時(shí)的CRC邏輯電路Fig.1CRC logical circuit with delay有延時(shí)的cRc邏輯電路工作過程:先將移位寄存器清零;將數(shù)

6、據(jù)流m(戈的高6位移進(jìn)六級(jí)的寄存器中,由于寄存器初始值為零,因此數(shù)據(jù)流m(戈的高6位移進(jìn)寄存器中不發(fā)生改變;數(shù)據(jù)流m(石繼續(xù)移進(jìn)寄存器時(shí),第6級(jí)移位寄存器移出值若為“0”時(shí),不進(jìn)行模2運(yùn)算只右移一位;若為“1”時(shí)進(jìn)行模2運(yùn)算后右移一位;數(shù)據(jù)流m(石全部移進(jìn)寄存器后,還要繼續(xù)移進(jìn)6個(gè)連續(xù)“0”之后,該組數(shù)據(jù)的cRc計(jì)算才結(jié)束。這種電路的設(shè)計(jì)思想完全采用了一般的模2除法的運(yùn)算過程。其最大缺點(diǎn)是在數(shù)據(jù)流m(菇結(jié)束后還需要連續(xù)輸入6個(gè)“o”,再計(jì)算6次后,移位寄存器的值才是CRC碼,增加了6個(gè)時(shí)鐘延遲,使數(shù)據(jù)流m(戈結(jié)束到CRc校驗(yàn)碼計(jì)算結(jié)束之間有6個(gè)時(shí)鐘間隔,造成它們之間的不同步,給電路設(shè)計(jì)帶來了困

7、難。2CRC算法的改進(jìn)針對(duì)有延時(shí)的cRC邏輯電路和模2除法運(yùn)算過程進(jìn)行分析,發(fā)現(xiàn)模2除法開始前,必須將數(shù)據(jù)流m(z的最高6位,先一位一位的移進(jìn)移位寄存器,然后才進(jìn)行模2除法運(yùn)算,使得模2除法運(yùn)算不能和數(shù)據(jù)流m(戈的流人同時(shí)開始。如果能尋找一種算法,使模2除法運(yùn)算提前開始,不需等待6個(gè)時(shí)鐘周期,那么就可以消除數(shù)據(jù)流m(戈和cRc校驗(yàn)碼之間的6個(gè)時(shí)鐘問隔,簡化電路設(shè)計(jì)。因此,對(duì)CRC編碼的除法過程進(jìn)行變換,找到了一種遞歸算法,其推導(dǎo)過程如下:設(shè)數(shù)據(jù)流m(戈=c。+c訓(xùn)F。1+ C2X2+G1x1+Co,(3生成多項(xiàng)式g(石=甌F+礬一lF_1+ 92x2+glxl+go,(4第i次運(yùn)算的余數(shù)r(川

8、H(戈=r(州H¨矛1+ r(n+1一。一2r一2+r(n+1一i2X2+r(。+1一i lXl+(5商Q(石=d。x“+d。一1x“_1+d2矛+dlxl +氏,(6則由式(1得Q(z+r0(戈/g(x=(m(z×2/g(石= (C。X“×2+C。一1X“-1×2+C2r×2+C1X1×2+Co×2/g(石=Go×2/g(菇+x(C1×2/g(戈+X(G2×2/g(菇+X(C。一1×2/g(菇+X(C。×2/g(戈。(7數(shù)據(jù)流m(石的傳輸順序是從最高位到最低位依次傳輸,即為

9、G。,C。二1'.一,C。,c0。計(jì)算順序從式(7中最里面的括號(hào)開始計(jì)算。由于是二進(jìn)制多項(xiàng)式,因此在運(yùn)算過程中x的取值為2。在一組n次多項(xiàng)式的數(shù)據(jù)流m(石中有n+1位,在運(yùn)算前不需要裝入移位寄存器消除了等待時(shí)間,因此在m(石傳送的n+1個(gè)時(shí)鐘周期內(nèi)就可以完成運(yùn)算。將式(7按照數(shù)據(jù)流m(z傳輸J頃序進(jìn)一步展開計(jì)算如下。第一個(gè)時(shí)鐘周期:傳輸數(shù)據(jù)流m(茗中第一位(最高位C。×2/g(戈=C。+r。(戈/g(石。第二個(gè)時(shí)鐘周期:傳輸數(shù)據(jù)流m(菇中第二位C。一1×2/g(戈+x(C。+r。(戈/g(戈=C。一1×2/g(戈+X×r。(戈/g(戈+C。x=c

10、。一1×2+2×(r。一lx。一1+r。一2F一2+r。txl+r。o/g(戈+d。x=(c。一1+r。t1×2+r。t一2×2_1+r。1×22+r。o×21/g(石+d。x=d。一l+r。一1(菇/g(戈+d。石。第凡個(gè)時(shí)鐘周期:傳輸數(shù)據(jù)流m(戈中第n位ClX/g(戈+x(d2+r2(戈/g(戈+d。X42+ d。一lx83+d3X=cl x2/g(戈+2×(r2一lx一1+r2一2x一2+ r21x1+r2o/g(戈+d。x”-1+d。一1x“一2+d,r+d,X=第6期李宥謀等:cRc編碼算法研究與實(shí)現(xiàn)897一(c1

11、+r2一1×2+r2k一2×2。一1+r21×22+r2o×21/g(戈+d。X81+d。一1X“一2+d3X2+d2X=d1+rl(戈/g(髫+d。X“_。+d。一lX82+d3r+d2X。第懟+1個(gè)時(shí)鐘周期:傳輸數(shù)據(jù)流鞏(菇中第忍+ 1位(最后一位Cox/g(z+x(d1+r】(戈/,g(髫+d。x“。+ d。一lx“一2+咬x=co×2/g(戈+2×(rl一lx一1+r1&一2釅一2+ r11x1+rl o/g(艽+d。X“+d。一lX”“+d2X2+dlX=(Co+r1kI×2+r1一2×2_1+r

12、ll×22+rl o×21/g(石+d。X“+d。一lX“+d2.Y2+d1X=如+ro(戈/g(戈+d。X8+d。一1叉41+d2X2+d1X=Q(戈+ro(戈/g(戈。經(jīng)過上述的n+1次的計(jì)算和移位后,數(shù)據(jù)流m(z結(jié)束,同時(shí)移位寄存器中的值就是CRc校驗(yàn)碼。從上面的遞歸模2除法過程中,可以設(shè)計(jì)出它的邏輯電路(見圖2。從電路圖的組成來看,有延時(shí)的CRC電路和無延時(shí)的CRC電路,它們所需電路資源相同,都是由6個(gè)寄存器和4個(gè)異或門組成,只是在電路結(jié)構(gòu)上將左邊的異或門移到了右邊,就可以縮短CRC碼的計(jì)算時(shí)間。無延時(shí)CRC電路的這種改進(jìn),使得數(shù)據(jù)流m(戈的高6位不必預(yù)先送人移位寄

13、存器,而是立即進(jìn)行模2除法運(yùn)算,與有延時(shí)的cRc 電路相比,CRc碼的計(jì)算提前了6個(gè)時(shí)鐘周期,恰好解決了數(shù)據(jù)流m(膏結(jié)束后,需要等待6個(gè)時(shí)鐘周期CRc碼才能計(jì)算完成的問題。圖2無延時(shí)的CRC邏輯電路F培.2CRC lo舀cal circuit witllout delay經(jīng)過對(duì)兩種不同算法設(shè)計(jì)的電路進(jìn)行驗(yàn)證,可數(shù)據(jù)流m(戈和cRc碼的發(fā)送。當(dāng)輸出選擇信號(hào)以證明有延時(shí)的cRC邏輯電路和無延時(shí)的CRC邏crcsel為高時(shí),輸出要發(fā)送的數(shù)據(jù),當(dāng)crcsel為低輯電路計(jì)算出的CRc校驗(yàn)碼是完全相同的,只是時(shí),輸出要發(fā)送cRC校驗(yàn)碼。cRc碼的計(jì)算所用的時(shí)間不同。這一結(jié)論可以推按照?qǐng)D3cRc一16邏輯電

14、路,編寫cRc16程序廣到任意長度的CRC碼的計(jì)算。這種改進(jìn)的CRC列表如下。碼計(jì)算方法具有更廣泛的應(yīng)用價(jià)值。module crcl6(clk,reset,crcsel,din,dout;3改進(jìn)后CRC編碼算法的實(shí)現(xiàn)近年來在電路設(shè)計(jì)方面,更多的采用可編程邏輯器件,它具有設(shè)計(jì)靈活、容易擴(kuò)充、容易修改等特點(diǎn),而且可以直接使用已有的軟核或固核,使得電路設(shè)計(jì)更加方便、快捷。目前,使用最多的設(shè)計(jì)方法是采用Verilog或VHDL硬件描述語言。下面以cRC一16L31為例,使用無延時(shí)的CRC設(shè)計(jì)思想,實(shí)現(xiàn)16位的CRC碼的校驗(yàn)電路,并采用Verilog硬件描述語言,給出經(jīng)過驗(yàn)證的16位CRC編碼程序”1。

15、CRC16校驗(yàn)碼,采用的生成多項(xiàng)式為g(戈=戈16+戈15+菇2+l,依據(jù)上述的推導(dǎo)公式(7的結(jié)論設(shè)計(jì)出邏輯電路(見圖3,在圖3中有16級(jí)移位寄存器和3個(gè)異或門,實(shí)現(xiàn)CRC碼的計(jì)算,還有一個(gè)二選一的選擇器、二輸人與門和一個(gè)輸出緩存器,完成inputdin,clk,reset,crcsel;output dout;reg15:Ocrc-ou;reg omJ;/輸出緩存寄存器wire crcctl;/經(jīng)“與門”后的輸出信號(hào)assign dout=outr;assign crcctl=din“crcout15&crcsel;always(posedge clk or posedge rese

16、tbeginif(resetcrcout<=16h00(0;else begincrcout14:3<=crcout13:2;crcout1<=crc_out0;crcout2<=crcout1“crcctl;crcout15<=crcout14“crcctl:一898一西北大學(xué)學(xué)報(bào)(自然科學(xué)版第36卷crcout0<=crcctl;if(crcseloutr<=din;elseoutr<=crcout15;end endendmodule 4結(jié)語圖3cRC一16邏輯電路框圖Fig.3Thelo西cajdi89ram 0f CRC16西安電子科技

17、大學(xué)出版社,2003.由于cRC校驗(yàn)電路實(shí)現(xiàn)簡單,檢錯(cuò)能力強(qiáng),被廣泛應(yīng)用在各種數(shù)據(jù)校驗(yàn)中51。為了解決CRc應(yīng)用中的延時(shí)問題,而提出的無延時(shí)cRC算法可以應(yīng)用于不同長度的cRc碼計(jì)算,實(shí)現(xiàn)了數(shù)據(jù)信息與CRC校驗(yàn)碼的無縫連接。參考文獻(xiàn):2345Out數(shù)據(jù)輸出RAMABADRA刊11V.GAnl0N DE S S.A tutorimoncRccomputationsJ.IEEE Micro,1988,(8:62-74.BORRELU C.IEEE802.3cyclicredundancycheckJ.xIuNxxAPP209March,200l,23(1:l一8.李宥謀,韓俊剛.sDH芯片功能驗(yàn)證

18、平臺(tái)的設(shè)計(jì)與實(shí)現(xiàn)J.光通信研究,2005,130(4:61_63.聶敏,張澤.移動(dòng)通信cDMA系統(tǒng)Qos實(shí)時(shí)測量方法的研究J.西北大學(xué)學(xué)報(bào):自然科學(xué)版,2004,34(1:4446.(編輯亢小玉1王新梅,肖國鎮(zhèn).糾錯(cuò)碼原理與方法M.西安:Research and implementation ofanew CRC coding algorithmLI You.moul,FANG DingVi2(1.ASICCenter,xian university of Post andI、eleeommunications,Xi 7an 710061,China;2.Information Science

19、 and 7Iechnology Institute,Nonhwest university,xian 710069,chinaAbstract:Aim To research the algorithm of CRC coding basedonthe arithmetic of modulo 2for the purposedecreasing the delav generated in CRC code calculating.MethodsTransform the arithmetic of modulo 2in CRCcoding,designasimple and practi

20、eal coding algorithm without delay.ResultsA CRC16Softcore was designedand verified by using Verilog HDL which hasnodelay.ConclusionThe Softcorecanbe use(i directly in thetmnsceiver with the CRC一16verifyingci“:uit.Key words:CRC code;CRC一16;Verilog HDL 1anguage CRC編碼算法研究與實(shí)現(xiàn)作者:李宥謀, 房鼎益, LI You-mou, FAN

21、G Ding-yi作者單位:李宥謀,LI You-mou(西安郵電學(xué)院,專用集成電路設(shè)計(jì)中心,陜西,西安,710061, 房鼎益,FANG Ding-yi(西北大學(xué),信息科學(xué)與技術(shù)學(xué)院,陜西,西安,710061刊名: 西北大學(xué)學(xué)報(bào)(自然科學(xué)版英文刊名:JOURNAL OF NORTHWEST UNIVERSITY(NATURAL SCIENCE EDITION年,卷(期:2006,36(6引用次數(shù):4次參考文獻(xiàn)(5條2.RAMABADRAN T V.GAITONDE S S A tutorial on CRC computations 1988(83.BORRELLI C IEEE 802.3

22、 cyclic redundancy check 2001(1相似文獻(xiàn)(7條2007,21(3介紹了循環(huán)冗余校驗(yàn)CRC算法原理和校驗(yàn)規(guī)則,分析了CRC校驗(yàn)碼的具體計(jì)算過程,并以CRC-16為例,給出了使用硬件描述語言Verilog HDL來實(shí)現(xiàn)CRC-16的部分源程序,它既是校驗(yàn)碼的生成器,也是待校驗(yàn)數(shù)據(jù)的校驗(yàn)器,對(duì)該例進(jìn)行仿真并給出綜合結(jié)果,最終可以在現(xiàn)場可編程門陣列(FPGA上實(shí)現(xiàn),其工作頻率可達(dá)400 MHz.院學(xué)報(bào)2008,28(2在數(shù)據(jù)通信中,提高數(shù)據(jù)在通信中的可靠性,以及快速的數(shù)據(jù)處理能力一直是人們所追求的,循環(huán)冗余校驗(yàn)CRC就是一種廣泛采用的差錯(cuò)控制方法,也是一種最常用的信道編碼方法.在介紹CRC碼原理之后,以經(jīng)典的LFSR電路為基礎(chǔ),推導(dǎo)出產(chǎn)生32位并行數(shù)據(jù)的CRC-16編碼表達(dá)式,用EDA工具設(shè)計(jì)出CRC-16編碼模塊,并對(duì)其進(jìn)行綜合仿真,驗(yàn)證其可行性.本文給出了一種快