CRC循環(huán)冗余校驗(yàn)原理及FPGA實(shí)現(xiàn)

1、CRC循環(huán)冗余校驗(yàn)原理及FPGA實(shí)現(xiàn)姚樹(shù)渝|創(chuàng)建時(shí)間：2013年06月19日14:07|瀏覽：220評(píng)論：0 標(biāo)簽：管理13.1基本CRC循環(huán)冗余校驗(yàn)原理介紹循環(huán)冗余碼校驗(yàn)英文名稱為Cyclical Redundancy Check，簡(jiǎn)稱CRC它是利用除法及余數(shù)的原理來(lái)作錯(cuò)誤偵測(cè)( Error Detecting )的。實(shí)際應(yīng)用時(shí)，發(fā)送裝 置計(jì)算出CRC直并隨數(shù)據(jù)一同發(fā)送給接收裝置，接收裝置對(duì)收到的數(shù)據(jù)重新計(jì)算CRC并與收到的CRC相比較，若兩個(gè) CRC直不同，則說(shuō)明數(shù)據(jù)通訊出現(xiàn)錯(cuò)誤。根據(jù)應(yīng)用環(huán)境與習(xí)慣的不同，CRC又可分為以下幾種標(biāo)準(zhǔn)： CRC-12 碼； CRC-16 碼； CRC-CCI

2、TT碼； CRC-132 碼。CRC-12碼通常用來(lái)傳送 6-bit字符串。CRC-16及 CRC-CCITT碼則用是來(lái)傳送 8-bit字符，其中CRC-16為美國(guó)采用，而CRC-CCITT 為歐洲國(guó)家所采用。CRC-132碼大都被采用在一種稱為Poi nt-to-Poi nt的同步傳輸中。1. CRC特點(diǎn)CRC是種常用的檢測(cè)錯(cuò)誤的循環(huán)碼，它能夠榆測(cè)出如下錯(cuò)誤：(1) 突發(fā)長(zhǎng)度小于r的突發(fā)錯(cuò)誤。(2) 大部分突發(fā)長(zhǎng)度等于r十I的錯(cuò)誤，其中不可檢測(cè)的這類錯(cuò)誤只占2-(r-1)。(3) 大部分突發(fā) K度大于r+1的錯(cuò)堤，其中不可檢測(cè)的這類錯(cuò)誤只占2-r。(4) 所有奇數(shù)個(gè)錯(cuò)誤。CRC檢錯(cuò)能力極強(qiáng)，

3、開(kāi)銷小，易于用編碼器及檢測(cè)電路實(shí)現(xiàn)。從其檢錯(cuò)能力來(lái)看，它所 不能發(fā)現(xiàn)的錯(cuò)誤的幾率僅為0.0047%以下。從性能上和開(kāi)銷上考慮，均遠(yuǎn)遠(yuǎn)優(yōu)于奇偶校驗(yàn)及算術(shù)和校驗(yàn)等方式。因而，在數(shù)據(jù)存儲(chǔ)和數(shù)據(jù)通訊領(lǐng)域，CRC無(wú)處不在：著名的通訊協(xié)議X.25的FCS(幀檢錯(cuò)序列)采用的是 CRC-CCITT , Win RAR、NERO、ARJ、LHA等壓縮工具 軟件采用的是 CRC132 ,磁盤驅(qū)動(dòng)器的讀寫采用了CRC16 ,通用的圖像存儲(chǔ)格式 GIF、TIFF等也都用CRC作為檢錯(cuò)手段。2. CRC生成原理CRC循環(huán)碼即在m位信息碼后再拼接r位的校驗(yàn)碼，整個(gè)編碼長(zhǎng)度為n位，因此這種編碼又叫(n , k)碼。對(duì)于一

