1、第25卷第1期暨南大學學報(自然科學版 Vol. 25No. 12004年2月 Journal of Jinan University(Natural Science Feb. 2004基于Verilog 的循環冗余校驗(CRC 的實現吳士萍, 車 娟, 黃君凱(暨南大學電子工程系, 廣東廣州510632摘 要 介紹了CRC 的工作原理, 給出了基于Verilog 的可編程邏輯器件的實現方法及其仿真結果.關鍵詞 循環冗余校驗; m 序列; 模2除法中圖分類號 TN914. 3 文獻標識碼 A 文章編號 1000-9965(2004 01-0045-06數字通信要求傳輸過程中所造成的數碼差錯足夠

2、低. 引起傳輸差錯的根本原因是信道內存在噪聲及信道傳輸特性不理想造成的碼間串擾, 為了盡可能的提高通信的可靠性, 需要采用信道編碼技術1(又稱抗干擾編碼 , 對可能或已經出現的差錯進行控制, CRC(循環冗余校驗 碼就是其中一種有效的編碼技術, 在移動通信、計算機通信、USB 接口、測控等領域有著廣泛的應用. 本文通過可編程邏輯器件來實現CRC 的功能, 其中, 發送碼由m 序列發生器產生.1 基本原理1 1 循環冗余校驗(CRC循環冗余校驗1(cyclic redundanc y check, CRC 是一種檢錯能力很強, 且使用非常廣泛的數據傳輸差錯檢測方法. 循環冗余校驗采用在要發送的有

3、用碼后邊添加一個稱為循環冗余校驗碼(簡稱CRC 碼 的比特串來實現數據傳輸差錯檢測. 這種碼的編碼和解碼設備都不太復雜, 且檢、糾錯的能力較強, 目前在理論上和實踐上都有了較大的發展. 循環碼除了具有線性碼的一般性質外, 還具有循環性, 即循環碼中任一碼組循環一位(將最右端的碼元移至左端, 或反之 以后, 仍為該碼中的一個碼組.循環冗余校驗由分組線性碼的分支而來2, 它建立在嚴格的代數理論基礎上, 利用除法和余數的原理來進行錯誤偵測(error detecting. 在除法運算中, 如果用被除數除以除數后所得的余數不為零, 那么從被除數中減去余數后, 所得結果可被除數除盡, 循環冗余校驗正是基

4、于這一思想. 采用CRC 校驗時, 發送方和接收方事先約定一個生成多項式G (X , 該生成多項式作為除數多項式, 將要發送的數據比特序列作為一個多項式F (X 的系數, 該多項式為被除多項式, 被除多項式F(X 與除數多項式的余數多項式R(X 的系數為循環冗余校驗碼(CRC 碼 , 它添加在要檢測的二進制位串后邊, 形成發送碼. 數據鏈路將發送碼發送到接收方后, 接收方同樣將其看成是一個多項式的系數序列, 并用相同的生成多項式來除該多項式. 若余數為零, 則傳輸無差錯; 否則, 傳輸有差錯.收稿日期 2003-09-08( 女, , :.46暨南大學學報(自然科學版 2004年最長線性反饋移

5、存器序列1, 2簡稱m 序列, 是由帶圖1 CRC 碼的模2計算流程線性反饋的移存器產生的周期最長的一種序列, 具有平衡性、游程特性、線性迭加性、自相關特性和偽噪聲特性, 應用十分廣泛. 本文采用4級反饋移存器構成設計周期為P =24-1=15的m 序列發生器, 所用本原多項式為X 4+X 3+1, 如圖2所示. 若設定初始狀態為(A 3, A 2, A 1, A 0 =(0, 0, 0, 0 , 在移位一次時, 由移位寄存器A 3和A 0經同或運算產生新的輸入A 4=0! 0=1, 由此發生器狀態變為(A 3, A 2, A 1, A 0 =(1, 0, 0, 0 . 類似地, 在移位15次

6、后可回到初始狀態(0, 0, 0, 0 , 因此, 它的周期為15 .圖2 4級反饋寄存器構成的m 序列發生器2 循環冗余校驗的實現2 1 循環冗余校驗的內部結構考慮到循環冗余校驗碼的功能, 本功能模塊由3部分組成:m 序列發生器, 它隨機產生一數據流供以后的校驗碼產生和接收檢驗; 數據發送模塊, 它負責發送數據并加冗余進程; 數據接收模塊, 它負責接收并驗證數據是否正確. 如圖3所示. 2 2 程序說明為了協調各進程之間工作, 進程之間設置了握手信號fx 、fy 、fa 、fb, 這樣避免了進程之間沖突, 有利于控制進程的工作秩序. 他們之間的工作關系如表1所示.表1 進程之間的握手信號(a

7、 進程mxlenge 和進程encrc 之間fx 0011fy 0101工作狀態無效mx lenge 工作, encrc 禁止mx lenge 禁止, encrc 工作無效fa 0011(b 進程encrc 和進程decrc 之間fb 0101工作狀態decrc 工作, encrc 禁止無效無效decrc 禁止, encrc 工作圖3 CRC 校驗的內部結構框圖第1期吳士萍等: 基于Verilog 的循環冗余校驗(CRC 的實現47進程encrc 在進程mxlenge 數據生成完畢后開始工作, 然后將第一個進程產生的數據除多項式生成冗余校驗位. 通過循環, 將11位數據移位再與生成多項式異或,

8、 生成5位的冗余校驗位:00111. 數據拼接上冗余校驗位后發送.進程decrc 收到16位數據后, 將前11位數據進行冗余計算, 所得冗余校驗位與收到的最后5位數據相比較, 若相同, 則表示接收的數據無誤; 否則chaerr 信號置高電平, 表示收到誤碼, 并加以清零. 2 3 CRC 功能的實現用Verilog HDL 語言完成電路描述之后, 本文采用MAX+PLUS #3工具對程序進行了功能和時序仿真. 采用的器件是ALTERA 公司的FLEX10K 系列芯片, 仿真波形如圖4所示 .圖4 CRC 的仿真波形由仿真波形可知, 由于發送有效碼要經過15個周期才能形成, 因此第15個周期之前

9、的mxl 寄存器中的數據在每個周期后是變化的. CRC 碼為00111. 由圖4的結果表明, 基于Verilog 的循環冗余校驗(CRC 是完全正確的, 圖3完整地指出了CRC 的結構框圖, 讀者可予參考. 2 4 完整的Verilog HDL 程序/m 序列發生器, 11位信息加5位校驗碼發送, 接收進程完成譯碼. /CRC 碼生成多項式是X 5+X 4+X 2+1. module crc5(clk, start, tail -crc, seda, recda, chaerr ; input clk;input start; /起始信號output4:0tail -crc; /冗余碼outp

10、ut10:0seda, recda; /顯示發送、接收碼output chaerr; /信道錯誤指示reg48暨南大學學報(自然科學版 2004年reg4:0tail -crc; reg10:0seda, recda;reg10:0sedareg; /m 序列產生的有用碼暫存變量reg10:0buf1, buf2; /存放發送、接收有用信號的變量reg15:0mxl; /m 序列暫存變量reg15:0sema, rema; /存放發送、接收碼變量reg fx, fy, fa, fb; /三進程之間的握手變量always(posedge clk 3 /m序列發生器模塊beginif(! star

11、t mxl=16h0000; elsebegin :mxlenge if(! fx fy=0;mxl15=mxl14mxl114;mxl=mxl>>1; endif (! mxl15:11 beginsedareg=mxl10:0; fy=1; end endalways(posedge clk /crc5碼產生模塊begin :encrc if(fy fx=1; else begin fx=0; fb=1; seda=sedareg; buf1=sedareg;if(buf110 buf110:5=buf110:56b1101015; if(buf19 buf19:4=buf19

12、:46b110101; if(buf18 buf18:3=buf18:36b110101;第1期吳士萍等: 基于Verilog 的循環冗余校驗(CRC 的實現49if(buf16 buf16:1=buf16:16b110101; if(buf15 buf15:0=buf15:06b110101; tail -crc=buf14:0; se ma=buf1, tail -crc; if(! fa fb=0; end endalways(ne gedge clk /接收端CRC5校驗模塊begin if(fb fa=1; else begin rema=sema; recda=rema15:5;

13、buf2=re ma15:5;if(buf210 buf210:5=buf210:56b110101; if(buf29 buf29:4=buf29:46b110101; if(buf28 buf28:3=buf28:36b110101; if(buf27 buf27:2=buf27:26b110101; if(buf26 buf26:1=buf26:16b110101; if(buf25 buf25:0=buf25:06b110101; if(buf24:0tail-crc recda=0; else beginrecda=rema15:5; chaerr=0; end end fa=0;

14、end endmoduleCRC 校驗有著廣泛的應用領域, 如移動通信、計算機通信、USB 接口等等. 通過前面的介紹可知, 使用C RC 碼作為糾錯編碼的算法, 結構簡單, 通俗易懂.50 暨南大學學報( 自然科學版 2004 年 參考文獻 1 2 3 4 5 徐志軍, 徐光輝. CPLD/ FPGA 的開發與應用 M . 北京: 電子工業出版社, 2002. 樊昌信. 通信原理 M . 北京: 國防工業出版社, 1995: 323- 344. 王金明, 楊吉斌. 數字系統設計與 Verilog HDL M . 北京: 電子工業出版社, 2002. 夏宇聞. 從算法設計到硬線邏輯的實現 M

15、. 北 京: 高等教育出版社, 2001. BHASKER J. Verilog HDL 硬件描述語言 M . 北京: 機械工業出版社, 2000. Realization of CRC based on Verilog WU Shi- ping, CHE Juan, HUANG Jun- kai ( Dept. of Electronic Engineering, Jinan University, Guangzhou 510632, China Abstract The principle of CRC is introduced. It emphasizes on the element

16、s of error check and data coding style of CRC. The CPLD realizing method based on Verilog and its simulation results are provided. Key words CRC( cyclic redundancy check ; m sequence; Modulo 2 責任編輯: 王蔚良 ( 上接第 40 頁 Research on the techniques of search engines based on dynamic knowledge bases WANG Hui

17、- jing, CHEN Chao- hua, LI Qing ( Dept. of Computer Science, Jinan University, Guangzhou 510632, China Abstract A fundamental problem for Information Retrieval ( IR is the word mismatch . Some query expansion approaches have been proposed to solve the problem. A new method based on the dy namic knowledge base is proposed to make the query expansion. A prototype of the Dynamic Knowledge base Information Retrieval System ( DKIRS is implemented and it constructs a knowledge base using the searc