一種循環(huán)冗余校驗(yàn)碼的設(shè)計(jì)及VHDL語(yǔ)言實(shí)現(xiàn)

尹曉琦

(淮陰工學(xué)院，江蘇 淮安 223003)

0 引言

數(shù)據(jù)通信技術(shù)是計(jì)算機(jī)網(wǎng)絡(luò)技術(shù)發(fā)展的基礎(chǔ)，已經(jīng)成為現(xiàn)代生活中必不可少的一部分。但通過(guò)通信信道傳輸?shù)臄?shù)據(jù)往往會(huì)有差錯(cuò)的產(chǎn)生，而且差錯(cuò)的產(chǎn)生是不可避免的，我們所關(guān)心的是分析差錯(cuò)產(chǎn)生的原因與差錯(cuò)類型，研究檢查是否出現(xiàn)差錯(cuò)及如何糾正差錯(cuò)。循環(huán)冗余碼(CRC)是一種在數(shù)據(jù)通信和數(shù)據(jù)壓縮中廣泛采用的差錯(cuò)控制編碼。循環(huán)冗余校驗(yàn)CRC即Cyclic Redundancy Check，是一種數(shù)字通信中的信道編碼技術(shù)。CRC碼在通訊傳輸中的應(yīng)用范圍十分廣泛，如USB協(xié)議、IEEE802.3標(biāo)準(zhǔn)、IEEE802.11標(biāo)準(zhǔn)、RFID協(xié)議等都采用了CRC作為正確性校驗(yàn)的方法。

1 CRC碼的基本原理

經(jīng)過(guò)CRC方式編碼的串行發(fā)送序列碼，可稱為CRC碼，共由兩部分構(gòu)成:k位有效信息數(shù)據(jù)和r位CRC校驗(yàn)碼，如圖1所示。

圖1 CRC碼結(jié)構(gòu)圖

其中，r位CRC校驗(yàn)碼是通過(guò)k位有效信息序列被一個(gè)事先選擇的r+1位“生成多項(xiàng)式”相除后得到的(r位余數(shù)即是CRC校驗(yàn)碼)，這里的除法是“模2運(yùn)算”。CRC校驗(yàn)碼一般在有效信息發(fā)送時(shí)產(chǎn)生，加在有效信息后被發(fā)送;在接收端，CRC碼用同樣的生成多項(xiàng)式相除，除盡表示無(wú)誤，棄掉r位CRC校驗(yàn)碼，接收有效信息;反之，則表示傳輸出錯(cuò)，糾錯(cuò)或請(qǐng)求重發(fā)。

CRC碼的生成多項(xiàng)式的次數(shù)r就是校驗(yàn)位的個(gè)數(shù)，信息分組的比特?cái)?shù)k并無(wú)特別限制。CRC碼的編碼效率是，一般也是用來(lái)描述CRC碼的效率。通常，較長(zhǎng)的信息分組使用較長(zhǎng)的CRC生成多項(xiàng)式。

CRC碼的編碼結(jié)果有2k種，他們都是g(x)的倍數(shù)。信道中可能發(fā)生的非全0錯(cuò)誤圖樣共有2n－1=2k+r－1種。當(dāng)錯(cuò)誤圖樣能被g(x)整除，也即錯(cuò)誤圖樣本身是一個(gè)碼字時(shí)，這樣的錯(cuò)誤將不會(huì)被接收器發(fā)現(xiàn)，使譯碼器報(bào)告無(wú)錯(cuò)，稱此情況為發(fā)生漏檢。不同的錯(cuò)誤圖樣的個(gè)數(shù)有2n=2k+r個(gè)，其中能被g(x)整除的錯(cuò)誤圖樣的個(gè)數(shù)是2k個(gè)，除去一個(gè)全0錯(cuò)誤圖樣表示無(wú)錯(cuò)外，其余的錯(cuò)誤圖樣都能導(dǎo)致漏檢，這些錯(cuò)誤圖樣的個(gè)數(shù)是2k－1個(gè)，占總錯(cuò)誤圖樣的比例為2k－1/2k+r≈2－r。例如:CRC－16不能檢出的錯(cuò)誤圖樣只占總可能錯(cuò)誤圖樣的1/216，約為六萬(wàn)分之一。在許多應(yīng)用中，出錯(cuò)本身是小概率事件，出錯(cuò)時(shí)錯(cuò)誤圖樣恰好是g(x)的倍數(shù)的概率更小。因而，CRC碼是一個(gè)強(qiáng)有力的檢錯(cuò)碼。CRC碼位數(shù)越長(zhǎng)，則檢錯(cuò)能力也越強(qiáng)。

