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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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