基于FPGA的crc編碼器的畢業(yè)設計文件綜述

1、畢業(yè)設計（論文）文 獻 綜 述浙江工業(yè)大學之江學院畢業(yè)設計（論文） 文獻綜述 基于FPGA的CRC編碼器的建模和設計1 前言人們對于信息的認識和利用，可以追溯到古代的通訊實踐。中國古代的“烽隧相望”和古羅馬地中海諸城市的“懸燈為號”，可以說是傳遞信息的原始方式。隨著社會生產(chǎn)的發(fā)展，科學技術(shù)的進步，人們對傳遞信息的要求急劇增加。到了20世紀20年代，如何提高傳遞信息的能力和可靠性己成為普遍重視的課題。1948年香農(nóng)(Shannon)在他的開創(chuàng)性論文“通信的數(shù)學理論”中，首次闡明了在有擾信道中實現(xiàn)可靠通信的方法，提出了著名的有擾信道編碼定理，奠定了糾錯碼的基石。目前，利用糾錯碼降低各類數(shù)

2、字通信系統(tǒng)以及計算機存儲和運算系統(tǒng)中的誤碼率，提高通信質(zhì)量，延長計算機無故障運行時間等，在美國等西方國家中已作為一門標準技術(shù)而廣泛采用，而且糾錯碼技術(shù)還用于超大規(guī)模集成電路設計中，以提高集成電路芯片的成品率，降低芯片的成本。不僅如此，糾錯碼技術(shù)已開始滲透到很多領(lǐng)域。利用糾錯碼中的許多編譯碼原理和方法，與通信系統(tǒng)中的其它有關(guān)技術(shù)相結(jié)合，得到令人驚喜的結(jié)果。分組碼和卷積碼是兩類較重要的糾錯碼。分組碼是對信源待發(fā)的信息序列進行分組(每組K位)編碼，它的校驗位僅同本組的信息位有關(guān)。分組碼在數(shù)字通信和數(shù)據(jù)存儲系統(tǒng)中已被廣泛應用。卷積碼不對信息序列進行分組編碼，它的校驗元不僅與當前的信息元有關(guān)，而且同以前

3、有限時間段上的信息元有關(guān)。卷積碼在編碼方法上尚未找到像分組碼那樣有效的數(shù)學工具和系統(tǒng)的理論。但在譯碼方面，不論在理論上還是實用上都超過了分組碼，因而在差錯控制和數(shù)據(jù)壓縮系統(tǒng)中得到廣泛應用。糾錯碼之所以有糾錯功能，是因為里面含有冗余信息，因此糾錯碼比檢錯碼要長很多。通常情況下只采用檢錯碼檢錯，數(shù)據(jù)的可靠性采用重傳的方式來完成。只有在信道質(zhì)量比較差的情況下，重傳次數(shù)很多，重傳開銷非常大，這個時候采用糾錯碼，信道質(zhì)量 越差，采用的糾錯碼漢明間距應該越大，冗余信息也就越多，編碼長度相應變長。廖海紅在通信系統(tǒng)中的CRC算法的研究和工程實現(xiàn)1中指出在通信系統(tǒng)中可靠與快速往往是一對矛盾。若要求快速，則必然使

4、得每個數(shù)據(jù)碼元所占的時間縮短、波形變窄、能量減少，從而在受到干擾后產(chǎn)生錯誤地可能性增加，傳送信息的可靠性下降。若是要求可靠，則使得傳送消息的速率變慢。因此，如何合理地解決可靠性也速度這一對矛盾，是正確設計一個通信系統(tǒng)的關(guān)鍵問題之一。為保證傳輸過程的正確性，需要對通信過程進行差錯控制.差錯控制最常用的方法是自動請求重發(fā)方式(ARQ)、向前糾錯方式(FEC)和混合糾錯(HEC)。在傳輸過程誤碼率比較低時，用FEC方式比較理想。在傳輸過程誤碼率較高時，采用FEC容易出現(xiàn)“亂糾”現(xiàn)象。HEC方式則是ARQ和FEC的結(jié)合。在許多數(shù)字通信中，廣泛采用ARQ方式，此時的差錯控制只需要檢錯功能。實現(xiàn)檢錯功能的

