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

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

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

    由于求CRC校驗碼采用模2加減運(yùn)算法則，即不帶進(jìn)位和借位的按位加減，這種加減運(yùn)算實際上就是邏輯上的異或運(yùn)算，加法和減法在邏輯上是等價的。在模2多項式代數(shù)運(yùn)算中定義的規(guī)則有：
   
    式中R(x)即為要求的CRC校驗碼，xrk(x)+R(x)為發(fā)送端向接收端所發(fā)送的加入了CRC校驗碼的信息碼，由式(6)可知xrk(x)+R(x)能夠被生成多項式G(x)所整除。故接收端對接受到的信息以同樣的生成多項式G(x)生成其CRC校驗碼，如果為0，則表示數(shù)據(jù)傳送過程中未出錯，否則出錯，應(yīng)做出相應(yīng)的處理。

2 CRC32算法介紹
    CRC32規(guī)范中其生成多項式G(x)如下：
   
    常用的CRC校驗碼生成算法包括串行比特型算法、查表型算法和并行算法。串行比特型算法主要由一個32比特移位寄存器和異或單元組成。每輸入一位串行數(shù)據(jù)，都會與移位寄存器中相應(yīng)的位進(jìn)行異或，異或結(jié)果保存在相應(yīng)的位中，并循環(huán)移位一位，直到32位串行數(shù)據(jù)輸入完畢，再進(jìn)行32次循環(huán)移位將每一位寄存器中的數(shù)據(jù)依次輸出，輸出的32位數(shù)據(jù)即為CRC32校驗值。其硬件實現(xiàn)框圖如圖1所示。

    串行比特型算法可以很容易通過帶反饋的移位寄存器的硬件實現(xiàn)，其吞吐率可以達(dá)到200 Mbps，但是遠(yuǎn)遠(yuǎn)不能達(dá)到高速通信系統(tǒng)的要求。
    對于查表法生成CRC校驗碼，要預(yù)先汁算好所要的有效信息位，并存放信息位表中，然后按信息位的順序計算好所有校驗位，并存放于表中，待要使用時通過查表輸出對于的CRC校驗值。但這種方法需要較大的存儲空間存儲長度較大的CRC余數(shù)表，并且隨著并行位數(shù)的增加，余數(shù)表的長度按指數(shù)增加，對于CRC32規(guī)范也不具有現(xiàn)實性。
    因此，SATA協(xié)議中需采用并行CRC32算法以達(dá)到3 Gbps的吞吐率。

3 CRC32并行算法推導(dǎo)
    CRC32并行算法可由串行比特型算法推導(dǎo)而出。
    令需進(jìn)行校驗的32位數(shù)據(jù)以Q0表示，32位移位寄存器初始值用M0表示即：
    Q0=[D0D1D2D3…D31]T       (8)
    M0=[C0C1C2C3…C31]T       (9)
    自反饋的移位運(yùn)算可以采用狀態(tài)轉(zhuǎn)移矩陣表示，i+1次移位后寄存器的狀態(tài)Qi+1與i次移位后寄存器的狀態(tài)Qi之間的關(guān)系可通過狀態(tài)矩陣A表示為：Qi+1=AQi，進(jìn)一步又可得到第i次的狀態(tài)Qi可通過初始狀態(tài)Q0表示為：
   
    式中狀態(tài)轉(zhuǎn)移矩陣A可由式(7)和CRC32串行實現(xiàn)框圖推導(dǎo)得到。首先32位數(shù)據(jù)串行輸入，與移位寄存器相關(guān)位中的初始值進(jìn)行模2加減運(yùn)算，32次移位后數(shù)據(jù)輸入完畢，即：
   
    然后再進(jìn)行32次移位，移位寄存器中的內(nèi)容即為所求的CRC校驗值，則：
   
    由式(13)可知：CRC校驗值只與CRC校驗初始值M0和需校驗數(shù)據(jù)Q0有關(guān)，其中A64和A32可以由MATLAB計算得出。通過計算，可以得出CRC校驗最高位為：
   

