32位CRC校驗碼課程設(shè)計

1、32位CRC校驗碼課程設(shè)計摘要：通過對CRC校驗碼原理的分析,研究了一種并行32位CRC算法。該算法 采用遞推的方法,直接得出計算多位數(shù)據(jù)后的CRC余數(shù)與計算前余數(shù)之間的邏輯 關(guān)系。相對于一般的按位串行計算或者查表并行計算的方法來說,該方法運算速 度快且不需要額外的空間存儲余數(shù)表，十分有利于硬件實現(xiàn)。概述：在數(shù)字通信系統(tǒng)中可靠與快速往往是一對矛盾。若要求快速，則必然 使得每個數(shù)據(jù)碼元所占地時間縮短、波形變窄、能量減少，從而在受到干擾后產(chǎn) 生錯誤地可能性增加，傳送信息地可靠性下降。若是要求可靠，則使得傳送消息 地速率變慢。因此，如何合理地解決可靠性也速度這一對矛盾，是正確設(shè)計一個 通信系統(tǒng)地關(guān)鍵

2、問題之一。為保證傳輸過程的正確性，需要對通信過程進行差錯 控制。差錯控制最常用的方法是自動請求重發(fā)方式（ARQ）、向前糾錯方式（FEC） 和混合糾錯（HEC）。在傳輸過程誤碼率比較低時，用FEC方式比較理想。在傳輸 過程誤碼率較高時，采用FEC容易出現(xiàn)“亂糾”現(xiàn)象HEC方式則式ARQ和FEC的結(jié) 合。在許多數(shù)字通信中，廣泛采用AR Q方式，此時的差錯控制只需要檢錯功能。 實現(xiàn)檢錯功能的差錯控制方法很多，傳統(tǒng)的有：奇偶校驗、校驗和檢測、重復(fù)碼 校驗、恒比碼校驗、行列冗余碼校驗等，這些方法都是增加數(shù)據(jù)的冗余量，將校 驗碼和數(shù)據(jù)一起發(fā)送到接受端。接受端對接受到的數(shù)據(jù)進行相同校驗，再將得到 的校驗碼和

3、接受到的校驗碼比較，如果二者一致則認(rèn)為傳輸正確。但這些方法都 有各自的缺點，誤判的概率比較高。循環(huán)冗余校驗CRCCCyclic Redundancy Check） 是由分組線性碼的分支而來，其主要應(yīng)用是二元碼組。編碼簡單且誤判概率很低， 在通信系統(tǒng)中得到了廣泛的應(yīng)用。下面重點介紹了CRC校驗的原理及其算法實現(xiàn)。一、CRC原理分析計算機系統(tǒng)中的數(shù)據(jù)，在進行讀、寫或者傳輸時可能產(chǎn)生錯誤，為了減少和避 免錯誤的產(chǎn)生，一方面可以通過對特定電路的精心設(shè)計，提高電路的穩(wěn)定性和可 靠性;另一方面則是對數(shù)據(jù)采用某種編碼，通過少量的附加電路，使之能發(fā)現(xiàn)某些 錯誤,甚至能確定出錯位置，進而實現(xiàn)自動改錯的功能。CR

4、C（循環(huán)冗余碼）就是一 種常用的錯誤檢測碼，它可以發(fā)現(xiàn)并糾正數(shù)據(jù)存儲或傳輸過程中連續(xù)出現(xiàn)的多位 錯誤，因此在介質(zhì)存儲和網(wǎng)絡(luò)通信方面得到了廣泛的應(yīng)用。隨著技術(shù)的發(fā)展，數(shù)據(jù) 存儲和傳輸速度大大提高,在一些高速的場合如usb2.0或者快速以太網(wǎng)中，傳統(tǒng) 的串行CRC算法已不能滿足速度上的要求，而必須采用速度更快的并行算法。CRC校驗的基本思路是利用線性碼原理，對需要進行傳輸?shù)脑糼位二進制 數(shù)據(jù)按照一定的規(guī)則處理，產(chǎn)生一個r位的校驗碼并附加在原始數(shù)據(jù)后面,形成 一個k + r位的二進制數(shù)據(jù),最后一起發(fā)送出去。首先,可將待編碼的k位數(shù)據(jù)表示成多項式M（X） = * 1 Xi + 樵 2Xk-2 +.