5、差錯控制方法很多，傳統(tǒng)的有:奇偶校驗、校驗和檢測等廠這些方法都是增加數(shù)據(jù)的冗余量，將校驗碼和數(shù)據(jù)一起發(fā)送到接收端。接收端對接收到的數(shù)據(jù)進行相同校驗，再將得到的校驗碼和接收到的校驗碼比較，如果二者一致則認為傳輸正確。但這些方法都有各自的缺點，誤判的概率比較高。循環(huán)冗余校驗CRC(Cyclic Redundancy Check)碼是由分組線性碼的分支而來，其簡稱為循環(huán)冗余碼，其主要應用是二元碼字。編碼簡單且誤判概率很低，在通信系統(tǒng)中得到了廣泛的應用。循環(huán)冗余校驗碼的檢錯能力很強，偶重的循環(huán)冗余校驗碼的檢錯能力如下：能100%檢測出奇數(shù)個差錯；能100%檢測出長度小于等于2的兩個突發(fā)差錯；能100%

6、檢測出小于等于生成多項式碼重dmin-1 的隨機差錯；能100%檢測出長度小于等于校驗位長w的單個突發(fā)差錯;能以的概率檢出長度為的單個突發(fā)差錯；能以的概率檢出長度大于的單個突發(fā)差錯。2 CRC編碼器的建模和設計 2.1 CRC 基本原理一個由若干個“0”或“1”組成n 位二進制數(shù)可以表示成為( n -1)階的多項式的各項系數(shù)，也就是說，一個n 位二進制數(shù)可以用( n -1)階多項式表示。一個8位二進制數(shù)可以用一個7階二進制碼多項式表示2。CRC碼共由兩部分構(gòu)成： k 位有效信息數(shù)據(jù)和r位CRC校驗碼。其中r 位CRC校驗碼是信息數(shù)據(jù)移位所得序列被一個事先選擇的r + 1位“生成多項式”相除后得

7、到，r 位余數(shù)即為CRC碼的校驗碼，此處的除法就是“模2”除運算,即不考慮進借位3。李曉珍，蘇建峰在循環(huán)冗余校驗CRC 算法分析及實現(xiàn)4中指出，CRC 校驗碼的基本思想是利用線性編碼理論，在發(fā)送端根據(jù)要傳送的k 位二進制碼序列，以一定的規(guī)則產(chǎn)生一個校驗用的監(jiān)督碼(既CRC碼) r 位，并附在信息后邊，構(gòu)成一個新的二進制碼序列數(shù)共位，最后發(fā)送出去。在接收端，則根據(jù)信息碼和CRC 碼之間所遵循的規(guī)則進行檢驗，以確定傳送中是否出錯。CRC 碼是基于模2 除法運算而建立編碼規(guī)律的校驗碼。步驟如下：(1) 用除數(shù)對被除數(shù)最高幾位作模2 減，沒有借位。(2) 除數(shù)右移一位,若余數(shù)最高位為1 ，商為1 ，并

8、對余數(shù)作模2 減。若余數(shù)最高位為0 ，商為0，除數(shù)繼續(xù)右移一位。(3) 一直做到余數(shù)的位數(shù)小于除數(shù)時，該余數(shù)就是最終余數(shù)。接收方將接收到的二進制序列數(shù)(包括信息碼和CRC碼) 除以多項式，如果余數(shù)為0 ，則說明傳輸中無錯誤發(fā)生，否則說明傳輸有誤。用軟件計算CRC 碼時，接收方可以將接收到的信息碼求CRC 碼，比較結(jié)果和接收到的CRC 碼是否相同。伍方輝，方安安在CRC的FPGA設計與實現(xiàn)5中指出16位的CRC碼產(chǎn)生的規(guī)則是先將要發(fā)送的二進制序列數(shù)左移16位后在除以一個多項式,最后所得到的余數(shù)就是CRC碼。如式1所示,B(X)表示二進制列數(shù),G(X)為多項式,Q(X)為整數(shù),R(X)是余數(shù),也就

9、是CRC碼。 (1)以CRC-CCITT為例,數(shù)據(jù)由低位開始串行輸入,逐位移入移位寄存器,并進行相應的模2加法運算(異或運算),如圖1所示。當所有的數(shù)據(jù)移位完成后,留在寄存器中的16位數(shù)就是最終的CRC碼。 楊宏在基于DSP的CRC算法的實現(xiàn)6中指出循環(huán)冗余校驗的過程可簡單描述為:在發(fā)送端,根據(jù)要傳送的k位二進制碼序列,以一定的規(guī)則產(chǎn)生一個校驗用的r位監(jiān)督碼(CRC碼),附在原始信息后邊,構(gòu)成一個新的二進制碼序,CRC碼的格式如圖1所示,共位,然后發(fā)送出去;在接收端,根據(jù)信息碼和CRC碼之間所遵循的規(guī)則進行檢驗,以確定傳送中是否出錯。這種碼的編碼和解碼設備都不太復雜,且檢錯的能力較強。在除法運

