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