5、+ CXi +. + C1 X + C0其中為C 0或者1。對于r位CRC來說，校驗碼產(chǎn)生的過程為：i將M (X)左移r位，然后除以一個稱為生成多項式的G (X),所得余數(shù)就是CRC校 驗碼。這里，生成多項式G(X)是一個r+1位的多項式。用公式表示如下：M (X ) xr / /G (X)其中Q(X)為商，在3RC的計算過程中不需要關(guān)注，R(x)為余數(shù)，就是需要的CRC 碼。CRC的計算使用的是模2運算，即不帶進位和借位的按位加減，這在邏輯上等 同于異或運算。串行32位的CRC算法設(shè)Cj x3i + Cj x30 + Cjx + Cj = x32(d xk-i + d xk-2 + d )m

6、od G(x)313010k-1k - 20為計算前的CRC多項式，為生成多項式G(x)的第i位系數(shù)。則新讀入一位數(shù)據(jù)d后，x 32( d xk-1 + d xk-2 + . + d xi + d x + d )mod G (x)=x 33( d xk-1 + d xk-2 + d xi + d )mod G (x) + x32d mod G (x)=(Cj + gCj)x31 + (Cj + g Cj)x30 + (Cj + gCj)x + TOC o 1-5 h z 301 312930 3101 31g Cj + g dx31 + g dx30 + g dx + g d = g (Cj

7、+ d) 0 31313010031+礦Cj + g (Cj + d)xi i-1i 31i=1若記Cj+1 x31 + Cj+1 x30 + + Cj+1 + Cj+1 = x32 (d xk-1 + d xk - 2 + +d xi + d x + d )mod G(x)為計算一位數(shù)據(jù)d后的CRC碼多項式，則可得：Cj+1 = Cj + g (Cj + d ) i e 1,31 ii-1i 310式(1)給出了讀入一位數(shù)據(jù)后新的CRC碼Cj+1與原來的Cj之間的邏輯關(guān)系。 ii采用這種算法，當(dāng)原始數(shù)據(jù)依次輸入完畢后，32位寄存器內(nèi)的值就是最后的CRC碼。這種算法無需在原始數(shù)據(jù)后添加32位0

8、進行計算。二、并行32位CRC算法串行算法一個時鐘周期內(nèi)只能處理一位數(shù)據(jù)，在某些高速場合只能靠提高時 鐘頻率來達到所需的速度要求，這增加了開發(fā)的難度和成本，因此提出7CRC的 并行算法。并行CRC算法一次讀入多位數(shù)據(jù)，通過當(dāng)前余數(shù)與讀入數(shù)據(jù)的運算， 得出新的余數(shù)。顯然，一個時鐘周期處理n位數(shù)據(jù)的并行算法在計算結(jié)果上與串 行算法處理n個時鐘周期所得的余數(shù)應(yīng)該相同。基于這一點，采用遞推的方法可 由串行算法導(dǎo)出并行算法計算前后余數(shù)之間的邏輯關(guān)系。下面以4位CRC - 32并 行算法為例，說明推導(dǎo)的過程。CRC-32的生成多項式G(x)為：X32 + X26 + X23 + % 22 + %16 +

9、X12 + %11 + X10 + X 8 + X 7 + X 5 + X 4 + X 2 + X + 1轉(zhuǎn)換成二進制序列就是100000100110000010001110110110111為了便于表達，記為： TOC o 1-5 h z g g g g g3231210(2) 其中，gj對應(yīng)于生成多項式的系數(shù)，取0或者1。定義為計算了第位數(shù)據(jù)后所得CRC值的第i位，d，d，d，d，d，d，d， 7654321d為讀入的數(shù)據(jù)順序，最初時的CRC值為：C0，C0，Co，C0，C0，C0。 0313029210基本思想就是連續(xù)套用式(1)給出的串行公式8次，以期得到處理8位數(shù)據(jù)后C8i與C0和d