4、個(gè)給定的(n , k)碼，可以證明存在一個(gè)最高次幕為n-k=r的多項(xiàng)式g(x)。根據(jù)g(x)可以生成后位信息的校驗(yàn)碼，而g(x)叫做這個(gè)CRc碼的生成多項(xiàng)式。校驗(yàn)碼的具體生成過(guò)程為：假設(shè)發(fā)送信息用數(shù)據(jù)多項(xiàng)式 m(x)表示，將m(x)左移n k位，則可表示成，n(z) x 2n-k。 這樣m(x)的右邊就會(huì)空出 n k位，即校驗(yàn)碼的位置。通過(guò)m(x) x 2n-k,除以生成多項(xiàng)式g(x) 得到的商Q(x和余數(shù)r(x)，其中余數(shù)r(x)就是校驗(yàn)碼。即：在發(fā)送端發(fā)送數(shù)據(jù)時(shí)余數(shù)加到信息碼之后一同發(fā)出，將一組信息碼和余數(shù)組成的數(shù)據(jù)塊 稱為一個(gè)碼元，設(shè)為 T(x)，則有在接收端任一組多項(xiàng)式 T(x)都應(yīng)被

5、生成多項(xiàng)式 g(x)整除，如果傳輸中未發(fā)生錯(cuò)誤，則接 收碼元與發(fā)送碼元相同，故接收的碼元必定能被g(x)整除；若碼元在傳輸中發(fā)生錯(cuò)誤，則接收的碼元可能除不盡而有余數(shù)，因此我們就以余數(shù)是否為零來(lái)判斷接收碼元中有無(wú)錯(cuò)誤。 可能有錯(cuò)誤的碼元正好也被g(x)整除，這是CRC校驗(yàn)無(wú)力消除的，但通過(guò)選擇多項(xiàng)式g(x)和增加冗余位數(shù)，使余數(shù) r(x)多項(xiàng)式的位數(shù)增多，來(lái)降低發(fā)生這種錯(cuò)誤的概率。3. 生成多項(xiàng)式的選擇生成多項(xiàng)式g(x)是構(gòu)成CRC校驗(yàn)碼的關(guān)鍵。它的選取并不是任何一個(gè)多項(xiàng)式都可以作為 生成多項(xiàng)式的，從檢錯(cuò)與糾錯(cuò)的要求出發(fā)，生成多項(xiàng)式應(yīng)能滿足下列要求：(1) 任何一位發(fā)生錯(cuò)誤都應(yīng)使余數(shù)不為0;(2

6、) 不同位發(fā)生錯(cuò)誤應(yīng)當(dāng)使余數(shù)不同；(13)應(yīng)滿足余數(shù)循環(huán)規(guī)律。CRC有多種國(guó)際標(biāo)準(zhǔn)，各種標(biāo)準(zhǔn)如下：CRC校驗(yàn)可以100 %地檢測(cè)出所有奇數(shù)個(gè)隨機(jī)錯(cuò)誤和長(zhǎng)度小于等于愚(是為g(z)的階數(shù))的突發(fā)錯(cuò)誤。所以CRc的生成多項(xiàng)式的階數(shù)越高，誤判的概率就越小。13.2 CRC循環(huán)冗余碼 FPGA設(shè)計(jì)思想1. 編碼電路的設(shè)計(jì)思想編碼電路的功能是己知信息數(shù)據(jù)位和生成多項(xiàng)式，要得到對(duì)應(yīng)的CRC碼字。CRC碼是系統(tǒng)碼，對(duì)一個(gè)合法的CRC碼字前面部分是原始信息位，后面部分為校驗(yàn)位部分。因此，若能求解出校驗(yàn)位，把它與原始數(shù)據(jù)組合即可得到CRC碼?，F(xiàn)已知 m(x) , G(x)，要求R(x)，用X*m(x)除以G(x

7、)，它的余式即為 XR(x)。用二進(jìn)制數(shù)表示，即將原始信息位后添 r個(gè)0后 的數(shù)據(jù)除以生成多項(xiàng)式對(duì)應(yīng)的二進(jìn)制數(shù)，所得余數(shù)即是校驗(yàn)位。2. 解碼電路的設(shè)計(jì)思想一個(gè)合法的CRC碼的多項(xiàng)式，它應(yīng)該能被 G(x)整除。據(jù)此，現(xiàn)對(duì)一個(gè)位長(zhǎng)為n的數(shù)據(jù)段(可能不是一合法 CRC碼)，其多項(xiàng)式除以 G(x)，若其余數(shù)為零，說(shuō)明該碼字是合法的，取 出其前面部分即為發(fā)端發(fā)送的有效數(shù)據(jù)，即完成解碼；若余數(shù)不為0,則該碼字出錯(cuò)，接收方可以告知發(fā)方重發(fā)，或進(jìn)行糾錯(cuò)后再解碼。實(shí)際上，對(duì)任意的CRC碼都能糾正一個(gè)錯(cuò)誤。3. 軟件及硬件實(shí)現(xiàn)方法一般有以下幾種軟件實(shí)現(xiàn)方法：逐位運(yùn)算法：則是用簡(jiǎn)單的軟件編程來(lái)實(shí)現(xiàn)CRC編碼，完成

8、這種編碼的原理同使用線性反饋移位寄存器的硬件方法雷同。假定監(jiān)督位已儲(chǔ)存在稱之為CRC的寄存器中，則逐位運(yùn)算法則的實(shí)現(xiàn)步驟可歸納如下： 給CRC寄存器賦值為0 如果CRC寄存器中最左邊的1位是” I”，則移人下一個(gè)消息位，并且用碼的生成多項(xiàng)式對(duì)CRC寄存器進(jìn)行模2相加；否則，只移人下一個(gè)消息位 重復(fù)第2步，直到一幀消息碼的所有位都被移人為止。標(biāo)準(zhǔn)查找表運(yùn)算法：對(duì)所有增加了 a位組合的CRC編碼進(jìn)行預(yù)處理，然后在查找表中找出對(duì) 應(yīng)的值作為CRC編碼的監(jiān)督位。假設(shè)監(jiān)督位已儲(chǔ)存在稱之為 CRC勺寄存器中，則標(biāo)準(zhǔn)查找表 運(yùn)算法則的軟件實(shí)現(xiàn)步驟歸納如下： 給CRC寄存器賦值為0,即設(shè)置(r n-k 一 1

9、, ., ro)位為0。 用右移了 (n ka)位的CRC寄存器的內(nèi)容對(duì) a個(gè)輸入位進(jìn)行模 2相加，即用(r n-k-1,.,ro)進(jìn)行模 2 相加。 在查找表中找出相應(yīng)的值，并且用左移了a位的CRC寄存器的內(nèi)容對(duì)其進(jìn)行模2相加，即用(r n-k-1,.,ro)進(jìn)行模2相加，然后代替原 CRC寄存器的內(nèi)容。 重復(fù)第二和第三步，直到所有的信息位都移人為止。一般有以下幾種硬件實(shí)現(xiàn)方法：(1) 采用LSFR(線性反饋移位寄存器組)來(lái)完成，這種方法簡(jiǎn)單，但每次只能處理一位二進(jìn)制數(shù)據(jù)，也很難以滿足速度較高的場(chǎng)合。(2) CRC校驗(yàn)碼的并行算法有查表法及基于查表法而導(dǎo)出的一些方法，但這些方法均需要存儲(chǔ)長(zhǎng)度

10、較大的CRC余數(shù)表，并且隨著并行位數(shù)的增加，余數(shù)表的長(zhǎng)度按指數(shù)增加，其現(xiàn)實(shí)性亦隨之大大降低.(13)根據(jù)線性時(shí)不變系統(tǒng)的特性推出了用于計(jì)算CRC校驗(yàn)碼,計(jì)算的轉(zhuǎn)換矩陣，但變換矩陣的推導(dǎo)方法過(guò)于煩瑣。(4)按字節(jié)運(yùn)算方法，它直接推導(dǎo)出CRC校驗(yàn)碼與輸入數(shù)據(jù)和生成多項(xiàng)式的邏輯關(guān)系，然后直接運(yùn)算得出CRC校驗(yàn)碼，這種方法直接、簡(jiǎn)潔。13.3 CRC循環(huán)冗余碼 FPGA實(shí)現(xiàn)CRC 16校驗(yàn)碼，采用的生成多項(xiàng)式為 g(x)=x16+x15+x2+l ，依據(jù)上述的推導(dǎo)公式的結(jié)論 設(shè)計(jì)出邏輯電路(見(jiàn)下圖)，在圖中有16級(jí)移位寄存器和13個(gè)異或門，實(shí)現(xiàn) CRC碼的計(jì)算。 初始化時(shí)每一位寄存器都清零，然后每輸入

11、一位數(shù)據(jù)，16位移位寄存器按照異或邏輯由低到高進(jìn)行移動(dòng)1位，直到一組校驗(yàn)數(shù)據(jù)結(jié)束，此時(shí)，16位移位寄存器的內(nèi)容就是該組數(shù)據(jù)的CRC-16的校驗(yàn)位。這里采用按字節(jié)運(yùn)算方法，它直接推導(dǎo)出CRC校驗(yàn)碼與輸入數(shù)據(jù)和生成多項(xiàng)式的邏輯關(guān)系，然后直接運(yùn)算得出CRC校驗(yàn)碼。添加test bench進(jìn)行功能測(cè)試。從仿真結(jié)果可知，當(dāng)輸入為1001100110011001時(shí)，通過(guò)CRC校驗(yàn)得到的校驗(yàn)位如上圖所示。由于串行CRC運(yùn)算，當(dāng)前的CRC余數(shù)值只與當(dāng)前信息碼的最前一位的輸入值和前一狀態(tài)的 CRC余數(shù)值有關(guān)，所以，當(dāng)輸入到最后一位信息位時(shí)，此時(shí)的校驗(yàn)位即為最終的校驗(yàn)位。這 里輸入的信息為周期信號(hào)，所以當(dāng)?shù)?6位

