文档介绍：该【一种CRC并行计算原理及实现方法 】是由【1781111****】上传分享，文档一共【6】页，该文档可以免费在线阅读，需要了解更多关于【一种CRC并行计算原理及实现方法 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。 【提要】本文提出一种通用的CRC并行计算原理及实现方法,适于不同的CRC生成多项式和不同并行度(如8位、16位、及32位等),与目前已采用的查表法比较,不需要存放余数表的高速存储器,减少了时延,且可通过增加并行度来降低高速数传系统的CRC运算时钟频率. 关键词:循环冗余码的并行计算,CRC余数,高速数传系统putingZhuRonghua(municationNationalKeyLabofUESTC,Chengdu610054) Abstract: TheprincipleandimplementationofageneralparallelCyclicRedundancyCode,,itneednotthehighspeedRAMwhichwasusedtostoretheremaindertable,,wecanincreaseproperlyparalleldegreetodecreasetheclockfrequencyputinginhigh-speeddigitalsystems. Keywords: puting,CRCremainder,High-speeddigitalsystem一、引言 循环冗余校验码简称为循环冗余码或CRC码(CyclicRedundancyCheck),是一种检出概率高、(最高次幂为k)产生,k次幂的生成多项式可产生k-,以及突发长度小于等于k-1的突发误码[1,3]. CRC码的编码过程如下: 设待校验的信息码有n位,M=(m,…),用多项式表示:n-1,mn-2,m1,m0M(x)()=n-1+…+1+Mxmn-1Xm1Xm0(1) 如果所采用的生成多项式g(x)的最高次幂为k,则先在式(1)的两端乘以Xk,变成:file:///F|/qikan_htm抽取_2000before/kjqk(200810)/dianzixb/dian99/dian9904/(第1/6页)2009-12-3114:52:28电子学报990438k()=k+n-1+k+n-2+…+k+1+kXMxmn-1Xmn-2Xm1Xm0X(2) XkM(x)模-2除以g(x),得到商多项式为q(x),余数多项式为R(x),即:XkM(x)+R(x)=q(x)g(x)(3) 余数多项式R(x)可表示为:()=k-1+k-2+…+1+Rxrk-1xrk-2xr1Xr0(4)将式(2)和式(4)代入式(3),得:()()=k()+()=k+n-1+…+k+k-1+…+1+qxgxXMxRxmn-1Xm0Xrr-1Xr1Xr0(5) 式(5)所对应的码组为n+k位,即:′=(,,…,m,,,,…,,)Mmn-1mn-21m0rk-1rk-2r1r0(6) 从M到M′,就是CRC的编码过程,r,r,…,,将接k-1k-21,r0收到的n+k位码除以相同的生成多项式g(x),根据式(3),所产生余数为零,就认为接收到的信息正确无误;(2914bytes)file:///F|/qikan_htm抽取_2000before/kjqk(200810)/dianzixb/dian99/dian9904/(第2/6页)2009-12-3114:52:28电子学报990438图1 通用CRC串行电路 式(1)~(6)表示,CRC编码必须进行模-2除运算,CRC码的校验位就是模-,模-2运算用异或门表示,那么一个通用的CRC串行电路就可以用图1所示的电路来表示. 在图1中,r,…,r表示k个二进制移位寄存器的存数,它由外部同步时钟启动移0,r1k-…表示生成多项式的系数,当为“1”时,开关相当于闭合;当gi(i=1,2,,k-1)g(x)gii为“0”时,,当给定一生成多项式g(x),-16的生成多项式g(x)=X16+X15+X2+1,相应的串行电路可简化为(图2).(2777bytes)图2 CRC-16的串行电路在串行电路中,只用移位寄存器和异或门,,若采用串行运算,需要高速串行移位时钟及相应的高速器件,极大地增加了实现的难度,,在155Mpbs的ATM网络或1000Mbps高速以太网等高速传输系统中,、并行计算及实现 目前已采用的CRC并行算法是查表法及基于查表法而导出的一些方法[2,4].这些方法均需要存储长度较大的CRC余数表,随着并行度的增加,余数表的长度大大增加(按指数增加),其现实性亦随之大大降低. 笔者在设计CRC电路的实践过程中提出了一种并行计算法及实现方案,如下所述. 如图1所示,各移位寄存器的状态值即为CRC余数值,当进行串行运算时,,如8位并行运算,即8位信息码同时输入并行运算电路所产生的CRC余数与串行运算时连续8位信息码相继输入串行运算电路所产生的CRC余数相同,: 设ri为图1中移位寄存器状态值,m为输入信息码序列,i=1,2,…,为输入信息码序号,j=0,1,…,k-ji1,为移位寄存器编码,(633bytes),当j=0时,(7) 下面以8位并行输入为例,推导8位并行计算的CRC-16(其中生成多项式为g(x)=X16+X15+X2+1,(7),可递推出8,…,8:K=16)r0r15file:///F|/qikan_htm抽取_2000before/kjqk(200810)/dianzixb/dian99/dian9904/(第3/6页)2009-12-3114:52:(6158bytes)(8)如式(8)所示,类似地可推导出88r1,…,:(1054bytes) (9) 8位并行计算的CRC-(2230bytes)(1990bytes) 根据表1的逻辑关系式容易直接实现8位并行的CRC-16的硬件运算电路,:///F|/qikan_htm抽取_2000before/kjqk(200810)/dianzixb/dian99/dian9904/(第4/6页)2009-12-3114:52:(3489bytes)图3 8位并行的CRC-16硬件实现示意图 上述方法的推导过程虽然是针对8位并行CRC-16运算为例进行的,但这种方法具有通用性,、性能比较 将本文提出的方法与查表法作比较. 查表法可以用软件实现[2,3],也可以用硬件实现(图4).如图4所示,要进行一个CRC生成多项式的运算,(3456bytes)图4 8位并行CRC查表法硬件实现示意图 将图3与图4加以比较可得到如下结论: (1),-3实现CRC-16为例,按本文提出的直接硬件实现法,如图3所示,可以全部用FPGA的内部资源实现,总的时延为两级异或门时延和寄存器的锁存时延之和,约为15ns;,还必须使用FPGA的输入/出引脚和外部高速存储器,总的时延为两级异或门时延、寄存器的锁存时延、输入/出引脚时延和外部存储器的读时延之和,,由于需要输入输出引脚和外部存储器,所以时延较大,限制了使用更高的处理时钟. (2),不管是软件实现还是硬件实现,并行度一般不超过8位,因为随着并行度的增大,,并行度为16位时,CRC余数表的长度将达到65536(216)项,而并行度为32位时,CRC余数表的长度将达到4,294,967,296(232)项,:///F|/qikan_htm抽取_2000before/kjqk(200810)/dianzixb/dian99/dian9904/(第5/6页)2009-12-3114:52:28电子学报990438时,查表法因其大并行度的实现受限,,如Jesper[4]等人,为了实现一个800Mbps的CRC计算,(如32位并行计算,甚至64位的并行计算),降低了处理时钟,、结束语 本文在分析了CRC计算原理的基础上,,可以灵活实现各种CRC生成多项式在不同并行度下的计算以及硬件实现(采用可编程器件或ASIC专用芯片的设计),尤其对需要提高并行度(大于8)的高速系统的CRC计算,,1989年毕业于电子科技大学,1993年获硕士学位,曾参加光纤通信,:电子科技大学光纤通信国家重点实验室,成都610054参考文献1 邵军力,杨心强,,1988,102 -,1983,3(3):40~503 ,1988,8(4):62~754 ,24,109~1181997年11月收到,1998年4月修改定稿file:///F|/qikan_htm抽取_2000before/kjqk(200810)/dianzixb/dian99/dian9904/(第6/6页)2009-12-3114:52:28