《電子技術(shù)應(yīng)用》
您所在的位置:首頁 > 嵌入式技術(shù) > 業(yè)界動態(tài) > Ultra DMA 33中CRC校驗并行算法推導(dǎo)及其實現(xiàn)

Ultra DMA 33中CRC校驗并行算法推導(dǎo)及其實現(xiàn)

2008-08-11
作者:錢小兵 許志猛 李兵兵

??? 摘?要: 介紹高速數(shù)據(jù)采集" title="高速數(shù)據(jù)采集">高速數(shù)據(jù)采集記錄系統(tǒng)中使用的Ultra? DMA硬盤存取方式,通過對CRC校驗原理的分析,與常用串行校驗電路中各移位寄存器" title="移位寄存器">移位寄存器狀態(tài)值變化的觀察,,推導(dǎo)出CRC校驗并行運算,,并給出其邏輯電路實現(xiàn)。
??? 關(guān)鍵詞: CRC校驗? 并行算法" title="并行算法">并行算法推導(dǎo)? Ultra DMA 33? 高速數(shù)據(jù)采集記錄系統(tǒng)

?

??? 在高速數(shù)據(jù)采集記錄系統(tǒng)中,,必須保證在限定時間內(nèi)有足夠的數(shù)據(jù)傳輸率和存儲容量,但數(shù)據(jù)的傳輸與存儲常常構(gòu)成系統(tǒng)瓶頸,制約了采集數(shù)據(jù)記錄系統(tǒng)的性能提高,。在此采用Ultra DMA方式對大容量硬盤進行數(shù)據(jù)存取。本文主要推導(dǎo)了循環(huán)冗余位校驗CRC(Cyclical Redundancy Check)的并行算法的硬件實現(xiàn)及其在Ultra DMA 33中的電路實現(xiàn),。
1 CRC檢驗方法的基本原理
??? CRC校驗碼由分組線性碼的分支而來,,其應(yīng)用主要為二元碼組,由一個生成多項式(最高次冪為k)產(chǎn)生,,k次冪的生成多項式可產(chǎn)生k位的冗余碼,,所有碼字的運算是封閉的。
??? 設(shè)每個Ultra DMA突發(fā)傳輸?shù)男盘柎a元序列為m={mn-1,mn-2,…,m1,m0},用多項式表示為:


??? 在Ultra DMA方式中,,收端同樣用原始數(shù)據(jù)進行CRC運算,,然后把計算出的校驗碼與發(fā)端發(fā)過來的校驗冗余碼相比較,根據(jù)結(jié)果是否為零來判別傳輸是否出錯,。
??? 一般產(chǎn)生16位校驗碼的串行電路如圖1所示,。???

?


??? 在信息碼長度個時鐘脈沖" title="時鐘脈沖">時鐘脈沖后,輸出原始待編碼碼字,,而移位寄存器所存的數(shù)據(jù)為產(chǎn)生的校驗碼,,再經(jīng)過16個時鐘脈沖,輸出校驗碼,。
??? 在串行電路中,,只用到移位寄存器和異或門。在Ultra DMA 33方式中,使用的時鐘為16MHz,,若采用串行方式,,每一個時鐘脈沖完成一個比特的運算,這樣就大大地影響了數(shù)據(jù)的傳輸速率" title="傳輸速率">傳輸速率,。實際采用并行運算方式,,每一個時鐘脈沖內(nèi)完成16個比特的運算,速率提高了近十六倍,。
2? 并行計算的推導(dǎo)
??? 設(shè)為移位寄存器狀態(tài)值,,mi為輸入信息碼序列,i=1,2,...,16為并行輸入16比特信息的序號數(shù)(或者為16次串行運算中某數(shù)據(jù)位上數(shù)的移位次數(shù)),,j=0,1,...,k-1為移位寄存器編號,。下面以16位并行輸入為例,直接由電路中各移位寄存器的不同狀態(tài)值,,推導(dǎo)16位并行計算CRC-16(生成多項式為g(x)=x16+x12+x5+1,,即K=16)的邏輯關(guān)系式。
??? 此時系數(shù)c0=c5=c12=c16=1,,其余系數(shù)均為0,。其電路圖可簡化,如圖2所示。

?