12、到達(dá)后，從圖中可以看到校驗(yàn)位為0101010101011100，這與通過(guò)計(jì)算所得的結(jié)果一致，驗(yàn)證是正確的。通過(guò)綜合后的RTL圖以及內(nèi)部詳細(xì)的電路結(jié)構(gòu)如上圖。在板上調(diào)試時(shí)，需要添加一個(gè)信號(hào)產(chǎn)生模塊source,以下是對(duì)Source添加test bench后的功能仿真波形：即輸入信號(hào)設(shè)為1011001111001101。這里需要對(duì)時(shí)鐘進(jìn)行設(shè)置，這里用的是13E的實(shí)驗(yàn)板，所以 CLK設(shè)為C9,見(jiàn)上圖。加核后，綜合后RTL圖如下所示。這里由于要觀察編解碼后的波形，所以要添加一個(gè)ILA核，那么就要添加兩個(gè)ICON核對(duì)ILA核以及VIO核進(jìn)行控制。通過(guò)下載到實(shí)驗(yàn)板上，chipscope在線調(diào)試結(jié)果如下VI

13、O捕捉到的波形如上，當(dāng)復(fù)位信號(hào)為0時(shí)，產(chǎn)生輸入信號(hào)，同時(shí)，CRC校驗(yàn)位也相應(yīng)發(fā)生變化。以上是Ila核捕捉的CRC校驗(yàn)位的校驗(yàn)位。板上調(diào)試代碼：module crc_mai n(clk,sig_s1,crc_reg,crc_s);in put clk;output15:0sig_s1;output15:0 crc_reg;output0:0 crc_s;wire reset;wire 15:0 sig_s1;wire 15:0 sigie;wire35:0co ntrol0,co ntrol1;wire32:0 data;wire0:0as yn c_out;wire32:0as ync_in;

