资源描述：
《一种CRC并行计算原理及实现方法.pdf》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、电子学报990438电子学报ACTAELECTRONICASINICA1999年第4期第27卷Vol.27No.41999一种CRC并行计算原理及实现方法朱荣华 【提要】 本文提出一种通用的CRC并行计算原理及实现方法，适于不同的CRC生成多项式和不同并行度(如8位、16位、及32位等)，与目前已采用的查表法比较，不需要存放余数表的高速存储器，减少了时延，且可通过增加并行度来降低高速数传系统的CRC运算时钟频率. 关键词:循环冗余码的并行计算，CRC余数，高速数传系统ThePrincipleandImplementationofaParallelCRCComputin
2、gZhuRonghua(OpticalFiberCommunicationNationalKeyLabofUESTC,Chengdu610054)Abstract:TheprincipleandimplementationofageneralparallelCyclicRedundancyCode,orCRCcomputingaredescribedinthepaper.Itissuitableforanygeneratorpolynomialandanyparalleldegreeofgeneratorpolynomialbetween1and32.Comparewit
3、hTableLookupAlgorithm,itneednotthehighspeedRAMwhichwasusedtostoretheremaindertable,anddecreasethedelay.Thus,wecanincreaseproperlyparalleldegreetodecreasetheclockfrequencyofCRCcomputinginhigh-speeddigitalsystems.Keywords:CRCparallelcomputing,CRCremainder,High-speeddigitalsystem一、引 言 循环冗余
4、校验码简称为循环冗余码或CRC码(CyclicRedundancyCheck)，是一种检出概率高、且易于用硬件实现的检错码.CRC码由一个生成多项式(最高次幂为k)产生，k次幂的生成多项式可产生k-1位的冗余码.适当选取生成多项式可以使CRC码能检出所有奇数位的随机误码，以及突发长度小于等于k-1的突发误码［1，3］.CRC码的编码过程如下： 设待校验的信息码有n位，M=(mn-1,mn-2,⋯,m1,m0)，用多项式M(x)表示：M(x)=mn-1Xn-1+⋯+m1X1+m0(1) 如果所采用的生成多项式g(x)的最高次幂为k，则先在式(1)的两端乘以Xk，变成：f
5、ile:///F
6、/qikan_htm抽取_2000before/kjqk(200810)/dianzixb/dian99/dian9904/990438.htm（第1／6页）2009-12-3114:52:28电子学报990438XkM(x)=mk+n-1+mk+n-2+⋯+mk+1+mkn-1Xn-2X1X0X(2)XkM(x)模-2除以g(x)，得到商多项式为q(x)，余数多项式为R(x)，即：XkM(x)+R(x)=q(x)g(x)(3) 余数多项式R(x)可表示为：R(x)=rk-1xk-1+rk-2xk-2+⋯+r1X1+r0(4)将式(2)和式(4)代入式
7、(3)，得：q(x)g(x)=XkM(x)+R(x)=mn-1Xk+n-1+⋯+m0Xk+rr-1Xk-1+⋯+r1X1+r0(5) 式(5)所对应的码组为n+k位，即：M′=(mn-1,mn-2，⋯，m1,m0,rk-1,rk-2,⋯,r1,r0)(6) 从M到M′，就是CRC的编码过程，rk-1，rk-2，⋯，r1,r0即为校验位.在接收端，将接收到的n+k位码除以相同的生成多项式g(x)，根据式(3)，所产生余数为零，就认为接收到的信息正确无误；否则就认为在传输过程中发生了误码.125.gif(2914bytes)file:///F
8、/qikan_htm抽取_2
9、000before/kjqk(200810)/dianzixb/dian99/dian9904/990438.htm（第2／6页）2009-12-3114:52:28电子学报990438图1 通用CRC串行电路 式(1)～(6)表示，CRC编码必须进行模-2除运算，CRC码的校验位就是模-2除的余数.如果余数用寄存器的存数表示，模-2运算用异或门表示，那么一个通用的CRC串行电路就可以用图1所示的电路来表示. 在图1中，r0,r1，⋯,rk-1表示k个二进制移位寄存器的存数，它由外部同步时钟启动移位.gi(i=1,2,⋯,
