循环冗余校验信息单元编码算法的研究

循环冗余校验信息单元编码算法的研究

0crc编码在重要数据通讯时的应用在数字通信过程中，由于信道的干扰，接收到的二进制数字与发送的不一致，导致“0”和“1”的无序更改。为了让信息社知道接收信息的准确性，有必要验证信息的准确性，纠正或发送错误。循环冗余验证crc（cyclicrequirequi），又称编码，是一种高效、简单、易于实现的通信编码。这是目前最广泛使用的验证方法。理论证明，r级crc可以测试所有形状的错误、所有相位的错误以及长度小于或等于r级的突然错误。crc码的检误率远远优于通常的奇偶检验。因此，crc验证可以应用于重要数据的通信环境，检测以下状态状态、运行模式或参数的在线设置。DNP3.0(DistributedNetworkProtocolVersion3.0)规约是在欧洲及北美比较流行的一种规约.它可用于电力系统子站系统、远程终端装置RTU(RemoteTerminalUnit)、智能电子设备IEDs(IntelligentElectronicDevices)以及主站系统之间的通信.在此规约中,为保证传输数据的可靠性,报文的报头、每个数据块都需进行CRC校验,而且CRC的计算是从数据的低字节低位开始的.DNP3.0的数据帧格式及CRC计算规则可参考文献.目前对CRC算法的研究都是按正序进行分析的,而在实际应用中CRC的计算几乎都是按低字节低位进行的,对此文献提出了信息位反转计算方法,而文献则从生成多项式逆序的角度进行CRC计算.本文在此基础上进一步分析CRC计算的信息位反转法与生成多项式反转法,并以DNP3.0中的CRC计算为例详细说明了CRC编解码算法的规则.1crc编码算法1.1数符合gx次数的余式CRC信息单元编码算法就是把待求CRC的信息按一定的位数分成若干块,找出相邻块之间CRC的关系,进而推求出整个信息的CRC的方法.假设把信息m按i位为一块进行划分,最左边的一块如果不够i位,可以补0,共划分为K块:m=[MK-1,MK-2,…,M1,M0],其中Mj(0≤j≤K-1)是由i个信息位组成的一个信息块.此时信息多项式为m(x)=MK-1xi(K-1)+MK-2xi(K-2)+…+M1xi+M0.(1)设生成多项式为g(x),其次数为r阶.那么求信息位的CRC方法如下:xrm(x)g(x)=Xi(k-1)ΜΚ-1xrg(x)xi(Κ-1)+ΜΚ-2xrg(x)xi(Κ-2)+⋯+Μ1xrg(x)xi+Μ0xrg(x).(2)xrm(x)g(x)=Xi(k−1)MK−1xrg(x)xi(K−1)+MK−2xrg(x)xi(K−2)+⋯+M1xrg(x)xi+M0xrg(x).(2)设ΜΚ-1xrg(x)=QΚ-1(x)+Rk-1(x)g(x),(3)MK−1xrg(x)=QK−1(x)+Rk−1(x)g(x),(3)式中:QK-1(x)为商;RK-1(x)为次数小于g(x)次数的余式.将式(3)代入式(2)得到xrm(x)g(x)=QΚ-1(x)xΚ-1+[RΚ-1(x)⋅xig(x)+ΜΚ-2xrg(x)]xi(Κ-2)+⋯+Μ1xrg(x)xj+Μ0xrg(x).(4)xrm(x)g(x)=QK−1(x)xK−1+[RK−1(x)⋅xig(x)+MK−2xrg(x)]xi(K−2)+⋯+M1xrg(x)xj+M0xrg(x).(4)再设RΚ-1(x)⋅xi+ΜΚ-2xrg(x)=QΚ-2(x)+RΚ-2(x)g(x).(5)RK−1(x)⋅xi+MK−2xrg(x)=QK−2(x)+RK−2(x)g(x).(5)式中:QK-2(x)为商;RK-2(x)为次数小于g(x)次数的余式.把式(5)代入式(4)可类推得到xrm(x)g(x)=QΚ-1(x)xi(Κ-1)+QΚ-2(x)xi(Κ-2)+⋯+Q0(x)+R0(x)g(x)xrm(x)g(x)=QK−1(x)xi(K−1)+QK−2(x)xi(K−2)+⋯+Q0(x)+R0(x)g(x),(6)式中:R0(x)就是要求的校验码.式(5)反映了相邻信息块之间CRC的关系,下面对其进行详细分析.为此,设RK-1(x)的形式如下RK-1(X)=RK-1,r-1xr-1+…+RK-1,r-ixr-i+RK-1,r-i-1xr-i-1+…+RK-1,0=RK-1,Hbxr-i+RK-1,Lb(x)(7)式中:RK-1,Hb=RK-1,r-1xj-1+…+RK-1,r-i为余式的高i位;RK-1,Lb(x)=RK-1,r-ixr-i-1+…+RK-1,0为余式的低位.如果余式位数少于i位,需要在余式右端补0凑够高i位,余式的低位可省去,或当作全0对待.把式(7)代入式(5)可得到RΚ-1(x)⋅xi+ΜΚ-2xrg(x)=RΚ-1,Ηb(x)xr+ΜΚ-2xrg(x)+RΚ-1,Lb⋅xig(x)=QΚ-2(x)+RΚ-2(x)g(x).(8)RK−1(x)⋅xi+MK−2xrg(x)=RK−1,Hb(x)xr+MK−2xrg(x)+RK−1,Lb⋅xig(x)=QK−2(x)+RK−2(x)g(x).(8)由此可得到在已知前一信息块Mj+1的校验码Rj+1(x)的情况下,本字节Mj的校验码Rj(x)的算法如下:首先,把本信息块Mj与Rj+1(x)的高i位Rj+1,Hb(x)做异或运算:M′j(x)=Mj+Rj+1,Hb(x);其次,求字节M′j(x)的CRC,得到R′j(x);第三,把Rj+1(x)的低位Rj+1,Lb(x)左移i位,得到Rj+1,Lb(x)·xi;第四,得到本字节Mj的CRC为Rj(x)=R′j(x)+Rj+1,Lb(x)·xi.算法流程如图1所示.图1中生成多项式的码字是生成多项式去掉最左端的“1”后所得到的二进制序列.比如,生成多项式g(x)=xr+gr-1xr-1+…+g0x+1,其码字为gr-1…g01,从左到右4位一块可得到十六进制表示.另外,信息被划分为块后,放入结构数组中.图1中的运算都是以左端对齐进行的.若信息块中的位数i小于生成多项式的阶数r,则需在信息块的右端补0到r位为止.若生成多项式的阶数r小于信息块中的位数i,则需在生成多项式的右端补0到i位,再进行运算,最后结果是取CRC左端的r位即是要求的CRC码.常用的信息分块方法有按位分块法(i=1)与按字节分块法(i=8),分别对应于按位求CRC的方法与按字节求CRC的方法.以上介绍的方法是从高位高字节开始计算的,实际中还有传输数据是从低位低字节开始的情况,此时CRC的计算也要从低位低字节开始.考虑到前面的算法,有2种处理方法:一是信息位反转法,即把待求CRC字节的高低位反转,生成多项式高低位排列不变,按前述算法求出CRC后再反转过来即可;二是生成多项式反转法,即把生成多项式的高低位反转,信息字节与位的排列是高字节高位在左、低字节低位在右,从低字节低位开始运算.这只要把前述方法的左移(即升高阶次)变成右移(降低阶次)进行运算即可.假设有n个字节在数组中的存放关系是低字节在前高字节在后,那么CRC的2种计算方法示意图如图2所示.1.2接收数据是发送数据且被生成分布式除尽发送的数据是按照信息位加上校验位的方式进行发送的.对接收数据进行校验的方法是用同样的生成多项式g(x)直接去除接收数据,若除尽,说明数据传输正确,此时把接收到的二进制序列去掉尾部校验位即得信息;若不能除尽,则说明一定有传输错误,需要进行相应的纠错或重发处理.假设发送数据为Txd(x)=xrm(x)+R(x),收到的数据为Rxd(x)=xrm′(x)+R′(x),用同样的生成多项式g(x)直接去除接收数据,当Txd(x)=Rxd(x)时有Rec(x)g(x)=xrm(x)+R(x)g(x)=Q(x)+R(x)+R(x)g(x)=Q(x)+R(x)+R(x)g(x)=Q(x),(9)这说明,当接收到的数据是发送数据时,此数据能被生成多项式除尽.在有信道干扰的情况下,接收的数据可能不是发送的数据,但此数据同样能被生成多项式除尽,此时接收方仍认为是发送数据,这是由校验码的检错能力有限造成的;在除不尽的情况下,肯定数据传输错误,此时可以采用丢弃、自动纠错或申请重发等处理方式.CRC解码算法的流程如图3所示.2dyn3的crc算法流程和编程2.1rc的计算流程DNP3.0所采用的生成多项式为g(x)=x16+x13+x12+x11+x10+x8+x6+x5+x2+1,所以CRC校验码为2个字节长.规则规定CRC的计算是从低字节低位开始的.生成多项式的反转为g′(x)=1+x2+x5+x6+x8+x10+x11+x12+x13+x16,其二进制序列为10100110101111001,略去最右端的1,得到其码字为0xA6BC,即GEN=0XA6BC.依照流程图1,把其中的左移变为右移,左对齐计算变为右对齐计算,可以得到按字节分块的从低字节低位开始的CRC计算流程如图4所示.以下单片机C语言程在keilμVision8.08a环境下编写并调试通过.2.2uhar-te-crc见表1#defineucharunsignedchar#defineuintunsignedint#defineGEN0xA6BC//生成多项式:g(x)=x16+x13+x12+x11+x10+x8+x6+x5+x2+1的反转码字/*计算1个字节的CRC,参数ucharabyte是要计算其CRC的字节*/uintcalcrc_1byte(ucharabyte){uchari;uintcrc=0;for(i=0;i<8;i++){/*前1位的crc的末位与本位相异或,当异或运算的结果末位为1时,再与生成多项式进行异或运算*/if((crc^abyte)&0x01){crc>>=1;crc^=GEN;}else//否则只是crc右移1位crc>>=1;abyte>>=1;}return(crc);}/*计算多个字节的CRC,参数uchar*p是指向计算其CRC的字节数组的指针,ucharlen是字节长度*/uintcalcrc_bytes(ucharidata*p,uintlen){uintcrc=0;while(len!=0){/*本字节的CRC与前面计算过的CRC相异或*/crc=(crc>>8)^calcrc_1byte((crc^*p)&0x0ff);p++;/*指向下一字节*/len--;/*剩下未计算CRC的字节数*/}return(crc);}多字节计算需要调用单字节求CRC的函数,由于字节取值共有0～255种情况,如果先由calcrc_1byte()函数把每种情况的CRC计算出来,放到数组中,那么就可以根据待求字节通过查找数组中对应的CRC来计算多字节的CRC,这就是按字节查表计算法.2.3entemp、要素更新计算bitrec_check(uchar*p,uintlen){bitflag;uinttemp;