crc的循环冗余校正.docxVIP

crc的循环冗余校正 1 编码/转换编码 为了确保系统数据的准确性，需要限制通信过程中的差异。其主要方式有3种:前向纠错 (FEC) 、反馈重传 (ARQ) 和混合纠错 (HEC) 。FEC方式是发送端发送有一定纠错能力的码, 接收端能在码的纠错能力内进行自动纠错, 它用于传输误码率较低的场合;ARQ方式是发送端发送有一定检错能力的码, 接收端如发现传输有错, 则通知发端重发;HEC方式是FEC和ARQ的结合。 在许多数字通信中, 广泛采用ARQ方式, 此时的差错控制只需要检错功能, 校验码 (Check-Sum) 与循环冗余校验 (Cyclic Redundancy Check, 简称CRC) , 是常用的两种校验方式。 本文首先介绍了CRC如何实现检错, 然后提出了两种程序实现方法:基于位运算计算CRC和基于半字节查表计算CRC的方法, 最后简单分析了几种计算CRC方法所适用的场合。 2 检查的原则和方法 2.1 合成上传字符 Check Sum的方法是将所有传送字符的ASCII码相加, 其和除以另一数字 (通常是255) , 取其余数, 并将此余数组合成传送字符串的一部分传送出去;同样, 接收端也把传送过来的字符串的ASCII码相加求和, 然后取余数, 与发送方送过来的值作对比, 若其值一样则代表传送的字符串是正确的, 反之是错误的。 2.2 crc编码分析 设G (x) 为CRC-CCITT生成多项式, 最高项次数r=16, g (x) =1+x5+x12+x16;m (x) 为信息多项式, 长度为k, k<32767; s (x) 为编码发送多项式, 长度为n, n=k+r; r (x) 为编码接收多项式, 长度为n; e (x) 为差错多项式, 长度为n; p (x) 为商多项式; q (x) 为余式多项式, 最高项次数小于r。 CRC编码分析在GF (2) 域上进行, 分析工具是近世代数的多项式理论。设 两边同时加余式q (x) , 有 如果e (x) =0, 则r (x) =p (x) g (x) 一定可以被g (x) 整除, 这就是CRC的检错原理。 2.2 接收方解码方法 CRC码的基本思想是:在发送方将要传送的m位二进制信息码序列, 以共同约定的生成多项式G (x) 产生一个校验用的r位CRC校验码, 附加在原始信息后边, 并将这m+r位的信息发送出去, 在收方接收时, 用G (x) 去除它, 若有余数, 则传输出错。 发送方编码的过程是: (1) 设G (x) 为r阶, 在要处理的信息位串M (x) 末尾添加r个0, 使数据块为m+r位, 则相应的多项式为xrM (x) 。 (2) 用对应于G (x) 的二进制数串去除对应于xrM (x) 的位串, 求得余数位串 (运算中采用模2加, 即XOR) 。 (3) 从对应于xrM (x) 的位串中减去 (等同于XOR运算) 余数位串, 结果即为要处理的信息位串生成的CRC循环冗余码, 其中前m位是原信息位, 后面r位是CRC校验位。 接收方解码方法的处理过程是:接收方收到的编码为M′ (x) , 将它除以共同约定的生成多项式G (x) , 如果等于0, 则说明信道没有受到干扰。 由此可见, 不管采用Check Sum或是CRC, 它们都是将所传送的数值连同余数一起发送出去, 然后在接收端进行校验。如果传送的数据量不大的话, 使用Check Sum的方式就足够了;如果数据量大的话, 仅使用Check Sum可以检查的错误就有限了;据理论统计, 使用CRC16时, 超过17个连续位的错误侦测率有99.9969%, 小于此17个连续位的错误侦测率则有100%。 目前较常使用的CRC位数有8、16、32。CRC位数越大, 则数据越不容易受干扰, 不过会降低运算速度。 常用的CRC码已成为国际标准, 有下列四种: CRC-12:其生成多项式为g (x) =1+x+x2+x3+x11+x12; CRC-16:其生成多项式为g (x) =1+x2+x15+x16; CRC-CCITT:其生成多项式为g (x) =1+x5+x12+x16; CRC-32:其生成多项式为g (x) =1+x+x2+x4+x5+x7+x8+x10+x11+x12+x16+x22+x23+x26+x32。 3 通信数据量小时 CRC算法实现方式主要有两种:按位计算法和查表法。在每次通信数据量小的情况下, 采用按位计算法;而在高速通信和长数据传送的时候, 为提高计算机的处理速度, 一般采用查表法。 3.1 按位计算crc的流程 M (x) 为有效信息串, 其长度可以确定模2除法的次数;G (x) 为多项式, 如采用CCITT, G (x) 的阶数r, r确定了冗余位串的位数, 冗余位串占两个字节