14、source s1(.clk(clk),.reset(reset),sig_s(sig_s1);crc v1(.clk(clk),.reset(reset), .x(sig_s1),.crc_reg(crc_reg),.crc_s(crc_s);icon icon (.CONTROL0(co ntrol0),.CONTROL1(co ntrol1);assign data15:0=sig_s115:0;assign data31:16=crc_reg15:0;assign data32:32=crc_s0:0;ila my_ila(CLK(clk),CONTROL(c on trolO),.T

15、RIGO(reset),.DATA(data)；assig n reset=as yn c_out0;assign asy nc_in 15:0=sig_s115:0;assign async_in31:16=crc_reg15:0;assign async_in32:32=crc_s0:0;vio my_vio(.CONTROL(c on troll),ASYNC_OUT(asy nc_out), ASYNC_IN(asy nc_in);en dmoduleCrc編碼代碼：module crc(clk, reset, x, crc_reg, crc_s);in put clk;in put

16、reset;in put x;/串行輸入數(shù)據(jù)output 15:0 crc_reg; /CRC 編碼輸出output crc_s; /CRC同步信號(hào)，標(biāo)志著一幀編碼的結(jié)束reg 15:0 crc_reg;reg crc_s;reg 3:0 cnt;wire 15:0 crc_e nc;always (posedge clk) begi nif(!reset) beg incrc_reg = 0;cnt = 0;else begi ncrc_reg = crc_e nc;ent = ent +1;if(cnt = 0)crc_s = 0;elsecrc_s = 1;endendassig n c

17、rc_e ncO = crc_reg15Ax;assig n crc_e nc1 = crc_reg0;assig n crc_e nc2 = crc_reg1Acrc_reg15Ax;assig n crc_e nc14:3 = crc_reg13:2;assig n crc_e nc15 = crc_reg14Acrc_reg15Ax; en dmodule輸入的數(shù)據(jù)產(chǎn)生代碼：module source(clk,reset,sig_s );in put clk,reset;output sig_s;reg sig_s;reg1:0 cou nt;reg3:0 addr;parameter

18、COUNT=3d2;always (posedge clk)beginif (reset)beginaddr=3d0;cou nt=3d0;endelsebegincoun t=co un t+1;if(cou nt=COUNT)beginaddr=addr+1;else addr=addr;end end always(posedge clk) begin case(addr3:0)4bOOOO:sig_s=1;4b0001:sig_s=0;4bOO1O:sig_s=1;4b0011:sig_s=1;4b0100:sig_s=0;4b0101:sig_s=0;4b0110:sig_s=1;4b0111:sig_s=1;4b1000:sig_s=1;4b1001:sig_s=1;4b1010:sig_s=0;4b1011:sig_s=0;4b1100:sig_s=1;4b1101:sig_s=1;4b1110:sig_s=0;4b1111:sig_s=1;endcaseend en dmodule13.4小結(jié)：這種基本的串行運(yùn)算電路僅用了移位寄存器和異或門，占用的資源很少，實(shí)現(xiàn)原理比較 簡(jiǎn)單，不論其輸人數(shù)據(jù)是 8b