10、算中,如果用被除數(shù)除以除數(shù)后所得的余數(shù)不為零,那么從被除數(shù)中減去余數(shù)后,所得結(jié)果可被除數(shù)除盡,循環(huán)冗余校驗正是基于這一思想。唐曉輝,楊雙,李云在一種基于FPGA 的快速CRC算法及實現(xiàn)7指出循環(huán)碼的編碼方法即是由信息碼元和監(jiān)督碼元一起構(gòu)成循環(huán)碼,首先把信息序列分為等長的k 位序列段,每一個信息段附加r 位監(jiān)督碼元,構(gòu)成長度為的循環(huán)碼。循環(huán)碼用表示。這樣新組成的二進制序列要由原序列經(jīng)過運算后得到。表征CRC 循環(huán)的多項式叫生成多項式,原k 位二進制碼加上r 位校驗后,信息位要向左移位( 位) ,這相當于乘上。 被生成多項式除,得整式多項式加上余數(shù)多項式,即，移項得 令 信息多項式 和余數(shù)多項式可

11、以合并成一個新得多項式,稱為循環(huán)多項式,則該多項式是生成多項式得的整數(shù)倍,即能被生成多項式整除。根據(jù)這一原理,在發(fā)送端用信息碼多項式乘上 除以生成多項式所得的余數(shù)多項式就是所要加的監(jiān)督位。在接收端將接收到的循環(huán)碼多項式除以生成多項式 ,若能整除,則說明接收的是正確的信息,否則說明出現(xiàn)錯誤。CRC 被廣泛使用,并且CRC 多項式有多項標準。如CRC - 12 、CRC - 16 、CRC - CCITT、CRC - 32 等, 其中CRC - 16 和CRC - CCITT 產(chǎn)生16 位的CRC 冗余碼,而CRC - 32 則產(chǎn)生的是32 位的CRC 冗余碼,多項式G(x) 的正確選擇對應不同的

12、通信環(huán)境和應用非常關(guān)鍵。2.2 CRC 算法分析2.2.1 直接計算法 直接計算法又可以分為并行計算法和串行計算法,這兩種方法里面又可以用3 種設計思想即矩陣法、代入法和流水線法來設計。并行算法對于高速的通信實時性要求非常強;同時對于長幀結(jié)構(gòu),采用并行算法有利于減少算法時間,但需要嚴格的數(shù)學算法模型。2.2.2 查表法 對于查表法生成CRC 校驗碼,預先計算好所要的全部有效信息位,存放信息位表中,接著按信息位的順序計算好所有校驗位,并存放于表中,待要使用時查表使用。其原理圖如圖2.17所示。圖2.1CRC 查表法原理圖唐曉輝，楊雙，李云在一種基于FPGA 的快速CRC 算法及實現(xiàn)7指出，和計算

13、法相反,查表法生成CRC 校驗碼的優(yōu)點是運算量小、速度快;缺點是需要大量地存儲空間,靈活性不高。但這幾種算法需要的邏輯資源較多,且需要多級組合邏輯的反饋及各種數(shù)學運算,較為復雜,不易實際應用。本設計擬采用模擬人的思維方式進行串行設計,同時減少串行設計所要的時間。其中,，模2 算法后得的余數(shù),判斷余數(shù)高位為0 ,則從 依次后補位位數(shù),直到余數(shù)高位為1 ,接著再進行模2 算法,循環(huán)處理。最后所得余數(shù),如示例中余數(shù)為110 共3 位,得新的信息序列1001100110 。本設計就是利用此算法,可以得出512 比特串行CRC- 32 算法的程序建模,比特型算法是逐位進行運算,效率比并行低,若算法是在C

14、PU 處理器中執(zhí)行,循環(huán)一次運算就要若干個指令時鐘,則不適用于高速通信的場合。數(shù)字通信系統(tǒng)(各種通信標準) 一般是對一幀數(shù)據(jù)進行CRC 校驗,而比特是幀的基本單位。本設計比特串行CRC - 32 算法不在FPGA 嵌入的CPU NIOS 中處理,而是利用FPGA的硬件資源來實現(xiàn),用硬件構(gòu)成多項式除法電路,除法電路的主體由一組移位寄存器和模2 加法器(異或單元) 組成,有效地解決了效率的問題,硬件算法并符合于10M 以太網(wǎng)接入系統(tǒng)的設計。CRC - 32 算法公式如下: 圖2.27為運算仿真輸出的32 位余數(shù)。為方便表示仿真信息位取288bit ,隨機取值為16 進制數(shù)92628CDE8 (后接

15、63 個0) ,余數(shù)為16 進制數(shù)5818EF44 (即圖中二進制值) 。同時經(jīng)過多次信息位位數(shù)變化的仿真,只要更改循環(huán)的次數(shù)j 就可以,滿足要求,移植性強,也符合以太網(wǎng)數(shù)據(jù)幀中數(shù)據(jù)位不斷變化的要求。一幀的時鐘可以根據(jù)所用不同速度等級的器件調(diào)節(jié)為幾十個ns 數(shù)量級,運算速度快,并且算法經(jīng)優(yōu)化,優(yōu)于其他算法。圖2.2CRC 余數(shù)仿真波形由上述的信息位和產(chǎn)生的余數(shù)構(gòu)成的新序列進行解碼仿真,仿真波形如圖2.37所示。圖2.3 余數(shù)為零 當有錯時,余數(shù)不為零。假設最后一位為錯,則余數(shù)為1 ,仿真波形如圖2.47所示。 圖2.4 余數(shù)不為零3 CRC編解碼系統(tǒng)的設計及實現(xiàn) 范綠蓉，栗廣云，吳淑君在基于V

