??? 摘?要： 介紹高速數(shù)據(jù)采集" title="高速數(shù)據(jù)采集">高速數(shù)據(jù)采集記錄系統(tǒng)中使用的Ultra? DMA硬盤存取方式,，通過(guò)對(duì)CRC校驗(yàn)原理的分析，與常用串行校驗(yàn)電路中各移位寄存器" title="移位寄存器">移位寄存器狀態(tài)值變化的觀察,，推導(dǎo)出CRC校驗(yàn)并行運(yùn)算，并給出其邏輯電路實(shí)現(xiàn)。
??? 關(guān)鍵詞： CRC校驗(yàn)? 并行算法" title="并行算法">并行算法推導(dǎo)? Ultra DMA 33? 高速數(shù)據(jù)采集記錄系統(tǒng)
?
??? 在高速數(shù)據(jù)采集記錄系統(tǒng)中,，必須保證在限定時(shí)間內(nèi)有足夠的數(shù)據(jù)傳輸率和存儲(chǔ)容量,，但數(shù)據(jù)的傳輸與存儲(chǔ)常常構(gòu)成系統(tǒng)瓶頸,，制約了采集數(shù)據(jù)記錄系統(tǒng)的性能提高,。在此采用Ultra DMA方式對(duì)大容量硬盤進(jìn)行數(shù)據(jù)存取,。本文主要推導(dǎo)了循環(huán)冗余位校驗(yàn)CRC（Cyclical Redundancy Check）的并行算法的硬件實(shí)現(xiàn)及其在Ultra DMA 33中的電路實(shí)現(xiàn),。
1 CRC檢驗(yàn)方法的基本原理
??? CRC校驗(yàn)碼由分組線性碼的分支而來(lái),，其應(yīng)用主要為二元碼組,，由一個(gè)生成多項(xiàng)式（最高次冪為k）產(chǎn)生，k次冪的生成多項(xiàng)式可產(chǎn)生k位的冗余碼,，所有碼字的運(yùn)算是封閉的,。
??? 設(shè)每個(gè)Ultra DMA突發(fā)傳輸?shù)男盘?hào)碼元序列為m={mn-1,mn-2,…,m1,m0},用多項(xiàng)式表示為：
??? 在Ultra DMA方式中，收端同樣用原始數(shù)據(jù)進(jìn)行CRC運(yùn)算,，然后把計(jì)算出的校驗(yàn)碼與發(fā)端發(fā)過(guò)來(lái)的校驗(yàn)冗余碼相比較,，根據(jù)結(jié)果是否為零來(lái)判別傳輸是否出錯(cuò)。
??? 一般產(chǎn)生16位校驗(yàn)碼的串行電路如圖1所示,。???
?
??? 在信息碼長(zhǎng)度個(gè)時(shí)鐘脈沖" title="時(shí)鐘脈沖">時(shí)鐘脈沖后,，輸出原始待編碼碼字，而移位寄存器所存的數(shù)據(jù)為產(chǎn)生的校驗(yàn)碼,，再經(jīng)過(guò)16個(gè)時(shí)鐘脈沖,，輸出校驗(yàn)碼。
??? 在串行電路中,，只用到移位寄存器和異或門,。在Ultra DMA 33方式中，使用的時(shí)鐘為16MHz,，若采用串行方式,，每一個(gè)時(shí)鐘脈沖完成一個(gè)比特的運(yùn)算，這樣就大大地影響了數(shù)據(jù)的傳輸速率" title="傳輸速率">傳輸速率,。實(shí)際采用并行運(yùn)算方式,，每一個(gè)時(shí)鐘脈沖內(nèi)完成16個(gè)比特的運(yùn)算，速率提高了近十六倍,。
2? 并行計(jì)算的推導(dǎo)
??? 設(shè)
為移位寄存器狀態(tài)值,，mi為輸入信息碼序列，i=1,2,...,16為并行輸入16比特信息的序號(hào)數(shù)（或者為16次串行運(yùn)算中某數(shù)據(jù)位上數(shù)的移位次數(shù)）,，j=0,1,...,k-1為移位寄存器編號(hào),。下面以16位并行輸入為例，直接由電路中各移位寄存器的不同狀態(tài)值,，推導(dǎo)16位并行計(jì)算CRC-16(生成多項(xiàng)式為g(x)=x16+x12+x5+1,，即K=16)的邏輯關(guān)系式。
??? 此時(shí)系數(shù)c0=c5=c12=c16=1,，其余系數(shù)均為0,。其電路圖可簡(jiǎn)化,如圖2所示。
?
??? 由圖2可以看到,，移位寄存器R0在16次移位運(yùn)算后輸出的數(shù)據(jù)r016,，等于寄存器R15第15次移位輸出數(shù)據(jù)與第16個(gè)輸入的原始數(shù)據(jù)模2相加,，即r016=r1515
m16；同時(shí)c14,、c13為零,，表示在寄存器R12輸出到寄存器R13、R13輸出到R14,、R14輸出到R15時(shí),，中間沒(méi)有新輸入的原始數(shù)據(jù)和最后一個(gè)寄存器輸出的數(shù)據(jù)參與運(yùn)算，用式子可表示為r1515=r1414=r1313=r1212,，有r016=r1212m16,；因?yàn)閏12=1，R12第11次移位后內(nèi)部的數(shù)值由R11的11次移位輸出的數(shù)據(jù),、R15第11次移位輸出的值,、輸入的第12個(gè)數(shù)三者之和構(gòu)成，即r1212=r1111r1511m12,；同理計(jì)算r1111,、r1511，r1111=r1010=r99=r88=r77=r66=r55,、r1511=r1410=r139=r128,，且 R5第5次移位輸出的值，又跟R4第4次輸出值,、R15第4次輸出值,、第5個(gè)輸入值有關(guān)，r55=r44r154m5,、r128=r117r157m8,；又c4=c3=c2=c1=0，其間只是各寄存器間直接傳遞數(shù)據(jù),，無(wú)其它數(shù)據(jù)參與,，所以r44=r33=r22=r11=r00、又r154=r121=r110r150m1,、r157=r146=r135=r124,、r117=r106=r95=r84=r73=r63=r51。進(jìn)一步運(yùn)算r51=r40m5r150,、r124=r113r153m4=r80r120m4,，從而可以得到最后的結(jié)果r016=r00m16r40m12r80m8r110m5r120m4。其中ri0為各移位寄存器初始值或上次運(yùn)算的產(chǎn)生值,mi為一次并行輸入的16位碼字,，i為其編號(hào),。
??? 上面推導(dǎo)中寄存器內(nèi)數(shù)據(jù)變化關(guān)系如表1所示。
?
??? 設(shè)
15,同理可以推導(dǎo)其余移位寄存器的狀態(tài),。
??? 可以看到,，表1中還有許多重復(fù)的部分,，直接用到電路中，完全實(shí)現(xiàn)需要73個(gè)異或門和16個(gè)D觸發(fā)器,，會(huì)浪費(fèi)一些資源,，所以對(duì)表1進(jìn)行整合、簡(jiǎn)化,。首先定義如表2,。再進(jìn)一步把表2的定義帶入到表1中化簡(jiǎn)，得到表3,。根據(jù)表2、3,，其邏輯電路圖可直接獲得,，圖3為硬件電路圖。
?
?
?
??? 圖3中Crcout（i）反饋回輸入端,，作為初始值,，參與下一組并行輸入16位數(shù)據(jù)的運(yùn)算。
3 CRC在Ultra DMA中應(yīng)用
??? IDE硬盤接口為了提高數(shù)據(jù)傳輸速率,，Ultra DMA方式利用時(shí)鐘上升沿和下降沿鎖存數(shù)據(jù),，這樣就可以在不提高時(shí)鐘頻率的情況下使得數(shù)據(jù)傳輸速率增加一倍。但是,，隨著計(jì)算機(jī)性能的提高,，硬盤接口也不得不通過(guò)提高時(shí)鐘頻率來(lái)提高性能。這樣,，為了獲得數(shù)據(jù)的可靠性,，引入了數(shù)據(jù)檢錯(cuò)機(jī)制，即CRC校驗(yàn),。在每次突發(fā)傳輸過(guò)程中,，主機(jī)和硬盤都進(jìn)行CRC計(jì)算。當(dāng)數(shù)據(jù)傳輸結(jié)束后,，硬盤把自己計(jì)算的CRC值與主機(jī)計(jì)算的CRC值進(jìn)行比較,，如果兩個(gè)值不一樣，那么主機(jī)必須選擇較低的傳輸模式并重新傳輸數(shù)據(jù),。在UDMA數(shù)據(jù)傳輸之前,，主機(jī)和設(shè)備都應(yīng)該初始化成起始值4ABAh。
??? 若使用查表方式,，當(dāng)并行度為16位時(shí),，CRC余數(shù)表的長(zhǎng)度將達(dá)到65536(216)項(xiàng)，需要額外的存儲(chǔ)空間,，同時(shí)對(duì)該空間的讀取也會(huì)占用一定的時(shí)鐘和邏輯資源,。所以實(shí)際應(yīng)用中,，用FLEX10KA來(lái)產(chǎn)生控制邏輯，直接使用上文推導(dǎo)出的邏輯算法電路,，CRC校驗(yàn)只占用了50個(gè)異或門和16個(gè)D觸發(fā)器,，在使用流水線結(jié)構(gòu)的前提下，每個(gè)時(shí)鐘脈沖都可以輸出一個(gè)16位的校驗(yàn)值,。
參考文獻(xiàn)
1 ATA/ATAPI-6?information technology AT attachment with? packet interface-6
2 王新梅,，肖國(guó)鎮(zhèn). 糾錯(cuò)碼－原理與方法（修訂版）. 西安:?西安電子科技大學(xué)出版社， 2001
3 樊昌信,，詹道庸.通信原理（第四版）.長(zhǎng)沙：國(guó)防工業(yè)出版社,，2001