算法及Verilog實(shí)現(xiàn)

1、CRC算法原理及其Verilog實(shí)現(xiàn)1 CRC簡(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語言對(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除四種運(yùn)算。模2運(yùn)算用“+”表示加法運(yùn)算，用“-

2、”、“×”或“.”、“/”分別表示減法、乘法和除法運(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)制除法中，當(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。

3、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=100111 列豎式計(jì)算： 1011 × 101 1011 0000 1011 100111 其中橫線之間的累加過程，采用的是2進(jìn)制加法，不進(jìn)位。4.模2除法： 0/1=0，1/1=1。 舉例如下： 1011/

4、101=10，余數(shù)為100。 列豎式計(jì)算： 10 101 ）1011 101 001 101 001 3 三.CRC實(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碼之間所遵行的規(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ù)

5、即為監(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)制序列1101011101對(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×X0 M(x)= X9+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

6、，并且要求0次冪的系數(shù)為1。根據(jù)以上約束，以及對(duì)糾錯(cuò)能力的要求，人們提出了一些通用的CRC生成多項(xiàng)式，例如：CRC16和CRC32等。 CRC16的生成多項(xiàng)式為：G(x)= X15+X10+X2+1 CRC32的生成多項(xiàng)式為：G(x)= X32+X26+X23+ X22+X16+X12+ X11+X10+X8+ X7+X5+ X4+ X2+X1+11.1 CRC的值等于信息多項(xiàng)式M(x)乘以2n ，再除以生成多項(xiàng)式G(x)所得的余數(shù)，除法采用模2除法。其中，n表示的是生成多項(xiàng)式G（x）的最高次冪，CRC16中n為16，CRC32中n為32。 4 四CRC-32串行計(jì)算公式推導(dǎo) 根據(jù)二進(jìn)制信息碼

7、轉(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+ 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ù)

8、為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) -（公式一） M(x)×232/ G(x) = Q(x) + R(x)/ G(x) -（公式二） 將M(x)中最高次項(xiàng)的系數(shù)Mm作為一個(gè)特殊的M(x)即帶入公式二，即得到公式三： Mm×232/ G(x) = Qm(x) + Rm(x)/ G(x) -（公式三）其中，Mm是一個(gè)只有0次

9、冪的多項(xiàng)式，Mm的值為1。Rm(x)是余數(shù)，是一個(gè)最高次冪為31的多項(xiàng)式。再將公式三代入公式一: 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) = Qm(x)×2m + Rm(x)/ G(x)×2m +Mm-1×2m-1×232/ G(x)+ + M1×21×232/ G(x) + M0×20

10、15;232/ G(x) = Qm(x)×2mRm(x)×2/G(x)×2m-1Mm-1×2m-1×232/ G(x) + + M1×21×232/ G(x) + M0×20×232/ G(x)= Qm(x)×2m + (Rm(x)×2 + Mm-1×232)/ G(x) ×2m-1 + + M1×21×232/ G(x)+ M0×20×232/ G(x) -（公式四）公式四中，設(shè) (Rm(x)×2 + Mm-1&#

11、215;232)/ G(x)= Qm-1(x) + Rm-1(x)/ G(x) -（公式五）再代入到公式四中，那么公式四轉(zhuǎn)化為： M(x)×232/ G(x)= Qm(x)×2m + Qm-1(x)×2m-1 + (Rm-1(x)×2 + Mm-2×232)/ G(x) ×2m-2 + + M1×21×232/ G(x) + M0×20×232/ G(x)以此類推，最終獲得公式： M(x)×232/ G(x)= Qm(x)×2m + Qm-1(x)×2m-1 + Q

12、m-2(x)×2m-2 + + Q1(x)×21 + Q0(x) + R0(x)/G(x) -(公式六)根據(jù)CRC的定義，多項(xiàng)式R0(x)對(duì)應(yīng)的系數(shù)即為我們的CRC32的值。以上推導(dǎo)過程表明：一個(gè)m+1位的二進(jìn)制序列，可以按位求取CRC32的值。運(yùn)算時(shí)，首先從最高位(第m+1位，設(shè)最右邊的為第1位)開始計(jì)算，然后依次計(jì)算較低位。當(dāng)輸入第n個(gè)位(n<m+1)時(shí)，首先將第n+1位運(yùn)算后的結(jié)果乘以2，再將第n的值(0或1)乘以232，兩者相加后除以生成多項(xiàng)式G(x)。因此，每一位的CRC32運(yùn)算就轉(zhuǎn)化成了一個(gè)最高次冪為32的多項(xiàng)式除以一個(gè)最高次冪為32的多項(xiàng)式（生成多項(xiàng)式）

13、，結(jié)果（余數(shù)）為一個(gè)最高次冪不超過31的多項(xiàng)式。 5 五CRC32串行計(jì)算的LFSR實(shí)現(xiàn) 上一節(jié)已經(jīng)推導(dǎo)出了CRC的串行實(shí)現(xiàn)方法，但如何將公式六用Verilog語言表示出來呢？用Verilog描述CRC32的串行計(jì)算方法時(shí)，使用到了一種叫做LFSR（Linear feedback shift register）的結(jié)構(gòu)。下圖為該LFSR的結(jié)構(gòu)圖，其中寄存器3到寄存器25沒有在圖中畫出。 圖1.CRC32的串行移位寄存器實(shí)現(xiàn) 如圖所示，各個(gè)寄存器儲(chǔ)存著上一次CRC32運(yùn)算的結(jié)果，寄存器的輸出即為CRC32的值。讓我們回顧一下CRC32的生成多項(xiàng)式： G(x)= 232+226+223+ 222+2

14、16+212+211+210+28+ 27+25+ 24+ 22+21+1 當(dāng)輸入新的位參與運(yùn)算時(shí)，信息多項(xiàng)式為： M(x)= Mn×232 上一次CRC計(jì)算的結(jié)果為： Rn+1(x) = A31×231+ A30×230+ A29×229+ + A2×22+ A1×21+ A0×1 根據(jù)上一節(jié)推導(dǎo)出的公式，新的CRC32值Rn(x)為Rn+1(x)×2 + M(x)/ G(x)的余數(shù)。設(shè) Q(x) = Rn+1(x)×2 + M(x),則： Q(x) = （A31+ Mn）×232+ A30&

15、#215;231+ A29×230+ +A1×22+ A0×21在計(jì)算Q(x)/ G(x)的結(jié)果時(shí)，根據(jù)模2運(yùn)算法則，如果A31+ Mn的結(jié)果為1，則商為1，余數(shù)為Q(x)- G(x)；如果A31+ Mn的結(jié)果為0，則商為0，余數(shù)為Q(x)本身。其中，A31+ Mn是模2加法，不進(jìn)位；Q(x)- G(x) 模2減法，不借位。根據(jù)以上分析，上圖中的結(jié)構(gòu)剛好能夠完成一位串行輸入的CRC32計(jì)算。當(dāng)上一個(gè)CRC32結(jié)果的最高位A31和輸入的數(shù)值Mn模2加法結(jié)果為1時(shí)，上一次CRC結(jié)果右移一位，完成乘2的過程，再與G(x)多項(xiàng)式的系數(shù)進(jìn)行異或運(yùn)算，完成減法。由于任何數(shù)與0

16、異或保持不變，所以LFSR中只有在G(x)多項(xiàng)式為1的系數(shù)處才放置異或門。運(yùn)算完畢以后把結(jié)果存入寄存器即為新的CRC32值。當(dāng)上一個(gè)CRC32結(jié)果的最高位A31和輸入的數(shù)值Mn模2加法結(jié)果為0時(shí)，Q(x)不夠除，Q(x)本身作為余數(shù)存入寄存器，獲得新的CRC32值。由于A31+ Mn的結(jié)果為0，異或門不起作用，Q(x) = A30×231+ A29×230+ +A1×22+ A0×21，由Rn+1(x) 右移一位獲得, Q(x)的0次冪為0，剛好把A31+ Mn的結(jié)果作為輸入。因此，以上LFSR結(jié)構(gòu)能夠?qū)崿F(xiàn)串行CRC32運(yùn)算，且這種結(jié)構(gòu)很容易在Veril

17、og語言中描述。6 六CRC32串行計(jì)算的Verilog實(shí)現(xiàn) 根據(jù)第五節(jié)中的描述，一位數(shù)據(jù)的CRC32值為：_ crc32_new = crc32_old30:0,1'b0 (32(crc32_old31 datain) & POLYNOMIAL) ;_ 其中，crc32_old為之前存儲(chǔ)在LFSR中的值，可以是上一次計(jì)算的結(jié)果，也可以中第一次計(jì)算時(shí)的初始值。datain表示的是新參與運(yùn)算的一位數(shù)值。POLYNOMIAL是生成多項(xiàng)式的系數(shù)對(duì)應(yīng)的二進(jìn)制序列，POLYNOMIAL=32'h04C11DB7,是個(gè)常數(shù)。上述Verilog語句中，如果crc32_old31dat

18、ain為0，則crc32_new由crc32_old左移一位（即乘以2）后獲得；如果crc32_old31datain為1，在POLYNOMIAL為1的位上，crc32_old30:0,1'b0與1相異或獲得新的CRC32值crc32_new。此語句實(shí)現(xiàn)的邏輯，剛好滿足CRC32的定義，是對(duì)第五節(jié)中提及的LFSR行為的描述。 求一個(gè)二進(jìn)制序列的CRC32值時(shí)，可以讓二進(jìn)制序列的各個(gè)位依次計(jì)算CRC32，最終的結(jié)果即為二進(jìn)制序列的CRC32值。例如一個(gè)長(zhǎng)度為8的二進(jìn)制序列，它的CRC32值為： _ always( * ) begin for(i = 0 ,i<= 7,i = i +

19、1) crc32_new = crc32_old30:0,1'b0 (32(crc32_old31 dataini) & POLYNOMIAL) ; end_ 以上代碼中，datain位寬為8，表示的是一個(gè)寬度為8的二進(jìn)制序列。在以上代碼中，實(shí)現(xiàn)一個(gè)輸入數(shù)據(jù)位寬為8的crc32計(jì)算邏輯。在輸入位寬為1的CRC32計(jì)算邏輯的基礎(chǔ)上，很容易實(shí)現(xiàn)更大輸入位寬的CRC32計(jì)算邏輯。 _博主導(dǎo)讀： 本博文的第二小節(jié)有借鑒網(wǎng)友關(guān)于模2運(yùn)算的文章，原文鏈接：模2運(yùn)算原理，本文關(guān)于模2運(yùn)算的說明比較簡(jiǎn)潔，有需要詳細(xì)了解模2運(yùn)算的朋友可點(diǎn)擊鏈接閱讀原文。另外，本博文的第四節(jié)公式推導(dǎo)過程頗為艱澀，大家可以直接閱讀第四節(jié)末尾結(jié)論部分，無須閱讀推導(dǎo)過程。7