10、，d，d，d，d，d，d，d之間的邏輯關(guān)系。推導(dǎo)過程如下： i76543210C8= C7+ d= C6 + g(C6+ d ) + d031030313110=C1 + g (C1 + d ) + d 25263160=C0 + C0 + d + dC8 = C7 + g (C7 + d ) = C7 + C0 + C0 + d + d 1013100243060=C0 + C0 + d + d + C0 + C0 + d + d253171243060C8 = C; + g2(q + d0)=C0 + C0 + C0 + C0 + C0 + d + d + d + d + d2425263

11、03176210C3 = C; + g3(C；+ d0)C o + C o + C o + C o + d + d + d + d TOC o 1-5 h z 252627317321C8 C; + gC + d)C0 +C0 + C0 + C0 + C0 + d + d + d + d + d242627283064320C8C7 +g (C7+d)Co +g (Co +d)+g (C2 +d)+g (C3 +d)+g (C4 +d)=C0 +C0 +C0 +C0 +C0 +d +d +d +d272829317543C8 =C +g (C +d)1516 310=C0 + g C +d)+

12、g (C3 +d)+g (C2 +d)+g (G +d)16 31012 31411 31510 316=C +C0 +C +C +d +d +d242829540C8 =C + g (C +d)1617 310=C0 + g (C6 +d)+g (C2 +d)+g (C1 +d)+g (C0 +d)16 31112 31511 31610 317=C +C +C +C +d +d +d9252930651C8 = C + g (C7 + d ) 292829310=Co + g(C4+ d) + g(Ci+ d ) + g (C。+ d)263132331622317=C0 + C0 + C

13、0 + C0 + d + d + d273031763C8 = C7 + g (C7 + d ) 302930310=C0 + g (C3 + d ) + g (C0 + d )2631423317C0 + C0 + C0 + d + d283174C8 C7 + g (C7 + d ) 313031310C0 + g(C2 + d )26315C 0 + C 0 + d317以上推導(dǎo)結(jié)果表明，計算8位數(shù)據(jù)后的CRC值可由當(dāng)前CRC值與輸入數(shù)據(jù)的異或組 合來表示，這為并行CRC的實現(xiàn)提供了理論基礎(chǔ)。三、并行CRC-32算法的一些改進及模塊的設(shè)計思路當(dāng)接收端收到包含CRC校驗的數(shù)據(jù)包時,用與發(fā)送

14、端同樣的生成多項式再次 計算CRC值，如果數(shù)據(jù)在傳輸過程中沒有發(fā)生錯誤，則計算的結(jié)果應(yīng)該為0。這在 通常情況下是正確的?，F(xiàn)在考慮兩種特殊的情況，一種是當(dāng)數(shù)據(jù)包的開頭有多余0 出現(xiàn)（或者以連續(xù)0開頭的數(shù)據(jù)丟失了開頭的幾位0），另一種是數(shù)據(jù)包的結(jié)尾有 多余的0出現(xiàn)（或者以連續(xù)0結(jié)尾的數(shù)據(jù)丟失了結(jié)尾的幾位0）。在這兩種情況下, 當(dāng)接收端計算CRC的值為0時,不能確定沒有錯誤發(fā)生,這是因為如果一個數(shù)據(jù)串的CRC計算結(jié)果為0，那么在串頭或者串尾 增加或減少幾位0 ,計算的結(jié)果仍然是0 ,然而數(shù)據(jù)已經(jīng)被改變了。針對這兩種情 況,CRC算法作了相應(yīng)的改動。對于解決串開頭0的問題，可以把32位CRC寄存器的值

