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

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

（中國(guó)工程物理研究院 電子工程研究所，四川 綿陽(yáng) 621900）

隨著通信和存儲(chǔ)技術(shù)的發(fā)展，數(shù)據(jù)傳輸速率在急劇提高。然而由于通道傳輸特性不理想及可能受到干擾或噪聲的影響，數(shù)據(jù)傳輸過(guò)程中難免會(huì)發(fā)生錯(cuò)誤。如何保證可靠性是正確設(shè)計(jì)一個(gè)通信系統(tǒng)或數(shù)據(jù)存儲(chǔ)系統(tǒng)的關(guān)鍵問(wèn)題所在。

信道編碼是提高可靠性的必要手段，實(shí)現(xiàn)檢錯(cuò)功能的差錯(cuò)控制方法很多，包括奇偶校驗(yàn)、重復(fù)碼校驗(yàn)、校驗(yàn)和檢測(cè)、行列冗余碼校驗(yàn)、恒比碼校驗(yàn)、CRC校驗(yàn)等。其中CRC循環(huán)冗余校驗(yàn)是一種高效率的差錯(cuò)控制方案，其特點(diǎn)是編碼和解碼的方法簡(jiǎn)單、檢錯(cuò)糾錯(cuò)能力強(qiáng)，因而應(yīng)用于許多領(lǐng)域尤其是串行通信中以實(shí)現(xiàn)差錯(cuò)控制。

CRC循環(huán)校驗(yàn)算法占用的系統(tǒng)資源少，其實(shí)現(xiàn)方法分為軟件實(shí)現(xiàn)和硬件實(shí)現(xiàn)。文中在研究CRC32算法的基礎(chǔ)上，結(jié)合SATAⅡ協(xié)議的具體要求，實(shí)現(xiàn)了基于FPGA的CRC32并行算法。

1 CRC校驗(yàn)原理

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

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

xrk（x）模 2 除以 G（x），得到的余數(shù)多項(xiàng)式為 R（x），商多項(xiàng)式為 Q（x），則：

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

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

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

2 CRC32算法介紹

CRC32規(guī)范中其生成多項(xiàng)式G（x）如下：

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

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

串行比特型算法可以很容易通過(guò)帶反饋的移位寄存器的硬件實(shí)現(xiàn)，其吞吐率可以達(dá)到200 Mbps，但是遠(yuǎn)遠(yuǎn)不能達(dá)到高速通信系統(tǒng)的要求。

對(duì)于查表法生成CRC校驗(yàn)碼，要預(yù)先計(jì)算好所要的有效信息位，并存放信息位表中，然后按信息位的順序計(jì)算好所有校驗(yàn)位，并存放于表中，待要使用時(shí)通過(guò)查表輸出對(duì)于的CRC校驗(yàn)值。但這種方法需要較大的存儲(chǔ)空間存儲(chǔ)長(zhǎng)度較大的CRC余數(shù)表，并且隨著并行位數(shù)的增加，余數(shù)表的長(zhǎng)度按指數(shù)增加，對(duì)于CRC32規(guī)范也不具有現(xiàn)實(shí)性[5]。

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

3 CRC32并行算法推導(dǎo)

CRC32并行算法可由串行比特型算法推導(dǎo)而出。

令需進(jìn)行校驗(yàn)的32位數(shù)據(jù)以Q0表示，32位移位寄存器初始值用M0表示即：

自反饋的移位運(yùn)算可以采用狀態(tài)轉(zhuǎn)移矩陣表示，i+1次移位后寄存器的狀態(tài)Qi+1與i次移位后寄存器的狀態(tài)Qi之間的關(guān)系可通過(guò)狀態(tài)矩陣A表示為：Qi+1=AQi，進(jìn)一步又可得到第i次的狀態(tài)Qi可通過(guò)初始狀態(tài)Q0表示為：

式中狀態(tài)轉(zhuǎn)移矩陣A可由式（7）和CRC32串行實(shí)現(xiàn)框圖推導(dǎo)得到[6]。首先32位數(shù)據(jù)串行輸入，與移位寄存器相關(guān)位中的初始值進(jìn)行模2加減運(yùn)算，32次移位后數(shù)據(jù)輸入完畢，即：

然后再進(jìn)行32次移位，移位寄存器中的內(nèi)容即為所求的CRC校驗(yàn)值，則：

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

由式（13）可知：CRC校驗(yàn)值只與CRC校驗(yàn)初始值M0和需校驗(yàn)數(shù)據(jù)Q0有關(guān)，其中A64和A32可以由MATLAB計(jì)算得出。通過(guò)計(jì)算，可以得出CRC校驗(yàn)最高位為：

CRC32其他校驗(yàn)位都可以類推由式（13）得出。

4 SATA協(xié)議中CRC32算法實(shí)現(xiàn)

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

圖2 SATA鏈路數(shù)據(jù)結(jié)構(gòu)圖Fig.2 Structure chart of the SATA link data

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

SATA協(xié)議中CRC生成校驗(yàn)?zāi)K采用有限狀態(tài)機(jī)來(lái)識(shí)別傳輸數(shù)據(jù)流中的原語(yǔ)，從而完成CRC值的生成與校驗(yàn)。其狀態(tài)機(jī)結(jié)構(gòu)圖如圖3所示。

圖3 CRC生成模塊狀態(tài)轉(zhuǎn)換圖Fig.3 State transition diagram of CRC generation module

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

輸入一幀數(shù)據(jù)，并由式（14）進(jìn)行計(jì)算，得出輸入數(shù)據(jù)對(duì)應(yīng)的CRC計(jì)算值如表1所示。

表1 輸入數(shù)據(jù)流實(shí)例Tab.1 The examp le of input data flow

其對(duì)應(yīng)的系統(tǒng)仿真結(jié)果如圖4所示。

圖4 系統(tǒng)仿真結(jié)果圖Fig.4 Result of system simulation

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

5 結(jié)束語(yǔ)

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

[1]黃維超，劉橋，黃初華.基于FPGA的循環(huán)冗余校驗(yàn)并行實(shí)現(xiàn)[J].信息技術(shù)，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實(shí)現(xiàn)[J].重慶工學(xué)院學(xué)報(bào)：自然科學(xué)版，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實(shí)現(xiàn)[J].數(shù)據(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并行算法研究與實(shí)現(xiàn)[J].微處理機(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校驗(yàn)碼并行計(jì)算的FPGA實(shí)現(xiàn)[J].計(jì)算機(jī)技術(shù)與發(fā)展，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]郭熙業(yè)，蘇紹璟，王躍科.并行CRC-32校驗(yàn)碼生成算法研究及其實(shí)現(xiàn)[J].電子技術(shù)應(yīng)用，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]張偉，陳鋒，馬軍強(qiáng).軌/姿控發(fā)動(dòng)機(jī)脈沖后效沖量快速算法的研究及應(yīng)用[J].火箭推進(jìn)，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.