一．CRC簡介
CRC校驗是一種在數(shù)據(jù)通信系統(tǒng)和其它串行傳輸系統(tǒng)中廣泛使用的錯誤檢測手段。通用的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編碼的實現(xiàn)方式以及如何用verilog語言對CRC編碼進行描述。
二．模2運算
在說明CRC編碼方式之前，首先介紹一下模2運算法則，在CRC運算過程中會使用到模2除法運算。模2運算是一種二進制運算法則，與四則運算相同，模2運算也包括模2加、模2減、模2乘、模2除四種運算。模2運算用“+”表示加法運算，用“-”、“×”或“.”、“/”分別表示減法、乘法和除法運算。與普通四則運算法則不同的是，模2加法是不帶進位的二進制加法運算，模2減法是不帶借位的二進制減法運算。同時，模2乘法在累加中間結(jié)果時采用的是模2加法運算；模2除法求商過程中余數(shù)減除數(shù)采用的是模2減法運算。因此，兩個二進制數(shù)進行模2加減法運算時，相當(dāng)于兩個二進制數(shù)進行按位異或運算，每一位的結(jié)果只與兩個數(shù)的當(dāng)前位有關(guān)。模2除法在確定商時，與普通二進制除法也略有區(qū)別。普通二進制除法中，當(dāng)余數(shù)小于除數(shù)時，當(dāng)前位的商為0，當(dāng)余數(shù)大于等于除數(shù)時，當(dāng)前位的商為1。模2除法在確定當(dāng)前位的商時，只關(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=100111
列豎式計算：
1011
× 101
——————
1011
0000
1011
——————
100111
其中橫線之間的累加過程，采用的是2進制加法，不進位。
4.模2除法：
0/1=0，1/1=1。
舉例如下：
1011/101=10，余數(shù)為100。
列豎式計算：
10
————
101 ）1011
101
————
001
101
————
001
三.CRC實現(xiàn)原理
CRC校驗的基本思想是：利用線性編碼理論，在發(fā)送端根據(jù)要發(fā)送的k位二進制碼序列，以一定的規(guī)則產(chǎn)生一個校驗用的r位監(jiān)督碼（即CRC碼），并附在信息碼后面，構(gòu)成一個新的共k+r位的二進制碼序列，最后發(fā)送出去。在接受端，則根據(jù)信息碼和CRC碼之間所遵行的規(guī)則進行校驗，以確定傳輸過程中是否出錯，并糾錯。一般而言，監(jiān)督碼的位寬r越大，糾錯能力就越能，例如，CRC32的糾錯能力比CRC16要強。CRC校驗獲得監(jiān)督碼的方式是，將k位信息碼轉(zhuǎn)換成多項式，然后除以一個生成多項式，獲得余數(shù)即為監(jiān)督碼。
在求解一個k位二進制信息碼的CRC之前，首先需要將二進制信息碼轉(zhuǎn)換成多項式。一個二進制數(shù)序列的各個位是它對應(yīng)多項式的系數(shù)，例如，二進制序列1101011101對應(yī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)換方式獲得的多項式稱為信息多項式。在進行CRC計算時，除了信息多項式之外，還需要有一個生成多項式G(x)。生成多項式G(x)要求次數(shù)大于0，并且要求0次冪的系數(shù)為1。根據(jù)以上約束，以及對糾錯能力的要求，人們提出了一些通用的CRC生成多項式，例如：CRC16和CRC32等。
CRC16的生成多項式為：G(x)= X15+X10+X2+1
CRC32的生成多項式為：G(x)= X32+X26+X23+ X22+X16+X12+ X11+X10+X8+ X7+X5+ X4+ X2+X1+1
CRC的值等于信息多項式M(x)乘以2n ，再除以生成多項式G(x)所得的余數(shù)，除法采用模2除法。其中，n表示的是生成多項式G（x）的最高次冪，CRC16中n為16，CRC32中n為32。
四．CRC-32串行計算公式推導(dǎo)
根據(jù)二進制信息碼轉(zhuǎn)換成多項式的方法，對于任意一個長度為（m+1）的二進制信息碼，可以轉(zhuǎn)換成一個最高次冪為m的多項式：
M(x)= Mm×Xm+ Mm-1×Xm-1+ … + M1×X1+ M0×X0
將以上公式中的X置換成2，表示是一個二進制的多項式，那么該多項式的系數(shù)只能是1和0。
M(x)= Mm×2m+ Mm-1×2m-1+ … + M1×21+ M0×20
為求此二進制序列的CRC值，首先將M(x）乘以232，然后再除以生成多項式G（x），所得余數(shù)即為CRC32的值。G（x）亦為一個二進制多項式。設(shè)除法運算獲得的商為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)
--------（公式一）
M(x)×232/ G(x) = Q(x) + R(x)/ G(x) --------（公式二）
將M(x)中最高次項的系數(shù)Mm作為一個特殊的M(x)即帶入公式二，即得到公式三：
Mm×232/ G(x) = Qm(x) + Rm(x)/ G(x) --------（公式三）
其中，Mm是一個只有0次冪的多項式，Mm的值為1。Rm(x)是余數(shù)，是一個最高次冪為31的多項式。再將公式三代入公式一:
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×232/ G(x)
= Qm(x)×2m + {Rm(x)×2/G(x)×2m-1 + Mm-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×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 + Qm-2(x)×2m-2 + … + Q1(x)×21
+ Q0(x) + R0(x)/G(x)
--------(公式六)
根據(jù)CRC的定義，多項式R0(x)對應(yīng)的系數(shù)即為我們的CRC32的值。
以上推導(dǎo)過程表明：一個m+1位的二進制序列，可以按位求取CRC32的值。運算時，首先從最高位(第m+1位，設(shè)最右邊的為第1位)開始計算，然后依次計算較低位。當(dāng)輸入第n個位(n<m+1)時，首先將第n+1位運算后的結(jié)果乘以2，再將第n的值(0或1)乘以232，兩者相加后除以生成多項式G(x)。因此，每一位的CRC32運算就轉(zhuǎn)化成了一個最高次冪為32的多項式除以一個最高次冪為32的多項式（生成多項式），結(jié)果（余數(shù)）為一個最高次冪不超過31的多項式。
五．CRC32串行計算的LFSR實現(xiàn)
上一節(jié)已經(jīng)推導(dǎo)出了CRC的串行實現(xiàn)方法，但如何將公式六用Verilog語言表示出來呢？用Verilog描述CRC32的串行計算方法時，使用到了一種叫做LFSR（Linear feedback shift register）的結(jié)構(gòu)。下圖為該LFSR的結(jié)構(gòu)圖，其中寄存器3到寄存器25沒有在圖中畫出。
圖1.CRC32的串行移位寄存器實現(xiàn)
如圖所示，各個寄存器儲存著上一次CRC32運算的結(jié)果，寄存器的輸出即為CRC32的值。讓我們回顧一下CRC32的生成多項式：
G(x)= 232+226+223+ 222+216+212+211+210+28+ 27+25+ 24+ 22+21+1
當(dāng)輸入新的位參與運算時，信息多項式為：
M(x)= Mn×232
上一次CRC計算的結(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×231+ A29×230+ … +A1×22+ A0×21
在計算Q(x)/ G(x)的結(jié)果時，根據(jù)模2運算法則，如果A31+ Mn的結(jié)果為1，則商為1，余數(shù)為Q(x)- G(x)；如果A31+ Mn的結(jié)果為0，則商為0，余數(shù)為Q(x)本身。其中，A31+ Mn是模2加法，不進位；Q(x)- G(x) 模2減法，不借位。
根據(jù)以上分析，上圖中的結(jié)構(gòu)剛好能夠完成一位串行輸入的CRC32計算。當(dāng)上一個CRC32結(jié)果的最高位A31和輸入的數(shù)值Mn模2加法結(jié)果為1時，上一次CRC結(jié)果右移一位，完成乘2的過程，再與G(x)多項式的系數(shù)進行異或運算，完成減法。由于任何數(shù)與0異或保持不變，所以LFSR中只有在G(x)多項式為1的系數(shù)處才放置異或門。運算完畢以后把結(jié)果存入寄存器即為新的CRC32值。當(dāng)上一個CRC32結(jié)果的最高位A31和輸入的數(shù)值Mn模2加法結(jié)果為0時，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運算，且這種結(jié)構(gòu)很容易在Verilog語言中描述。
六．CRC32串行計算的Verilog實現(xiàn)
根據(jù)第五節(jié)中的描述，一位數(shù)據(jù)的CRC32值為：
crc32_new = {crc32_old[30:0],1'b0} ^ ({32{(crc32_old[31] ^ datain)}} & POLYNOMIAL) ;
求一個二進制序列的CRC32值時，可以讓二進制序列的各個位依次計算CRC32，最終的結(jié)果即為二進制序列的CRC32值。例如一個長度為8的二進制序列，它的CRC32值為：
always@( * )
begin
for(i = 0 ,i<= 7,i = i +1)
crc32_new = {crc32_old[30:0],1'b0} ^ ({32{(crc32_old[31] ^ datain[i])}} & POLYNOMIAL) ;
end
博主導(dǎo)讀： 本博文的第二小節(jié)有借鑒網(wǎng)友關(guān)于模2運算的文章，原文鏈接：模2運算原理，本文關(guān)于模2運算的說明比較簡潔，有需要詳細了解模2運算的朋友可點擊鏈接閱讀原文。另外，本博文的第四節(jié)公式推導(dǎo)過程頗為艱澀，大家可以直接閱讀第四節(jié)末尾結(jié)論部分，無須閱讀推導(dǎo)過程。
相關(guān)閱讀：1.V6 CRC使用注意事項
聯(lián)系客服