15、預(yù)設(shè)為全1 ,相當(dāng)于 把原始數(shù)據(jù)的高32位取反來計算CRC。這樣處理后，如果由于傳輸錯誤在數(shù)據(jù)開 頭出現(xiàn)0的增加或減少，經(jīng)過取反后的數(shù)據(jù)就會與原來的不同，故而達到了錯誤 檢測的目的。由于在數(shù)值上這樣等于給被除數(shù)加上了個常量F，而在CRC的生成 和校驗階段都做這樣的處理，所以在算法上對最終的校驗結(jié)果沒有影響。解決串 結(jié)尾0的問題稍微麻煩點，具體做法是生成CRC碼時將正常計算得出的結(jié)果按位 取反，作為最終的CRC碼附加在數(shù)據(jù)后。校驗時在接收到的數(shù)據(jù)包(包括原始數(shù)據(jù) 和校驗碼)之后添加32個0，計算除以生成多項式的余數(shù)。這時，當(dāng)數(shù)據(jù)傳輸沒 有發(fā)生錯誤時,CRC校驗的結(jié)果不再為0，而是一個常數(shù)，通常被

16、稱為魔數(shù)(magic number)。同樣，當(dāng)出現(xiàn)數(shù)據(jù)結(jié)尾有0的增減錯誤時，計算所得的余數(shù)會發(fā)生變化。 所有校驗結(jié)果不等于這個常數(shù)的數(shù)據(jù)包就被認(rèn)為是出現(xiàn)了錯誤。下面給出32位CRC校驗中這個常量的計算方法：設(shè)M為原始數(shù)據(jù)串,G為生成多項式,R為取反前的余數(shù)，所用的加法均為模2 加法可知(Mx32 + R)mod G = 0現(xiàn)在將日取反，計為REMx2+R)moG=x32Mx2+(R+x3i+x30+. +x+1)mGd =X3#MX2+R)+X31+X30+ +x+1mod=x32(Mx2+R)+X52(x3i+x30+- +x+1)mOd由式(3)可知:x32 (Mx 32 + R) mod

17、 G = 0所以x 32 (Mx32 + R)mod G = x32( x3i + x 30 + x + 1)mod G對于32位CRC校驗的生成多項式來說，這個結(jié)果為0 x704DD70。其代碼是這樣寫的if(i=(INPUT_BYTE-4) Begincrcout=crcout32hFFFFFFFF;crcout= crcout0, crcout1, crcout2, crcout3,crcout4, crcout5, crcout6, crcout7,crcout8, crcout9, crcout10, crcout11,crcout12, crcout13, crcout14, cr

18、cout15,crcout16, crcout17, crcout18, crcout19,crcout20, crcout21, crcout22, crcout23,crcout24, crcout25, crcout26, crcout27, crcout28, crcout29, crcout30, crcout31;end對于CRC-32的校驗碼來說，比較重要的一部分是怎樣控制接收數(shù)據(jù)，并當(dāng)符合條 件時計算CRC，與送過來的校驗碼進行比較，正確的就輸出結(jié)果為1，錯誤的就輸 出結(jié)果為0。代碼如下：if(i(INPUT_BYTE-4)/控制輸入送過來的crc結(jié)果，這個是拿比較用的begi

19、ncrcout=nextCRC32_D8(d,crcout);endelse if(i(INPUT_BYTE)/控制輸入要計算crc的字?jǐn)?shù)begintempcrc=tempcrc23:0,d;endif(tempcrc=crcout)/比較crc結(jié)果是否正確beginresult=1;endelsebeginresult=0;endend其中 INPUT-BYTE=64。四、CRC-32校驗碼生成和校驗碼模塊的設(shè)計生成模塊的功能示意圖如圖1所示圖1 CRC生成示意圖同CRC生成模塊，將32位寄存器初始化為全1 ,然后把接收到的數(shù)據(jù)每時鐘周期 輸入4位,與當(dāng)前寄存器中的數(shù)據(jù)運算，結(jié)果存入32位寄存器作為新的值，當(dāng)所 有數(shù)據(jù)輸入完畢后,與0 xC704DD78比較，得出校驗結(jié)果。電路仿真Current Simulaticn Time: 1QQ5QQ nsns1 1 1 12 ns1 1 1 1 Illi4代1 1 1 1 1 1 1 1EC VI I I I I I I I