资源描述：
《32位CRC校验码的并行算法及硬件实现》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、中图分类号:TP331文献标识码:A文章编号:1009-2552(2007)04-0071-0432位CRC校验码的并行算法及硬件实现俞迅(同济大学电子与信息工程学院,上海200092)摘要:通过对CRC校验码原理的分析,研究了一种并行32位CRC算法。该算法采用递推的方法,直接得出计算多位数据后的CRC余数与计算前余数之间的逻辑关系。相对于一般的按位串行计算或者查表并行计算的方法来说,该方法运算速度快且不需要额外的空间存储余数表,十分有利于硬件实现。关键词:CRC;模2运算;并行CRC算法The32-bitcyclicredundancycheckparallelalgorithman
2、dhardwareimplementationYUXun(CollegeofElectronicandInformationEngineering,TongjiUniversity,Shanghai200092,China)Abstract:Basedonthetheoryofthecyclicredundancycheck,aparallelalgorithmisstudiedinthepaper.Thisalgorithmusesarecursivemethodtocalculatethelogicrelationshipofthechecksum.Differingfromgene
3、ralserialalgorithmortheparallelalgorithmbasedonlist-checking,itisfasteranddoesn’tneedtheex2tramemoryspacetostoretheremainderlist.Itisveryeasytobeimplementedbyhardware.Keywords:Cyclicredundancycheck;modulo2arithmetic;CRCparallelalgorithm计算机系统中的数据,在进行读、写或者传输时出去。可能产生错误,为了减少和避免错误的产生,一方面首先,可将待编码的k位数据表
4、示成多项式可以通过对特定电路的精心设计,提高电路的稳定M(X):k-1k-2性和可靠性;另一方面则是对数据采用某种编码,通M(X)=Ck-1X+Ck-2X+⋯i过少量的附加电路,使之能发现某些错误,甚至能确+CiX+⋯+C1X+C0定出错位置,进而实现自动改错的功能。CRC(循环其中Ci为0或者1。冗余码)就是一种常用的错误检测码,它可以发现并对于r位CRC来说,校验码产生的过程为:纠正数据存储或传输过程中连续出现的多位错误,将M(X)左移r位,然后除以一个被称为生成因此在介质存储和网络通信方面得到了广泛的应多项式的G(X),所得余数就是CRC校验码。这里,用。随着技术的发展,数据存储和
5、传输速度大大提生成多项式G(X)是一个r+1位的多项式。高,在一些高速的场合如usb2.0或者快速以太网用公式表示如下:r中,传统的串行CRC算法已不能满足速度上的要M(X)·xR(X)=Q(X)+求,而必须采用速度更快的并行算法。G(X)G(X)其中Q(X)为商,在CRC的计算过程中不需要关注,1CRC校验码原理简介R(X)为余数,就是需要的CRC码。CRC的计算使CRC校验的基本思路是利用线性码原理,对需要进行传输的原始k位二进制数据按照一定的规则收稿日期:2006-11-20处理,产生一个r位的校验码并附加在原始数据后作者简介:俞迅(1982-),男,同济大学微电子与固体电子学在读
6、硕面,形成一个k+r位的二进制数据,最后一起发送士研究生,研究方向为集成电路前端设计及仿真。—71—用的是模2运算,即不带进位和借位的按位加减,这转换成二进制序列就是在逻辑上等同于异或运算。1000001001100000100011101101101112串行32位CRC算法为了便于表达,记为:设cj31+cj30+⋯+cjj32(dk-1+g32,g31,⋯,g2,g1,g0(2)31x30x1x+c0=xk-1xdk-2其中,gi对应于生成多项式的系数,取0或者1。k-2x+⋯+d0)modG(x)j为计算前的CRC多项式,gi为生成多项式G(x)定义ci为计算了第j位数据后所得C
7、RC值的第的第i位系数。i位,d3,d2,d1,d0为读入的数据顺序,最初时的000000则新读入一位数据d′后,CRC值为:c31,c30,c29,⋯,c2,c1,c0。基本思想就是32k-1k-2ix(dk-1x+dk-2x+⋯+dix+d0x+连续套用式(1)给出的串行公式4次,以期得出处理4033k-1k-2i4位数据后cd′)modG(x)=x(dk-1x+dk-2x+⋯+dix+i与ci和d3,d2,d1,d0之间的逻辑
