|
一．CRC簡介 CRC校驗是一種在數(shù)據(jù)通信系統(tǒng)和其它串行傳輸系統(tǒng)中廣泛使用的錯誤檢測手段。通用的CRC標準有CRC-8、CRC-16、CRC-32、CRC-CCIT，其中在網(wǎng)絡(luò)通信系統(tǒng)中應用最廣泛的是CRC-32標準。本文將以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加減法運算時，相當于兩個二進制數(shù)進行按位異或運算，每一位的結(jié)果只與兩個數(shù)的當前位有關(guān)。模2除法在確定商時，與普通二進制除法也略有區(qū)別。普通二進制除法中，當余數(shù)小于除數(shù)時，當前位的商為0，當余數(shù)大于等于除數(shù)時，當前位的商為1。模2除法在確定當前位的商時，只關(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ù)序列的各個位是它對應多項式的系數(shù)，例如，二進制序列1101011101對應的多項式為： 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串行計算公式推導 根據(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) ={ 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)對應的系數(shù)即為我們的CRC32的值。 以上推導過程表明：一個m+1位的二進制序列，可以按位求取CRC32的值。運算時，首先從最高位(第m+1位，設(shè)最右邊的為第1位)開始計算，然后依次計算較低位。當輸入第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)推導出了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 M(x)= Mn×232 Rn+1(x) = A31×231+ A30×230+ A29×229+ … + A2×22+ A1×21+ A0×1 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計算。當上一個CRC32結(jié)果的最高位A31和輸入的數(shù)值Mn模2加法結(jié)果為1時，上一次CRC結(jié)果右移一位，完成乘2的過程，再與G(x)多項式的系數(shù)進行異或運算，完成減法。由于任何數(shù)與0異或保持不變，所以LFSR中只有在G(x)多項式為1的系數(shù)處才放置異或門。運算完畢以后把結(jié)果存入寄存器即為新的CRC32值。當上一個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_old為之前存儲在LFSR中的值，可以是上一次計算的結(jié)果，也可以中第一次計算時的初始值。datain表示的是新參與運算的一位數(shù)值。POLYNOMIAL是生成多項式的系數(shù)對應的二進制序列，POLYNOMIAL=32'h04C11DB7,是個常數(shù)。上述Verilog語句中，如果crc32_old[31]^datain為0，則crc32_new由crc32_old左移一位（即乘以2）后獲得；如果crc32_old[31]^datain為1，在POLYNOMIAL為1的位上，{crc32_old[30:0],1'b0}與1相異或獲得新的CRC32值crc32_new。此語句實現(xiàn)的邏輯，剛好滿足CRC32的定義，是對第五節(jié)中提及的LFSR行為的描述。
求一個二進制序列的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
以上代碼中，datain位寬為8，表示的是一個寬度為8的二進制序列。在以上代碼中，實現(xiàn)一個輸入數(shù)據(jù)位寬為8的crc32計算邏輯。在輸入位寬為1的CRC32計算邏輯的基礎(chǔ)上，很容易實現(xiàn)更大輸入位寬的CRC32計算邏輯。
博主導讀： 本博文的第二小節(jié)有借鑒網(wǎng)友關(guān)于模2運算的文章，原文鏈接：模2運算原理，本文關(guān)于模2運算的說明比較簡潔，有需要詳細了解模2運算的朋友可點擊鏈接閱讀原文。另外，本博文的第四節(jié)公式推導過程頗為艱澀，大家可以直接閱讀第四節(jié)末尾結(jié)論部分，無須閱讀推導過程。
|
|
|
來自： 灞河之濱 > 《Xilinx應用》