2 CRC碼的實(shí)現(xiàn)方法

實(shí)際應(yīng)用的過(guò)程一般是在發(fā)送端計(jì)算發(fā)送信息的CRC碼值，并將它作為信息包/幀的一部分傳遞給接收端;接收端將對(duì)接收到的信息進(jìn)行 CRC碼計(jì)算，并與發(fā)送過(guò)來(lái)的CRC碼進(jìn)行比較，從而判斷接收的信息是否正確。CRC碼的計(jì)算實(shí)現(xiàn)可以有多種方法，它可以通過(guò)軟件方式計(jì)算，也可以通過(guò)硬件方式計(jì)算，還可以通過(guò)查表得到。發(fā)送時(shí)，CRC碼的計(jì)算過(guò)程可以在傳輸之前完成，也可以在傳輸過(guò)程中進(jìn)行;對(duì)CRC碼的校驗(yàn)可以在接收的同時(shí)進(jìn)行，也可以在傳輸完成之后進(jìn)行。

CRC碼的計(jì)算可以是按位串行進(jìn)行的，也可以是多位并行進(jìn)行的。CRC碼的產(chǎn)生與檢查可以有兩種方式:計(jì)算法和查表法。對(duì)于硬件實(shí)現(xiàn)來(lái)說(shuō)，查表法沒(méi)有太大的優(yōu)勢(shì)，因?yàn)樗加煤芏嘈酒娣e來(lái)構(gòu)造一個(gè)ROM實(shí)現(xiàn)的表。實(shí)際硬件設(shè)計(jì)中，CRC碼的計(jì)算可以有兩種方式，一種是串行方式，另一種是并行方式。串行方式就是按位產(chǎn)生CRC碼，也就是通過(guò)一個(gè)線性反饋移位寄存器(LFSR)按每次輸入一位的方式來(lái)產(chǎn)生CRC碼。這種方式結(jié)構(gòu)規(guī)則，但每個(gè)時(shí)鐘周期只能計(jì)算1位的結(jié)果，速度較慢。并行方式是每次輸入一組并行數(shù)據(jù)，同時(shí)產(chǎn)生出CRC碼結(jié)果，并行方式處理速度較快。在CRC碼檢查時(shí)也可以有兩種方式，一種是對(duì)要檢查的部分采用與CRC碼產(chǎn)生同樣的方法計(jì)算CRC碼的值，然后看是否與傳輸過(guò)來(lái)的CRC碼相同;另一種是對(duì)接收的所有部分(包括CRC碼)計(jì)算新的CRC碼值，看是否得到預(yù)計(jì)的結(jié)果(余數(shù))。

2.1 CRC生成多項(xiàng)式

在串行數(shù)據(jù)傳輸中廣泛采用循環(huán)冗余校驗(yàn)碼來(lái)測(cè)試一個(gè)數(shù)據(jù)包是否有錯(cuò)誤發(fā)生，雖然循環(huán)冗余校驗(yàn)碼的理論較為復(fù)雜，但實(shí)現(xiàn)檢錯(cuò)的基本原理十分簡(jiǎn)單。在m位信息碼后再拼接r位的校驗(yàn)碼，整個(gè)編碼長(zhǎng)度為n位，因此這種編碼又叫(n，k)碼。對(duì)于一個(gè)給定的(n，k)碼，可以證明存在一個(gè)最高次冪為n－k=r的多項(xiàng)式g(x)。根據(jù)g(x)可以生成k位信息的校驗(yàn)碼，而g(x)叫做這個(gè)碼的生成多項(xiàng)式。CRC檢錯(cuò)碼的檢錯(cuò)能力與其生成多項(xiàng)式g(x)密切相關(guān)。(n，k)循環(huán)碼的生成多項(xiàng)式g(x)的一般形式為:

