基于SATAⅡ協議的CRC32并行算法的研究

朱佳齊，尹 蕾，許 晏，陳泉根

（中國工程物理研究院 電子工程研究所，四川 綿陽 621900）

隨著通信和存儲技術的發展，數據傳輸速率在急劇提高。然而由于通道傳輸特性不理想及可能受到干擾或噪聲的影響，數據傳輸過程中難免會發生錯誤。如何保證可靠性是正確設計一個通信系統或數據存儲系統的關鍵問題所在。

信道編碼是提高可靠性的必要手段，實現檢錯功能的差錯控制方法很多，包括奇偶校驗、重復碼校驗、校驗和檢測、行列冗余碼校驗、恒比碼校驗、CRC校驗等。其中CRC循環冗余校驗是一種高效率的差錯控制方案，其特點是編碼和解碼的方法簡單、檢錯糾錯能力強，因而應用于許多領域尤其是串行通信中以實現差錯控制。

CRC循環校驗算法占用的系統資源少，其實現方法分為軟件實現和硬件實現。文中在研究CRC32算法的基礎上，結合SATAⅡ協議的具體要求，實現了基于FPGA的CRC32并行算法。

1 CRC校驗原理

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

式中ki的系數取0或1。同樣，用G（x）表示r+1位生成多項式，先在式（1）兩端同時乘以 xr，則：

xrk（x）模 2 除以 G（x），得到的余數多項式為 R（x），商多項式為 Q（x），則：

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

由式（3）、式（4）和式（5）可得：

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

2 CRC32算法介紹

CRC32規范中其生成多項式G（x）如下：

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

圖1 比特型算法硬件框圖Fig.1 Hardware diagram of bit calculation

串行比特型算法可以很容易通過帶反饋的移位寄存器的硬件實現，其吞吐率可以達到200 Mbps，但是遠遠不能達到高速通信系統的要求。

對于查表法生成CRC校驗碼，要預先計算好所要的有效信息位，并存放信息位表中，然后按信息位的順序計算好所有校驗位，并存放于表中，待要使用時通過查表輸出對于的CRC校驗值。但這種方法需要較大的存儲空間存儲長度較大的CRC余數表，并且隨著并行位數的增加，余數表的長度按指數增加，對于CRC32規范也不具有現實性[5]。

因此，SATA協議中需采用并行CRC32算法以達到3 Gbps的吞吐率。

3 CRC32并行算法推導

CRC32并行算法可由串行比特型算法推導而出。

令需進行校驗的32位數據以Q0表示，32位移位寄存器初始值用M0表示即：

自反饋的移位運算可以采用狀態轉移矩陣表示，i+1次移位后寄存器的狀態Qi+1與i次移位后寄存器的狀態Qi之間的關系可通過狀態矩陣A表示為：Qi+1=AQi，進一步又可得到第i次的狀態Qi可通過初始狀態Q0表示為：

式中狀態轉移矩陣A可由式（7）和CRC32串行實現框圖推導得到[6]。首先32位數據串行輸入，與移位寄存器相關位中的初始值進行模2加減運算，32次移位后數據輸入完畢，即：

然后再進行32次移位，移位寄存器中的內容即為所求的CRC校驗值，則：

綜合式（11）和式（12）得：

由式（13）可知：CRC校驗值只與CRC校驗初始值M0和需校驗數據Q0有關，其中A64和A32可以由MATLAB計算得出。通過計算，可以得出CRC校驗最高位為：

CRC32其他校驗位都可以類推由式（13）得出。

4 SATA協議中CRC32算法實現

SATA總線主要由應用層、傳輸層、鏈路層和物理層組成，其中傳輸層主要用于傳輸數據命令，鏈路層則是對數據進行編碼和解碼以保證數據在鏈路中正確傳輸。SATA總線鏈路中的信息包含兩種結構：原語（Primitive）和幀（Frame），兩者都以雙字為最小的單位，其結構如圖2所示。

圖2 SATA鏈路數據結構圖Fig.2 Structure chart of the SATA link data

幀結構由多個雙字組成，包括幀頭（SOF）、幀數據、幀尾（EOF）和用于控制碼流的控制原語HOLD原語和HOLDA原語。SATA協議中CRC校驗模塊需自動識別出數據流中的原語，并不計算這些原語的CRC值。在發送信息時，需要由幀數據生成CRC碼，即所有非原語數據都要進行CRC編碼，并且將生成的CRC值插入到幀尾（EOF）之前進行傳輸。在接受到數據時，需要對幀數據進行CRC校驗，從而判斷數據在鏈路中傳輸是否出錯。在SATA協議中規定CRC校驗初始值0x52325032，并且在幀頭和幀尾中的數據不能超過2 046個雙字。

