資源描述：
《CRC算法原理及Verilog實(shí)現(xiàn).doc》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。
1、CRC算法原理及其Verilog實(shí)現(xiàn)1CRC簡(jiǎn)介CRC校驗(yàn)是一種在數(shù)據(jù)通信系統(tǒng)和其它串行傳輸系統(tǒng)中廣泛使用的錯(cuò)誤檢測(cè)手段。通用的CRC標(biāo)準(zhǔn)有CRC-8、CRC-16、CRC-32、CRC-CCIT，其中在網(wǎng)絡(luò)通信系統(tǒng)中應(yīng)用最廣泛的是CRC-32標(biāo)準(zhǔn)。本文將以CRC-32為例，說明CRC編碼的實(shí)現(xiàn)方式以及如何用Verilog語(yǔ)言對(duì)CRC編碼進(jìn)行描述。2模2運(yùn)算在說明CRC編碼方式之前，首先介紹一下模2運(yùn)算法則，在CRC運(yùn)算過程中會(huì)使用到模2除法運(yùn)算。模2運(yùn)算是一種二進(jìn)制運(yùn)算法則，與四則運(yùn)算相同，模2運(yùn)算也包括
2、模2加、模2減、模2乘、模2除四種運(yùn)算。模2運(yùn)算用“+”表示加法運(yùn)算，用“-”、“×”或“.”、“/”分別表示減法、乘法和除法運(yùn)算。與普通四則運(yùn)算法則不同的是，模2加法是不帶進(jìn)位的二進(jìn)制加法運(yùn)算，模2減法是不帶借位的二進(jìn)制減法運(yùn)算。同時(shí)，模2乘法在累加中間結(jié)果時(shí)采用的是模2加法運(yùn)算；模2除法求商過程中余數(shù)減除數(shù)采用的是模2減法運(yùn)算。因此，兩個(gè)二進(jìn)制數(shù)進(jìn)行模2加減法運(yùn)算時(shí)，相當(dāng)于兩個(gè)二進(jìn)制數(shù)進(jìn)行按位異或運(yùn)算，每一位的結(jié)果只與兩個(gè)數(shù)的當(dāng)前位有關(guān)。模2除法在確定商時(shí)，與普通二進(jìn)制除法也略有區(qū)別。普通二進(jìn)制除法中，
3、當(dāng)余數(shù)小于除數(shù)時(shí)，當(dāng)前位的商為0，當(dāng)余數(shù)大于等于除數(shù)時(shí)，當(dāng)前位的商為1。模2除法在確定當(dāng)前位的商時(shí)，只關(guān)心余數(shù)的首位，首位為1則商為1，首位為0則商為0。1.模2加法的定義：0+0=0，0+1=1，1+0=1，1+1=0。舉例如下：1010+0110=1100。2.模2減法的定義：0-0=0，0-1=1，1-0=1，1-1=0。舉例如下：1010-0110=1100。3.模2乘法的定義：0×0=0，0×1=0，1×0=0，1×1=1。舉例如下：1011×101=列豎式計(jì)算：1011×101——————101
4、100001011——————其中橫線之間的累加過程，采用的是2進(jìn)制加法，不進(jìn)位。4.模2除法：0/1=0，1/1=1。舉例如下：1011/101=10，余數(shù)為100。列豎式計(jì)算：10————101）1011101————001101————0011CRC實(shí)現(xiàn)原理CRC校驗(yàn)的基本思想是：利用線性編碼理論，在發(fā)送端根據(jù)要發(fā)送的k位二進(jìn)制碼序列，以一定的規(guī)則產(chǎn)生一個(gè)校驗(yàn)用的r位監(jiān)督碼（即CRC碼），并附在信息碼后面，構(gòu)成一個(gè)新的共k+r位的二進(jìn)制碼序列，最后發(fā)送出去。在接受端，則根據(jù)信息碼和CRC碼之間所遵行的
5、規(guī)則進(jìn)行校驗(yàn)，以確定傳輸過程中是否出錯(cuò)，并糾錯(cuò)。一般而言，監(jiān)督碼的位寬r越大，糾錯(cuò)能力就越高，例如，CRC32的糾錯(cuò)能力比CRC16要強(qiáng)。CRC校驗(yàn)獲得監(jiān)督碼的方式是，將k位信息碼轉(zhuǎn)換成多項(xiàng)式，然后除以一個(gè)生成多項(xiàng)式，獲得余數(shù)即為監(jiān)督碼。在求解一個(gè)k位二進(jìn)制信息碼的CRC之前，首先需要將二進(jìn)制信息碼轉(zhuǎn)換成多項(xiàng)式。一個(gè)二進(jìn)制數(shù)序列的各個(gè)位是它對(duì)應(yīng)多項(xiàng)式的系數(shù)，例如，二進(jìn)制序列對(duì)應(yīng)的多項(xiàng)式為：M(x)=1×X9+1×X8+0×X7+1×X6+0×X5+1×X4+1×X3+1×X2+0×X1+1×X0M(x)=X
6、9+X8+X6+X4+X3+X2+1通過這種轉(zhuǎn)換方式獲得的多項(xiàng)式稱為信息多項(xiàng)式。在進(jìn)行CRC計(jì)算時(shí)，除了信息多項(xiàng)式之外，還需要有一個(gè)生成多項(xiàng)式G(x)。生成多項(xiàng)式G(x)要求次數(shù)大于0，并且要求0次冪的系數(shù)為1。根據(jù)以上約束，以及對(duì)糾錯(cuò)能力的要求，人們提出了一些通用的CRC生成多項(xiàng)式，例如：CRC16和CRC32等。CRC16的生成多項(xiàng)式為G(x)=X15+X10+X2+1CRC32的生成多項(xiàng)式為：G(x)=X32+X26+X23+X22+X16+X12+X11+X10+X8+X7+X5+X4+X2+X1+
7、11.1CRC的值等于信息多項(xiàng)式M(x)乘以2n，再除以生成多項(xiàng)式G(x)所得的余數(shù)，除法采用模2除法。其中，n表示的是生成多項(xiàng)式G（x）的最高次冪，CRC16中n為16，CRC32中n為32。1CRC-32串行計(jì)算公式推導(dǎo)根據(jù)二進(jìn)制信息碼轉(zhuǎn)換成多項(xiàng)式的方法，對(duì)于任意一個(gè)長(zhǎng)度為（m+1）的二進(jìn)制信息碼，可以轉(zhuǎn)換成一個(gè)最高次冪為m的多項(xiàng)式：M(x)=Mm×Xm+Mm-1×Xm-1+…+M1×X1+M0×X0將以上公式中的X置換成2，表示是一個(gè)二進(jìn)制的多項(xiàng)式，那么該多項(xiàng)式的系數(shù)只能是1和0。M(x)=Mm×2m
8、+Mm-1×2m-1+…+M1×21+M0×20為求此二進(jìn)制序列的CRC值，首先將M(x）乘以232，然后再除以生成多項(xiàng)式G（x），所得余數(shù)即為CRC32的值。G（x）亦為一個(gè)二進(jìn)制多項(xiàng)式。設(shè)除法運(yùn)算獲得的商為Q(x),余數(shù)為R（x），那么：M(x)×232/G(x)=Mm×2m×232/G(x)+Mm-1×2m-1×232/G(x)+…+M1×21×232/G(x)+M0×20×232/G(x)--------
