一种多通道串行通信中循环冗余码校正算法.docxVIP

一种多通道串行通信中循环冗余码校正算法 在分布式循环系统中，通常使用并行通信技术来执行低级别控制计算机和上层计算机之间的数据传输。由于工业应用环境的干扰因素，阵列通信可能会丢失。为了确保网络系统的可靠性，必须采用分布式误差控制技术来纠正矩阵通信中的错误。建立循环冗余代码更新（crc）的技术在并行通信的欺诈控制中得到了广泛应用。 本文详细介绍了一种采用分段查表法实现的CRC快速算法,该算法只需占用32字节的存储单元,适合在内部存储单元较少的小型控制器中使用. 1 crc校验算法的实现 CRC码是一种多项式编码.若通信中要传送的数据有m位,则可将其看成是多项式M(x)=am-1xm-1+am-2xm-2+…+a0x0,ai=0或1,i=0,1,…,m-1.通信双方需约定一个阶数为r的生成多项式G(x),发送方计算M(x)xr/G(x)的余式,并将其系数作为校验和附加在数据帧后面一起发送.接收方用G(x)去除接收到的带校验和的帧,如果没有余数,则传输正确,否则存在错误. 用软件实现CRC校验的算法可分为2类:一种是根据CRC校验的原理实现的基本算法,通过大量的移位、比较和异或操作实现模2除法来计算CRC码,运算时间较长,实时性较差;另一种是基于字节查表法实现的CRC快速算法,其特点是预先计算好0到255的CRC码,以表格形式存储,计算整个数据帧的CRC码时,依次按字节查表进行递推运算.这种方法的运算速度较快,但是需要512个字节的存储空间,即通过牺牲算法的空间复杂度来减少算法的时间复杂度.在分布式控制系统中,许多底层小型控制设备中的存储单元有限,因此在考虑CRC校验的实时性要求的同时,也必须兼顾对存储单元数量的要求. 2 n+n,型n 分布式控制系统中上下位机之间的数据通信是以字节为单位的,每个数据帧由多个字节构成.多字节数据帧的CRC码可以通过单字节CRC码的递推算法实现. 设Mn(x)表示n个字节的数据帧,如果采用的生成多项式为G(x)=x16+x12+x5+1(国际电报电话咨询委员会CCITT推荐使用),则根据CRC校验原理有 Μn(x)x16G(x)=Qn(x)+Rn(x)G(x)=Qn(x)+x8Rn,Η(x)+Rn,L(x)G(x)(1)Re[Μn(x)x16G(x)]=Rn(x)=x8Rn,Η(x)+Rn,L(x)(2) 式中:Qn(x)为商;Rn(x)为余数,即Mn(x)的CRC码;Rn,H(x)和Rn,L(x)分别为CRC码的高、低字节;Re[A/B]表示求A/B的余数的运算. 以Mn+1(x)表示在Mn(x)的最低位增加一个字节形成的n+1个字节的数据帧,即Mn+1(x)=x8Mn(x)+M0(x),其中M0(x)表示新增字节对应的多项式,由式(1)有 Μn+1(x)x16G(x)=Μn(x)x8x16+Μ0(x)x16G(x)=Qn(x)x8+x8Rn,Η(x)+Rn,L(x)G(x)x8+Μ0(x)x16G(x)=Qn(x)x8+(Rn,Η(x)+Μ0(x))x16G(x)+Rn,Lx8G(x)=Qn(x)x8+Μ′(x)G(x)+Rn,L(x)x8G(x)=Qn(x)x8+ Q′(x)+R′(x)G(x)+Rn,L(x)x8G(x)=Qn(x)x8+Q′(x)+ x8R′Η(x)+R′L(x)G(x)+Rn,L(x)x8G(x)=Qn(x)x8+Q′(x)+x8(R′Η(x)+Rn,L(x))G(x)+R′L(x)G(x)(3) 则 Re[Μn+1(x)x16G(x)]=Rn+1(x)=x8(R′Η(x)+Rn,L(x))+R′L(x)(4) 式中:M′(x)表示将Rn,H(x)与M0(x)异或得到一个新字节;Q′(x)表示M′(x)/G(x)的商;R′(x)表示M′(x)的CRC码;R′H(x)和R′L(x)为R′(x)的高、低字节. 根据式(3)、式(4)的推导过程,当用已知的Mn(x)的CRC码Rn(x)求Mn+1(x)的校验码Rn+1(x)时,先将Rn,H(x)与M0(x)异或得到一个新字节M′(x),计算该字节的CRC码R′(x),则Rn+1(x)的高字节为R′(x)的高字节R′H(x)与Rn,L(x)异或,Rn+1(x)的低字节为R′(x)的低字节R′L(x).显然,该算法是一个递推算法,从数据帧的第一个字节开始,依次递推运算,便可求得整个数据帧的CRC码.算法的核心运算是计算每个字节的CRC码.为了提高算法的运算速度,可以预先计算出一个字节所有可能取的值(0~255)所对应的CRC码,做成一个表格.这样,在计算数据帧的CRC码的递推算法中,通过查表快速取得每个字节的CRC码,可加快递推算法的运算速度,这种算法就是基于字节查表的CRC快速算法. 由于一个字节数据的取值有256种可能,因此对应的