基于SATAII協(xié)議的CRC32并行算法的研究

摘要：在介紹CRC校驗原理和傳統CRC32串行比特算法的基礎上，由串行比特型算法推導出一種CRC32并行算法、并結合SATAⅡ協(xié)議的要求，完成了SATAⅡ主控制器設計中CRC生成與校驗模塊的設計。最后通過(guò)在ISE平臺上編寫(xiě)Verilog硬件描述語(yǔ)言，對SATA協(xié)議中幀結構數據進(jìn)行仿真，驗證該CRC32并行算法能夠滿(mǎn)足SATA接口實(shí)時(shí)處理的要求。
關(guān)鍵詞：CRC32；并行算法；SATA；Verilog

隨著(zhù)通信和存儲技術(shù)的發(fā)展，數據傳輸速率在急劇提高。然而由于通道傳輸特性不理想及可能受到干擾或噪聲的影響，數據傳輸過(guò)程中難免會(huì )發(fā)生錯誤。如何保證可靠性是正確設計一個(gè)通信系統或數據存儲系統的關(guān)鍵問(wèn)題所在。
信道編碼是提高可靠性的必要手段，實(shí)現檢錯功能的差錯控制方法很多，包括奇偶校驗、重復碼校驗、校驗和檢測、行列冗余碼校驗、恒比碼校驗、CRC校驗等。其中CRC循環(huán)冗余校驗是一種高效率的差錯控制方案，其特點(diǎn)是編碼和解碼的方法簡(jiǎn)單、檢錯糾錯能力強，因而應用于許多領(lǐng)域尤其是串行通信中以實(shí)現差錯控制。
CRC循環(huán)校驗算法占用的系統資源少，其實(shí)現方法分為軟件實(shí)現和硬件實(shí)現。文中在研究CRC32算法的基礎上，結合SATAⅡ協(xié)議的具體要求，實(shí)現了基于FPCA的CRC32并行算法。

1 CRC校驗原理
CRC校驗算法是利用線(xiàn)性編碼理論，發(fā)送方根據一定的規則，生成要傳送的n位信息碼的r位校驗碼(CRC碼)，并將校驗碼附在信息碼后面，最后發(fā)送(n+r)位二進(jìn)制系列。而接收方利用信息碼和校驗碼之間所遵循的同樣規則對接受到的二進(jìn)制系列進(jìn)行校驗，以判斷傳送中是否出錯。為了便于描述，n位信息碼用多項式k(x)表示：

由于求CRC校驗碼采用模2加減運算法則，即不帶進(jìn)位和借位的按位加減，這種加減運算實(shí)際上就是邏輯上的異或運算，加法和減法在邏輯上是等價(jià)的。在模2多項式代數運算中定義的規則有：

式中R(x)即為要求的CRC校驗碼，xrk(x)+R(x)為發(fā)送端向接收端所發(fā)送的加入了CRC校驗碼的信息碼，由式(6)可知xrk(x)+R(x)能夠被生成多項式G(x)所整除。故接收端對接受到的信息以同樣的生成多項式G(x)生成其CRC校驗碼，如果為0，則表示數據傳送過(guò)程中未出錯，否則出錯，應做出相應的處理。

2 CRC32算法介紹
CRC32規范中其生成多項式G(x)如下：

常用的CRC校驗碼生成算法包括串行比特型算法、查表型算法和并行算法。串行比特型算法主要由一個(gè)32比特移位寄存器和異或單元組成。每輸入一位串行數據，都會(huì )與移位寄存器中相應的位進(jìn)行異或，異或結果保存在相應的位中，并循環(huán)移位一位，直到32位串行數據輸入完畢，再進(jìn)行32次循環(huán)移位將每一位寄存器中的數據依次輸出，輸出的32位數據即為CRC32校驗值。其硬件實(shí)現框圖如圖1所示。