《电子技术应用》
您所在的位置:首页 > 嵌入式技术 > 业界动态 > Ultra DMA 33中CRC校验并行算法推导及其实现

Ultra DMA 33中CRC校验并行算法推导及其实现

2008-08-11
作者:钱小兵 许志猛 李兵兵

    摘 要: 介绍高速数据采集" 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=r1515m16;同时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

本站内容除特别声明的原创文章之外,转载内容只为传递更多信息,并不代表本网站赞同其观点。转载的所有的文章、图片、音/视频文件等资料的版权归版权所有权人所有。本站采用的非本站原创文章及图片等内容无法一一联系确认版权者。如涉及作品内容、版权和其它问题,请及时通过电子邮件或电话通知我们,以便迅速采取适当措施,避免给双方造成不必要的经济损失。联系电话:010-82306118;邮箱:aet@chinaaet.com。