g(x)的首項(xiàng)系數(shù)為1，末項(xiàng)系數(shù)也必須為1;g(x)的次數(shù)越高，其檢錯(cuò)能力越強(qiáng)。

2.2 CRC碼的生成及校驗(yàn)

校驗(yàn)碼的具體生成過(guò)程為:假設(shè)發(fā)送信息用數(shù)據(jù)多項(xiàng)式m(x)表示，將m(x)左移n－k位，則可表示成m(x)×xn－k，這樣m(x)的右邊就會(huì)空出n－k位，即校驗(yàn)碼的位置，通過(guò) m(x)×xn－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(mén)(x)，則有

在接收端任一組多項(xiàng)式T(x)都應(yīng)被生成多項(xiàng)式g(x)整除，如果傳輸中未發(fā)生錯(cuò)誤，則接收碼元與發(fā)送碼元相同，故接收的碼元必定能被g(x)整除;若碼元在傳輸中發(fā)生錯(cuò)誤，則接收的碼元可能除不盡而有余數(shù)，因此我們就以余數(shù)是否為零來(lái)判斷接收碼元中有無(wú)錯(cuò)誤?？赡苡绣e(cuò)誤的碼元正好也被g(x)整除，這時(shí)校驗(yàn)無(wú)效，但通過(guò)選擇多項(xiàng)式g(x)和增加冗余位數(shù)，使余數(shù)r(x)多項(xiàng)式的位數(shù)增多，來(lái)降低發(fā)生這種錯(cuò)誤的概率。生成多項(xiàng)式應(yīng)該能滿足當(dāng)任何一位發(fā)生傳送錯(cuò)誤時(shí)都能使余數(shù)不為0，并且不同位發(fā)生錯(cuò)誤時(shí)應(yīng)該使余數(shù)也不同，這樣不但能校驗(yàn)錯(cuò)誤，而且能推斷是哪一位出錯(cuò)，從而有利于準(zhǔn)確地糾錯(cuò)。另外，CRC是一種(n，k)循環(huán)碼，能夠檢測(cè)出如下錯(cuò)誤:

(1)突發(fā)長(zhǎng)度l≤n－k的突發(fā)錯(cuò)誤;

(2)大部分突發(fā)長(zhǎng)度l=n－k+1的錯(cuò)誤(不可檢測(cè)到的這類錯(cuò)誤只占2－(n－k－1));

(3)大部分突發(fā)長(zhǎng)度l＞n－k+1的錯(cuò)誤(不可檢測(cè)到的這類錯(cuò)誤只占2－(n－k));

(4)所有與準(zhǔn)用碼組的距離小于dmin的錯(cuò)誤;

(5)所有奇數(shù)個(gè)隨機(jī)錯(cuò)誤。

3 循環(huán)冗余校驗(yàn)CRC碼的設(shè)計(jì)

3.1 CRC校驗(yàn)生成模塊

所設(shè)計(jì)的16位CRC發(fā)生器和校驗(yàn)器，完成12位數(shù)據(jù)附加5位CRC校驗(yàn)碼發(fā)送和接收，系統(tǒng)由2個(gè)模塊組成:CRC校驗(yàn)生成模塊(發(fā)送)和CRC校驗(yàn)檢錯(cuò)模塊(接收)，輸入、輸出都采用并行的CRC校驗(yàn)生成方式。

圖2 CRC校驗(yàn)生成模塊

sdata:12位的待發(fā)送信息;

datald:sdata的裝載信息;

clk:時(shí)鐘信號(hào);

datacrco:附加上5位 CRC校驗(yàn)碼的17位CRC碼，在生成模塊被發(fā)送;

hsend:生成、檢錯(cuò)模塊的握手信號(hào)，協(xié)調(diào)相互之間關(guān)系。

3.2 CRC校驗(yàn)檢錯(cuò)模塊

圖3 CRC校驗(yàn)檢錯(cuò)模塊