??? 由圖2可以看到,,移位寄存器R0在16次移位運算后輸出的數(shù)據(jù)r016,,等于寄存器R15第15次移位輸出數(shù)據(jù)與第16個輸入的原始數(shù)據(jù)模2相加,即r016=r1515m16,;同時c14,、c13為零,表示在寄存器R12輸出到寄存器R13,、R13輸出到R14,、R14輸出到R15時,中間沒有新輸入的原始數(shù)據(jù)和最后一個寄存器輸出的數(shù)據(jù)參與運算,,用式子可表示為r1515=r1414=r1313=r1212,,有r016=r1212m16;因為c12=1,,R12第11次移位后內(nèi)部的數(shù)值由R11的11次移位輸出的數(shù)據(jù)、R15第11次移位輸出的值,、輸入的第12個數(shù)三者之和構(gòu)成,,即r1212=r1111r1511m12;同理計算r1111,、r1511,,r1111=r1010=r99=r88=r77=r66=r55、r1511=r1410=r139=r128,且 R5第5次移位輸出的值,,又跟R4第4次輸出值,、R15第4次輸出值、第5個輸入值有關(guān),,r55=r44r154m5,、r128=r117r157m8;又c4=c3=c2=c1=0,,其間只是各寄存器間直接傳遞數(shù)據(jù),,無其它數(shù)據(jù)參與,所以r44=r33=r22=r11=r00,、又r154=r121=r110r150m1,、r157=r146=r135=r124、r117=r106=r95=r84=r73=r63=r51,。進一步運算r51=r40m5r150,、r124=r113r153m4=r80r120m4,從而可以得到最后的結(jié)果r016=r00m16r40m12r80m8r110m5r120m4,。其中ri0為各移位寄存器初始值或上次運算的產(chǎn)生值,mi為一次并行輸入的16位碼字,,i為其編號。
??? 上面推導(dǎo)中寄存器內(nèi)數(shù)據(jù)變化關(guān)系如表1所示,。

?


??? 設(shè)15,同理可以推導(dǎo)其余移位寄存器的狀態(tài),。
??? 可以看到,表1中還有許多重復(fù)的部分,,直接用到電路中,,完全實現(xiàn)需要73個異或門和16個D觸發(fā)器,會浪費一些資源,,所以對表1進行整合,、簡化。首先定義如表2,。再進一步把表2的定義帶入到表1中化簡,,得到表3。根據(jù)表2,、3,,其邏輯電路圖可直接獲得,圖3為硬件電路圖,。

?

?

?


??? 圖3中Crcout(i)反饋回輸入端,,作為初始值,參與下一組并行輸入16位數(shù)據(jù)的運算,。
3 CRC在Ultra DMA中應(yīng)用
??? IDE硬盤接口為了提高數(shù)據(jù)傳輸速率,,Ultra DMA方式利用時鐘上升沿和下降沿鎖存數(shù)據(jù),,這樣就可以在不提高時鐘頻率的情況下使得數(shù)據(jù)傳輸速率增加一倍。但是,,隨著計算機性能的提高,,硬盤接口也不得不通過提高時鐘頻率來提高性能。這樣,,為了獲得數(shù)據(jù)的可靠性,,引入了數(shù)據(jù)檢錯機制,即CRC校驗,。在每次突發(fā)傳輸過程中,,主機和硬盤都進行CRC計算。當(dāng)數(shù)據(jù)傳輸結(jié)束后,,硬盤把自己計算的CRC值與主機計算的CRC值進行比較,,如果兩個值不一樣,那么主機必須選擇較低的傳輸模式并重新傳輸數(shù)據(jù),。在UDMA數(shù)據(jù)傳輸之前,,主機和設(shè)備都應(yīng)該初始化成起始值4ABAh。
??? 若使用查表方式,,當(dāng)并行度為16位時,,CRC余數(shù)表的長度將達到65536(216)項,需要額外的存儲空間,,同時對該空間的讀取也會占用一定的時鐘和邏輯資源,。所以實際應(yīng)用中,用FLEX10KA來產(chǎn)生控制邏輯,,直接使用上文推導(dǎo)出的邏輯算法電路,,CRC校驗只占用了50個異或門和16個D觸發(fā)器,在使用流水線結(jié)構(gòu)的前提下,,每個時鐘脈沖都可以輸出一個16位的校驗值,。
參考文獻
1 ATA/ATAPI-6?information technology AT attachment with? packet interface-6
2 王新梅,肖國鎮(zhèn). 糾錯碼-原理與方法(修訂版). 西安:?西安電子科技大學(xué)出版社,, 2001
3 樊昌信,,詹道庸.通信原理(第四版).長沙:國防工業(yè)出版社,2001

本站內(nèi)容除特別聲明的原創(chuàng)文章之外,,轉(zhuǎn)載內(nèi)容只為傳遞更多信息,,并不代表本網(wǎng)站贊同其觀點。轉(zhuǎn)載的所有的文章,、圖片,、音/視頻文件等資料的版權(quán)歸版權(quán)所有權(quán)人所有。本站采用的非本站原創(chuàng)文章及圖片等內(nèi)容無法一一聯(lián)系確認(rèn)版權(quán)者,。如涉及作品內(nèi)容,、版權(quán)和其它問題,請及時通過電子郵件或電話通知我們,,以便迅速采取適當(dāng)措施,,避免給雙方造成不必要的經(jīng)濟損失。聯(lián)系電話:010-82306118,;郵箱:[email protected],。