SATA協議中CRC生成校驗模塊采用有限狀態機來識別傳輸數據流中的原語，從而完成CRC值的生成與校驗。其狀態機結構圖如圖3所示。

圖3 CRC生成模塊狀態轉換圖Fig.3 State transition diagram of CRC generation module

其中狀態STATE0檢測幀頭并裝入STATE1狀態；在STATE1中，當輸入數據為幀尾時，則轉入STATE3狀態，否則轉入STATE2狀態，在STATE1狀態下輸出幀頭，并設置CRC初始值為0x52325032h；在STATE2中，當輸入為幀尾時，則轉入STATE3狀態，否則轉入STATE2狀態，對非原語數據進行CRC值生成，并保存到寄存器中，輸出為數據或保持原語；在STATE3中輸出最終的CRC值，并轉入STATE4狀態；在STATE4中輸出幀尾，并轉入STATE0狀態等待下一次數據的輸入。

輸入一幀數據，并由式（14）進行計算，得出輸入數據對應的CRC計算值如表1所示。

表1 輸入數據流實例Tab.1 The examp le of input data flow

其對應的系統仿真結果如圖4所示。

圖4 系統仿真結果圖Fig.4 Result of system simulation

仿真結果顯示，CRC數據校驗與表1中的理論值一致，CRC生成模塊能夠自動識別數據流中的原語和數據，并能有數據生成正確的CRC校驗值。其中每雙字數據生成CRC值僅需一個時鐘周期，系統輸出延時僅為一個時鐘周期，相對于串行CRC生成算法，CRC32并行算法更能滿足SATA協議對時鐘頻率的要求。

5 結束語

文中介紹了CRC校驗原理和常用CRC32實現算法，并根據比特型算法推導出一種CRC32并行算法的實現方案，該方案實現簡單，實現的并行算法相對于串行算法具有速度快，運算簡單，并且易于硬件實現等優點。本文還將將CRC32并行算法與SATA協議相結合，實現了滿足SATA協議規范的CRC生成和校驗模塊，并成功應用于SATAⅡ主控制器的設計中。

[1]黃維超，劉橋，黃初華.基于FPGA的循環冗余校驗并行實現[J].信息技術，2009（6）:181-183.HUANG Wei-chao，LIU Qiao，HUANG Chu-hua.Inplementation of parallel CRC based on FPGA[J].Information Technology，2009（6）:181-183.

[2]葉懋，劉宇紅，劉橋.CRC碼的FPGA實現[J].重慶工學院學報：自然科學版，2007，21（3）:85-87.YE Mao，LIU Yu-hong，LIU Qiao.Implementation of CRC based on FPGA[J].Journal of Chongqing Institute of Technology：Natural Science Edition，2007，21（3）:85-87.

[3]范紅旗，王勝，祝依龍.CRC編解碼器及其FPGA實現[J].數據采集與處理，2006（21）:97-100.FAN Hong-qi，WANG Sheng，ZHU Yi--long.CRC coderencoder algorithm and its FPGA implemenation[J].Journal of Data Acquisition ＆ Processing，2006（21）:97-100.

[4]常天海，胡鑒.基于FPGA的CRC并行算法研究與實現[J].微處理機，2010（2）:45-48.CHANG Tian-hai，HU Jian.Applicating research of CRC parallel algorithm based on FPGA[J].Microprocessors，2010（2）:45-48.

[5]張樹剛，張遂南，黃士坦.CRC校驗碼并行計算的FPGA實現[J].計算機技術與發展，2007，17（2）:56-58.ZHANG Shu-gang，ZHANG Sui-nan，HUANG Shi-tan.CRC parallel computation implementation on FPGA[J].Computer Technology and Development，2007，17（2）:56-58.

[6]郭熙業，蘇紹璟，王躍科.并行CRC-32校驗碼生成算法研究及其實現[J].電子技術應用，2007（5）:121-123.GUO Xi-ye，SU Shao-jing，WANG Yue-ke.Applicating research of CRC-32 parallel generation algorithm[J].Application of Electronic Technique，2007（5）:121-123.

[7]張偉，陳鋒，馬軍強.軌/姿控發動機脈沖后效沖量快速算法的研究及應用[J].火箭推進，2012（1）:51-56.ZHANG Wei，CHEN Feng，MA Jun-qiang.Research and application of fast algorithm for pulse residual impulse of divert and attitude control engine[J].Journal of Rocket Propulsion，2012（1）:51-56.