4 SATA協(xié)議中CRC32算法實現(xiàn)
    SATA總線主要由應(yīng)用層、傳輸層、鏈路層和物理層組成，其中傳輸層主要用于傳輸數(shù)據(jù)命令，鏈路層則是對數(shù)據(jù)進(jìn)行編碼和解碼以保證數(shù)據(jù)在鏈路中正確傳輸。SATA總線鏈路中的信息包含兩種結(jié)構(gòu)：原語(Primitive)和幀(Frame)，兩者都以雙字為最小的單位，其結(jié)構(gòu)如圖2所示。

    幀結(jié)構(gòu)由多個雙字組成，包括幀頭(SOF)、幀數(shù)據(jù)、幀尾(EOF)和用于控制碼流的控制原語HOLD原語和HOLDA原語。SATA協(xié)議中CRC校驗?zāi)K需自動識別出數(shù)據(jù)流中的原語，并不計算這些原語的CRC值。在發(fā)送信息時，需要由幀數(shù)據(jù)生成CRC碼，即所有非原語數(shù)據(jù)都要進(jìn)行CRC編碼，并且將生成的CRC值插入到幀尾(EOF)之前進(jìn)行傳輸。在接受到數(shù)據(jù)時，需要對幀數(shù)據(jù)進(jìn)行CRC校驗，從而判斷數(shù)據(jù)在鏈路中傳輸是否出錯。在SATA協(xié)議中規(guī)定CRC校驗初始值0x52325032，并且在幀頭和幀尾中的數(shù)據(jù)不能超過2 046個雙字。
    SATA協(xié)議中CRC生成校驗?zāi)K采用有限狀態(tài)機(jī)來識別傳輸數(shù)據(jù)流中的原語，從而完成CRC值的生成與校驗。其狀態(tài)機(jī)結(jié)構(gòu)圖如圖3所示。

    其中狀態(tài)STATE0檢測幀頭并裝入STATE1狀態(tài)；在STATE1中，當(dāng)輸入數(shù)據(jù)為幀尾時，則轉(zhuǎn)入STATE3狀態(tài)，否則轉(zhuǎn)入STATE2狀態(tài)，在STATE1狀態(tài)下輸出幀頭，并設(shè)置CRC初始值為0x52325032h；在STATE2中，當(dāng)輸入為幀尾時，則轉(zhuǎn)入STATE3狀態(tài)，否則轉(zhuǎn)入STATE2狀態(tài)，對非原語數(shù)據(jù)進(jìn)行CRC值生成，并保存到寄存器中，輸出為數(shù)據(jù)或保持原語；在STATE3中輸出最終的CRC值，并轉(zhuǎn)入STATE4狀態(tài)；在STATE4中輸出幀尾，并轉(zhuǎn)入STATTE0狀態(tài)等待下一次數(shù)據(jù)的輸入。
    輸入一幀數(shù)據(jù)，并由式(14)進(jìn)行計算，得出輸入數(shù)據(jù)對應(yīng)的CRC計算值如表1所示。

    其對應(yīng)的系統(tǒng)仿真結(jié)果如圖4所示。
    仿真結(jié)果顯示，CRC數(shù)據(jù)校驗與表1中的理論值一致，CRC生成模塊能夠自動識別數(shù)據(jù)流中的原語和數(shù)據(jù)，并能有數(shù)據(jù)生成正確的CRC校驗值。其中每雙字?jǐn)?shù)據(jù)生成CRC值僅需一個時鐘周期，系統(tǒng)輸出延時僅為一個時鐘周期，相對于串行CRC生成算法，CRC32并行算法更能滿足SATA協(xié)議對時鐘頻率的要求。

5 結(jié)束語
    文中介紹了CRC校驗原理和常用CRC32實現(xiàn)算法，并根據(jù)比特型算法推導(dǎo)出一種CRC32并行算法的實現(xiàn)方案，該方案實現(xiàn)簡單，實現(xiàn)的并行算法相對于串行算法具有速度快，運(yùn)算簡單，并且易于硬件實現(xiàn)等優(yōu)點。本文還將將CRC32并行算法與SATA協(xié)議相結(jié)合，實現(xiàn)了滿足SATA協(xié)議規(guī)范的CRC生成和校驗?zāi)K，并成功應(yīng)用于SATAⅡ主控制器的設(shè)計中。