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

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

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

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

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

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

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

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

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

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

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

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

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

13、O捕捉到的波形如上，當(dāng)復(fù)位信號為0時，產(chǎn)生輸入信號，同時，CRC校驗位也相應(yīng)發(fā)生變化。以上是Ila核捕捉的CRC校驗位的校驗位。板上調(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同步信號，標(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é)：這種基本的串行運算電路僅用了移位寄存器和異或門，占用的資源很少，實現(xiàn)原理比較 簡單，不論其輸人數(shù)據(jù)是 8b