datacrci:附加上5位CRC校驗(yàn)碼的17位CRC碼，在檢錯(cuò)模塊被接收;

hrecv:生成、檢錯(cuò)模塊的握手信號(hào)，協(xié)調(diào)相互之間關(guān)系;

clk:時(shí)鐘信號(hào);

datafini:數(shù)據(jù)接收校驗(yàn)完成;

rdata:檢錯(cuò)模塊接收的12位有效信息數(shù)據(jù);

error:誤碼警告信號(hào)。

4 VHDL語(yǔ)言實(shí)現(xiàn)與仿真結(jié)果

本次設(shè)計(jì)的CRC編碼器和解碼器，利用MAX+plusII軟件平臺(tái)，根據(jù)CRC編碼原理，采用硬件描述語(yǔ)言VHDL文本輸入法。為了提高編碼的速度，在設(shè)計(jì)時(shí)采用信息位并行輸入，CRC碼并行輸出的算法。生成多項(xiàng)式為G(x)=x5+x4+x2+1，校驗(yàn)位為5位，有效信息位為12位，最終生成17位CRC碼。部分程序代碼如下:

CRC生成和校驗(yàn)?zāi)K的仿真結(jié)果如圖4所示。從圖4中可以看出，信息碼m(x)為B5D(H)，即 101101011101，生成多項(xiàng)式為 35(H)，即110101。

如果用豎式除法，用去除以，得:

余數(shù) r(x)=x3+x，即1010，就是 CRC校驗(yàn)碼，把它加到信息碼101101011101后面就生成了CRC 碼為 10110101110101010，既 16BAA(H)，這個(gè)碼可以被35(H)除盡，說(shuō)明仿真波形中的編碼和校驗(yàn)結(jié)果是正確的。

圖4 CRC碼的仿真波形圖

5 結(jié)束語(yǔ)

循環(huán)冗余校驗(yàn)CRC(CyclicRedundancyCheck)碼是由分組線性碼的分支而來(lái)，其主要應(yīng)用是二元碼組。編碼和解碼方法簡(jiǎn)單，檢錯(cuò)和糾錯(cuò)能力強(qiáng)且誤判概率很低，在通信領(lǐng)域廣泛用于實(shí)現(xiàn)差錯(cuò)控制。本文設(shè)計(jì)的以EDA設(shè)計(jì)工具M(jìn)AX+PLUSII軟件為基礎(chǔ)，利用VHDL語(yǔ)言設(shè)計(jì)的CRC(17，12)編、解碼器，具有編碼速度快，可靠性高以及易于大規(guī)模集成等優(yōu)點(diǎn)。

［1］陸正福，官金蘭，吳立芝.CRC碼的Simulink仿真實(shí)驗(yàn)［J］.實(shí)驗(yàn)科學(xué)與技術(shù)，2007，5(5):45－48.

［2］唐鵬程，鄒久朋.CRC校驗(yàn)碼在單片機(jī)中的程序?qū)崿F(xiàn)及其冗余碼表的求取［J］.工業(yè)儀表與自動(dòng)化裝置，2004，(3):55－57.

［3］李宥謀，房鼎益.CRC編碼算法研究與實(shí)現(xiàn)［J］.西北大學(xué)學(xué)報(bào):自然科學(xué)版，2006，36(6):895－898.

［4］葉懋，劉宇紅，劉橋.CRC碼的FPGA實(shí)現(xiàn)［J］.重慶工學(xué)院學(xué)報(bào)，2008，21(5):85－87.

［5］黃熙.一種快速循環(huán)冗余校驗(yàn)算法的Verilog實(shí)現(xiàn)［J］.福建電腦，2009，(11):79－80.

［6］徐光輝，程?hào)|旭.基于 FPGA的嵌入式開(kāi)發(fā)與應(yīng)用［M］.北京:電子工業(yè)出版社，2006.

［7］陳榮，陳華.VHDL芯片設(shè)計(jì)［M］.北京:機(jī)械工業(yè)出版社，2006.

［8］樊昌信.通信原理［M］.北京:國(guó)防工業(yè)出版社，2006.