|
數據損壞是與數據傳輸和存儲有關的首要問題。只要是在通道上傳輸數據，就總會有出現某些錯誤的有限概率。 關鍵是接收模塊要能區分無錯消息和有錯消息。檢錯有多種方法，其中大多數都是專門為此目的引入冗余位。數據通信中常用的檢錯方法包括奇偶碼、漢明碼和循環冗余校驗(CRC)，其中CRC使用最廣泛。 CRC根據一個給定的數據位組算出，然后在傳輸或存儲之前附加到數據幀尾部。接收或檢索到幀后，對其內容重新計算CRC，以此來驗證其有效性，確保數據無誤。 本文簡述CRC計算所依據的原理，并且探討用線性反饋移位寄存器實現其硬件的方法。然后，我們把注意力轉向Xilinx?VirtexTM-5 LXT/SXT 器件中存在的 CRC 硬模塊。 原理 加法和減法運算是用模2算法執行；也就是說，這兩種運算與“異或”(XOR)運算相同。除了沒有進位，多項式算法中的兩數相加與普通二進制算法中的多數相加相同。 例如：二進制消息流11001011表達為x7+x6+x3+x+1。傳輸點與接收點約定一個固定多項式，稱為生成器多項式；這是CRC計算的關鍵參數。 將數據解釋為一個多項式的系數，用一個給定的生成器多項式除這些系數。除得的余數就是CRC。假設有一個m位消息序列和一個r階生成器多項式，發射器創建一個n位 (n=m+r)序列，稱為幀校驗序列 (FCS)，使這個(m+r)位合成幀可以被一個預先確定的序列整除。 發射器將r個0位附加到m位的消息，并且用生成器多項式除所得 m+r-1階多項式。這樣可得到一個階數等于或小于(r-1)的余數多項式。該余數多項式有r個系數，這些系數形成校驗和。將商丟棄。傳輸的數據是原m位消息后附r位校驗和。 在接收器上，可以按以下兩種標準方法之一評估所接收數據的有效性： 對收到的前m個位再次計算校驗和，然后與收到的校驗和（收到的后r個位）進行比較。 對收到的全部(m+r)個位計算校驗和，然后與一個0余數進行比較。 為了說明第二種方法如何得出 0余數，我們做如下約定： M=消息的多項表達式 R=發射器上所算得余數的多項表達式 G=生成器多項式 Q=用G除M得到的商 傳輸的數據對應于多項式 Mxr–R。變量xr表示消息為容納校驗和而產生的一個r位移位。 我們知道：Mxr=QG+R 在發射器上將校驗和R附加到消息中相當于從消息中減去余數。于是，傳輸的數據變為Mxr-R=QG，這顯然是G的倍數。這就是我們在第二種情況下得到0余數的過程。 不過，這一過程對所傳輸數據中首0位和尾0位的個數不敏感。換句話說，無論消息插入還是刪除尾0位，余數都保持為0，從而使錯誤漏檢，這表明不會復原成同樣的位序列。下面介紹一種克服這一缺點的變通辦法。 剩余法 實際上，校驗和經過反演后才附加到消息中。這就使接收器上算出的余數（超過m+r位）不為0。在這類情況下，接收器上得到的余數是一個固定值，稱為多項式的剩余值。 做一點演算有助于更清楚地說明這一概念。 假定%符號在下列表達式中表示模運算。 對于未經反演附加校驗和的情況： (Mxr–R)xr%G=0 在這種情況下，接收器會執行與發射器一樣的移位運算。 現在，考慮校驗和在發射器上經反演后附加到消息流的情況： (Mxr–Rc)xr% G 其中，Rc表示經過反演的校驗和。 還可以將其寫成：(Mxr– R +(xr-1+...+x+ 1)) xr% G 一個位的反碼與其對1異或運算的結果相同。這里的+號表示模2算法中的加法（另請注意，在模2算法中，加法和減法運算相同）。 在這種情況下，余數與以下表達式相同：(xr-1+...+x+1) xr% G 對于給定的生成器多項式來說，此表達式的計算結果將是一個常數。 最常用的CRC 32生成器多項式是G(x) = x32+x26+x23+x22+x16+x12+x11+x10+x8+x7+x5+x4+x2+x+1 該式在十六進制中是04C11DB7。 與CRC-32對應的常數剩余值在十六進制中是C704DD7B。對于給定的生成器多項式G來說，無論在輸入端提供何種數據樣式，剩余值仍為常數。 硬件實現 CRC校驗和的計算是多項式除法過程。在硬件中實現該過程需要使用一個移位寄存器（亦稱CRC寄存器）。該移位寄存器的長度與生成器多項式的階數相同。 CRC 計算過程如下： 1.初始化CRC寄存器。 2.持續獲取消息位，直到獲得所有消息位。如果CRC寄存器中的高階位是1，則向左移一位，并且將其結果與G進行異或運算。否則，僅向左移一位。 對給定消息完成所有這些步驟后，CRC寄存器中剩 下的就是余數。 可以用一種稱為線性反饋移位寄存器(LFSR)的電路執行這些步驟。圖1所示為用CRC32多項式計算 CRC 的 LFSR 實現方法。請注意，異或門的布局取決于生成器多項式中項值為 1 的對應項的系數。圖中的編號方框各代表一個存儲元件（觸發器）。 CRC模塊 CRC 的硬件實現使用一個簡單的 LFSR。這種電路雖然實現起來簡單，但對于一個n位數據流來說，要占用n個時鐘周期來計算CRC值。在必須以較高速度處理數據幀的高速數據網絡應用中，這樣的延遲是無法忍受的。這類高速網絡應用迫切需要對并行數據流實現CRC生成和校驗。 Virtex-5 LXT/SXT器件中實現的CRC模塊可幫助設計人員加速校驗和計算。 Virtex-5 LXT/SXT器件中的 CRC硬模塊基于CRC32多項式。Virtex-5 FPGA含有CRC32和 CRC64 兩種硬模塊，能以一個時鐘周期的延遲為4位和8位數據輸出生成CRC。其界面簡單易用。硬模塊對給定的消息流起著CRC計算器的作用，同時提供一些針對 CRC的參數作為輸入。CRC的比較功能已經超出硬模塊的范圍，應集成到FPGA架構中。 FPGA 中的每個CRC硬模塊異步計算一個32位校驗和。 圖2是說明硬模塊架構的模塊級圖。CRC硬模塊提供一個位反演和字節反轉的輸出。 圖3所示為CRC硬模塊的應用概況。在發射器上，CRC經計算后附加到給定數據包的尾部。在接收器上，對連帶發射器所附加的CRC一起接收到的整個數據包重新計算CRC。 所收數據包的有效性用剩余法來確定。對于本例中的CRC32多項式來說，剩余值的計算結果將是十六進制的1CDF4421，這其實就是 C704DDB7的位反演和字節反轉值。字節反轉和位反演的概念如圖4所示。 圖5所示為正常CRC運算的波形 我們還提供一個LogiCORETM CRC 向導，其中為 Virtex-5 器件中的CRC硬模塊提供一個LocalLink封裝。其內核還提供了一個說明如何使用 CRC 硬模塊的設計實例。此外，內核提供了各種選項，如流水線處理、補數計算和轉置。 結論 Xilinx FPGA中的CRC模塊使設計人員能夠輕松地將檢錯機制加入到各種設計中�？梢杂肅ORE GeneratorTM軟件中提供的CRC Wizard IP加入符合不同協議（如 Aurora 和 PCI Express）的檢錯功能。 |