16、HDL 語言的CRC 信道編解碼電路設計與實現(xiàn)8中指出，CRC編譯碼系統(tǒng)包含發(fā)端電路和收端電路兩部份。發(fā)端有信碼發(fā)生器模塊、編碼器模塊，收端有模擬錯碼發(fā)生器模塊、錯碼位置計算模塊、糾錯單元模塊。其中錯碼位置計算單元和糾錯單元合在一起構(gòu)成譯碼器。，其框圖如圖3.18所示。圖3.1 循環(huán)碼編解碼系統(tǒng) 4、總結(jié) 基于FPGA 的CRC 實現(xiàn)方法完全用數(shù)字電路實現(xiàn),具有很高的速度和可靠性,而且可以很方便地與其他功能模塊融合,嵌入到應用系統(tǒng)中,實現(xiàn)片上系統(tǒng)設計,優(yōu)化了電路系統(tǒng)的設計;同時采用模擬人類的思維方式,創(chuàng)建快速、移植性強的串行循環(huán)移位異或運算方式來實現(xiàn)CRC 編解碼的算法,運算速度快,同時簡化了

17、設計的資源,增加了可讀性。參考文獻1 廖海紅。通信系統(tǒng)中的CRC算法的研究和工程實現(xiàn)M 。北京:北京郵電大學,2006.2 馮玉珉，張樹京.通信系統(tǒng)原理M.北京:清華大學出版社,2003.3 王忠，李延社，游智勝. CRC 算法設計與程序?qū)崿F(xiàn)J。電子測量技術(shù),2007,32(12)：26-28.4 李曉珍，蘇建峰.循環(huán)冗余校驗CRC 算法分析及實現(xiàn)J.中國科技信息,2010,(13)，100-101.5 伍方輝,方安安.CRC的FPGA設計與實現(xiàn)M .南京:南昌大學，2008.6 楊宏.基于DSP的CRC算法的實現(xiàn)J .西安郵電學院伍方輝,方安安.CRC的FPGA設計與實現(xiàn)M.南京：南昌大學，

18、2008,(12)：34-38.7 唐曉輝,楊雙,李云.一種基于FPGA的快速CRC算法及實現(xiàn)J .桂林航天工業(yè)高等?？茖W校學報,2009（01）：37-39.8 范綠蓉，栗廣云，吳淑君.基于VHDL語言的CRC信道編解碼電路設計與實現(xiàn)J .湖北華中師范大學,2008：23-26.9 曹志剛.現(xiàn)代通信原理M .北京:清華大學出版社,2006.10 韓進, 程勇, 齊現(xiàn)英.VHDL在數(shù)字集成電路設計中的應用J.山東科技大學學報(自然科學版), 2003,(04):34-37.11 沈世錳,陳魯生.信息論與編碼理論M.北京:科學出版社，2003.12 張平安。16 位循環(huán)冗余校驗碼CRC 的原理和性能分析J.山西科技,2005 ,(5):180-190.13 鄒久朋,林瑤瑤,周建.CRC 校驗編程和硬件快速校驗探討J.單片機與嵌入式系統(tǒng)運用,2009 ,(4)，76-78.14 文謐.CRC校驗的軟件實現(xiàn)J.廣東工業(yè)大學華立學院.2008(27):330-331.15 薛瑞.適用于51 單片機的CRC 算法研究J .北華航天工業(yè)學院學報,2007, (1) :12 - 14.16 劉科峰,張沙清,田豐.EDA技術(shù)在電子設計中的應用J.廣西物理,2004,(02):59-89.17 程學敏,葉兵,孫寧.可糾正單個錯誤的并行CRC解碼器