數(shù)據(jù)損壞是與數(shù)據(jù)傳輸和存儲有關(guān)的首要問題。只要是在通道上傳輸數(shù)據(jù)，就總會有出現(xiàn)某些錯誤的有限概率。

　　關(guān)鍵是接收模塊要能區(qū)分無錯消息和有錯消息。檢錯有多種方法，其中大多數(shù)都是專門為此目的引入冗余位。數(shù)據(jù)通信中常用的檢錯方法包括奇偶碼、漢明碼和循環(huán)冗余校驗(CRC)，其中CRC使用廣泛。

　　CRC根據(jù)一個給定的數(shù)據(jù)位組算出，然后在傳輸或存儲之前附加到數(shù)據(jù)幀尾部。接收或檢索到幀后，對其內(nèi)容重新計算CRC，以此來驗證其有效性，確保數(shù)據(jù)無誤。

　　本文簡述CRC計算所依據(jù)的原理，并且探討用線性反饋移位寄存器實現(xiàn)其硬件的方法。然后，我們把注意力轉(zhuǎn)向Xilinx?VirtexTM-5 LXT/SXT 器件中存在的 CRC 硬模塊。

　　原理

　　加法和減法運(yùn)算是用模2算法執(zhí)行；也就是說，這兩種運(yùn)算與“異或”(XOR)運(yùn)算相同。除了沒有進(jìn)位，多項式算法中的兩數(shù)相加與普通二進(jìn)制算法中的多數(shù)相加相同。

　　例如：二進(jìn)制消息流11001011表達(dá)為x7+x6+x3+x+1。傳輸點(diǎn)與接收點(diǎn)約定一個固定多項式，稱為生成器多項式；這是CRC計算的關(guān)鍵參數(shù)。

　　將數(shù)據(jù)解釋為一個多項式的系數(shù)，用一個給定的生成器多項式除這些系數(shù)。除得的余數(shù)就是CRC。假設(shè)有一個m位消息序列和一個r階生成器多項式，發(fā)射器創(chuàng)建一個n位 (n=m+r)序列，稱為幀校驗序列 (FCS)，使這個(m+r)位合成幀可以被一個預(yù)先確定的序列整除。

　　發(fā)射器將r個0位附加到m位的消息，并且用生成器多項式除所得 m+r-1階多項式。這樣可得到一個階數(shù)等于或小于(r-1)的余數(shù)多項式。該余數(shù)多項式有r個系數(shù)，這些系數(shù)形成校驗和。將商丟棄。傳輸?shù)臄?shù)據(jù)是原m位消息后附r位校驗和。

　　在接收器上，可以按以下兩種標(biāo)準(zhǔn)方法之一*估所接收數(shù)據(jù)的有效性：

　　對收到的前m個位再次計算校驗和，然后與收到的校驗和（收到的后r個位）進(jìn)行比較。

　　對收到的全部(m+r)個位計算校驗和，然后與一個0余數(shù)進(jìn)行比較。

　　為了說明第二種方法如何得出 0余數(shù)，我們做如下約定：

　　M=消息的多項表達(dá)式

　　R=發(fā)射器上所算得余數(shù)的多項表達(dá)式

　　G=生成器多項式

　　Q=用G除M得到的商

　　傳輸?shù)臄?shù)據(jù)對應(yīng)于多項式 Mxr–R。變量xr表示消息為容納校驗和而產(chǎn)生的一個r位移位。

　　我們知道：Mxr=QG+R

　　在發(fā)射器上將校驗和R附加到消息中相當(dāng)于從消息中減去余數(shù)。于是，傳輸?shù)臄?shù)據(jù)變?yōu)镸xr-R=QG，這顯然是G的倍數(shù)。這就是我們在第二種情況下得到0余數(shù)的過程。

　　不過，這一過程對所傳輸數(shù)據(jù)中首0位和尾0位的個數(shù)不敏感。換句話說，無論消息插入還是刪除尾0位，余數(shù)都保持為0，從而使錯誤漏檢，這表明不會復(fù)原成同樣的位序列。下面介紹一種克服這一缺點(diǎn)的變通辦法。

　　剩余法

　　實際上，校驗和經(jīng)過反演后才附加到消息中。這就使接收器上算出的余數(shù)（超過m+r位）不為0。在這類情況下，接收器上得到的余數(shù)是一個固定值，稱為多項式的剩余值。

　　做一點(diǎn)演算有助于更清楚地說明這一概念。

　　假定%符號在下列表達(dá)式中表示模運(yùn)算。

　　對于未經(jīng)反演附加校驗和的情況：

　　(Mxr–R)xr%G=0

　　在這種情況下，接收器會執(zhí)行與發(fā)射器一樣的移位運(yùn)算。

　　現(xiàn)在，考慮校驗和在發(fā)射器上經(jīng)反演后附加到消息流的情況： (Mxr–Rc)xr% G

　　其中，Rc表示經(jīng)過反演的校驗和。

　　還可以將其寫成：(Mxr– R +(xr-1+...+x+ 1)) xr% G

　　一個位的反碼與其對1異或運(yùn)算的結(jié)果相同。這里的+號表示模2算法中的加法（另請注意，在模2算法中，加法和減法運(yùn)算相同）。

　　在這種情況下，余數(shù)與以下表達(dá)式相同：(xr-1+...+x+1) xr% G

　　對于給定的生成器多項式來說，此表達(dá)式的計算結(jié)果將是一個常數(shù)。

　　常用的CRC 32生成器多項式是G(x) = x32+x26+x23+x22+x16+x12+x11+x10+x8+x7+x5+x4+x2+x+1

　　該式在十六進(jìn)制中是04C11DB7。

　　與CRC-32對應(yīng)的常數(shù)剩余值在十六進(jìn)制中是C704DD7B。對于給定的生成器多項式G來說，無論在輸入端提供何種數(shù)據(jù)樣式，剩余值仍為常數(shù)。

　　硬件實現(xiàn)

　　CRC校驗和的計算是多項式除法過程。在硬件中實現(xiàn)該過程需要使用一個移位寄存器（亦稱CRC寄存器）。該移位寄存器的長度與生成器多項式的階數(shù)相同。

　　CRC 計算過程如下：

　　1.初始化CRC寄存器。

　　2.持續(xù)獲取消息位，直到獲得所有消息位。如果CRC寄存器中的高階位是1，則向左移一位，并且將其結(jié)果與G進(jìn)行異或運(yùn)算。否則，僅向左移一位。