基于SATAII協(xié)議的CRC32并行算法的研究
加入技術(shù)交流群
串行比特型算法可以很容易通過(guò)帶反饋的移位寄存器的硬件實(shí)現(xiàn)，其吞吐率可以達(dá)到200 Mbps，但是遠(yuǎn)遠(yuǎn)不能達(dá)到高速通信系統(tǒng)的要求。
對(duì)于查表法生成CRC校驗(yàn)碼，要預(yù)先汁算好所要的有效信息位，并存放信息位表中，然后按信息位的順序計(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í)性。
因此，SATA協(xié)議中需采用并行CRC32算法以達(dá)到3 Gbps的吞吐率。
3 CRC32并行算法推導(dǎo)
CRC32并行算法可由串行比特型算法推導(dǎo)而出。
令需進(jìn)行校驗(yà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)系可通過(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)得到。首先32位數(shù)據(jù)串行輸入，與移位寄存器相關(guān)位中的初始值進(jìn)行模2加減運(yùn)算，32次移位后數(shù)據(jù)輸入完畢，即：
然后再進(jìn)行32次移位，移位寄存器中的內(nèi)容即為所求的CRC校驗(yàn)值，則：
由式(13)可知：CRC校驗(yàn)值只與CRC校驗(yàn)初始值M0和需校驗(yàn)數(shù)據(jù)Q0有關(guān)，其中A64和A32可以由MATLAB計(jì)算得出。通過(guò)計(jì)算，可以得出CRC校驗(yàn)最高位為：
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所示。本文引用地址：http://butianyuan.cn/article/159619.htm
幀結(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è)雙字。
評(píng)論