《CRC原理 及算法总结》由会员分享，可在线阅读，更多相关《CRC原理 及算法总结（9页珍藏版）》请在金锄头文库上搜索。
1、引言引言CRC 的全称为 Cyclic Redundancy Check，中文名称为循环冗余校验。它是一 类重要的线性分组码，编码和解码方法简单，检错和纠错能力强，在通信领域 广泛地用于实现差错控制。实际上，除数据通信外，CRC 在其它很多领域也是 大有用武之地的。例如我们读软盘上的文件，以及解压一个 ZIP 文件时，偶尔 会碰到“Bad CRC”错误，由此它在数据存储方面的应用可略见一斑。差错控制理论是在代数理论基础上建立起来的。这里我们着眼于介绍 CRC的算法与实现，对原理只能捎带说明一下。若需要进一步了解线性码、分组码、 循环码、纠错编码等方面的原理，可以阅读有关资料。 利用利用 CRC
2、 进行检错进行检错的过程可简单描述为：在发送端根据要传送的 k 位二进制码序列，以一定的规则产生一个校验用的 r 位监督码(CRC 码)，附在原始信息后边，构成一个新的二进制码序列数共 k+r 位，然后发送出去。在接收端，根据信息码和 CRC 码之间所遵循的规则进行检验，以确定传送中是否出错。这个规则，在差错控制理论中称为“生成多项式” 。1 代数学的一般性算法代数学的一般性算法 在代数编码理论中，将一个码组码组表示为一个多项式，码组中各码元当作多 项式的系数。例如 1100101 表示为1x6+1x5+0x4+0x3+1x2+0x+1，即 x6+x5+x2+1。设: 编码前的原始信息原始信息
3、多项式为 P(x)，P(x)的最高幂次加 1 等于 k；生成多项式为 G(x)，G(x)的最高幂次等于r；CRC 多项式为 R(x)； 编码后的带 CRC 的信息多项式为 T(x)。 发送方编码方法：发送方编码方法： 将 P(x)乘以 xr (即对应的二进制码序列左移 r 位)，再除以 G(x)，所得余式 即为 R(x)。用公式表示为( )( )( )rT xx P xR x接收方解码方法：接收方解码方法： 将 T(x)除以 G(x)，如果余数为 0，则说明传输中无错误发生，否则说明传输 有误。 举例来说，设信息码为 1100，生成多项式为 1011，即 P(x)=x3+x2，G(x) =x3
4、+x+1，计算 CRC 的过程为 33265 32 333111rxxxx P xxxxxxxG xxxxxxx即 R(x)=x。注意到 G(x)最高幂次 r=3，得出 CRC 为 010。 如果用竖式除法，计算过程为1110- 1011 /1100000 (1100 左移 3 位)1011-11101011-10101011-00100000-010 因此，,即 1100000+010=110001033265( )( )( )()rT xx P xR xxxxxxxx如果传输无误，则接收端：无余式。65 32 3( )( ) 1T xxxxxxxG xxx回头看一下上面的竖式除法，如果被除
5、数是 1100010，显然在商第三个 1 时，就能除尽。 上述推算过程，有助于我们理解 CRC 的概念。但直接编程来实现上面的算 法，不仅繁琐，效率也不高。实际上在工程中不会直接这样去计算和验证 CRC。 下表中列出了一些见于标准的 CRC 资料：名称 生成多项式 简记式* 应用举例 CRC-4 x4+x+1 ITU G.704 CRC-12 x12+x11+x3+x+1 CRC-16 x16+x12+x2+1 1005 IBM SDLC CRC-ITU* x16+x12+x5+1 1021 ISO HDLC, ITU X.25, V.34/V.41/V.42, PPP-FCS CRC-32
6、x32+x26+x23+.+x2+x+1 04C11DB7 ZIP, RAR, IEEE 802 LAN/FDDI, IEEE 1394, PPP-FCS CRC-32c x32+x28+x27+.+x8+x6+1 1EDC6F41 SCTP * 生成多项式的最高幂次项系数是固定的 1，故在简记式中，将最高 的 1 统一去掉了，如 04C11DB7 实际上是 104C11DB7。* 前称 CRC-CCITT。ITU 的前身是 CCITT。2 硬件电路的实现方法 多项式除法，可用除法电路来实现。除法电路的主体由一组移位寄存器和 模 2 加法器(异或单元)组成。以 CRC-ITU 为例，它由 16
7、 级移位寄存器和 3 个加 法器 组成，见下图(编码/解码共用)。编码、解码前将各寄存器初始化为“1“， 信息位随着时钟移入。当信息位全部输入后，从寄存器组输出 CRC 结果。3 比特型算法 上 面的 CRC-ITU 除法电路，完全可以用软件来模拟。定义一个寄存器组， 初始化为全“1“。依照电路图，每输入一个信息位，相当于一个时钟脉冲到来， 从高 到低依次移位。移位前信息位与 bit0 相加产生临时位，其中 bit15 移入临 时位，bit10、bit3 还要加上临时位。当全部信息位输入完成后，从寄存 器组取 出它们的值，这就是 CRC 码。 typedef unsigned char bit
8、; typedef unsigned char byte; typedef unsigned short u16;typedef union u16 val;struct u16 bit0 : 1;u16 bit1 : 1;u16 bit2 : 1;u16 bit3 : 1;u16 bit4 : 1;u16 bit5 : 1;u16 bit6 : 1;u16 bit7 : 1;u16 bit8 : 1;u16 bit9 : 1;u16 bit10 : 1;u16 bit11 : 1;u16 bit12 : 1;u16 bit13 : 1;u16 bit14 : 1;u16 bit15 : 1;
9、 bits; CRCREGS;/ 寄存器组 CRCREGS regs;/ 初始化 CRC 寄存器组：移位寄存器置为全“1“ void crcInitRegisters() regs.val = 0xffff; / CRC 输入一个 bit void crcInputBit(bit in) bit a;a = regs.bits.bit0 in;regs.bits.bit0 = regs.bits.bit1;regs.bits.bit1 = regs.bits.bit2;regs.bits.bit2 = regs.bits.bit3;regs.bits.bit3 = regs.bits.bit4
10、 a;regs.bits.bit4 = regs.bits.bit5;regs.bits.bit5 = regs.bits.bit6;regs.bits.bit6 = regs.bits.bit7;regs.bits.bit7 = regs.bits.bit8;regs.bits.bit8 = regs.bits.bit9;regs.bits.bit9 = regs.bits.bit10;regs.bits.bit10 = regs.bits.bit11 a;regs.bits.bit11 = regs.bits.bit12;regs.bits.bit12 = regs.bits.bit13;
11、regs.bits.bit13 = regs.bits.bit14;regs.bits.bit14 = regs.bits.bit15;regs.bits.bit15 = a; / 输出 CRC 码(寄存器组的值) u16 crcGetRegisters() return regs.val; crcInputBit 中一步一步的移位/异或操作，可以进行简化：void crcInputBit(bit in) bit a;a = regs.bits.bit0 in;regs.val = 1;if(a) regs.val = 0x8408; 细心的话，可以发现 0x8408 和 0x1021(CRC
12、-ITU 的简记式)之间的关系。由 于我们是从低到高输出比特流的，将 0x1021 左右反转就得到 0x8408。将生成 多项式写成 G(x)=1+x5+x12+x16，是不是更好看一点？ 下面是一个典型的 PPP 帧。最后两个字节称为 FCS(Frame Check Sequence)， 是前面 11 个字节的 CRC。 FF 03 C0 21 04 03 00 07 0D 03 06 D0 3A 我们来计算这个 PPP 帧的 CRC，并验 证它。byte ppp13 = 0xFF, 0x03, 0xC0, 0x21, 0x04, 0x03, 0x00, 0x07, 0x0D, 0x03,
13、0x06, 0x00, 0x00;int i,j;u16 result;/ 以下计算 FCS/ 初始化crcInitRegisters();/ 逐位输入，每个字节低位在先，不包括两个 FCS 字节for(i = 0; i j) / 得到 CRC：将寄存器组的值求反result = crcGetRegisters();/ 填写 FCS，先低后高ppp11 = result ppp12 = (result 8) / 以下验证 FCS/ 初始化crcInitRegisters();/ 逐位输入，每个字节低位在先，包括两个 FCS 字节for(i = 0; i j) / 得到验证结果result =
14、crcGetRegisters(); 可以看到，计算出的 CRC 等于 0x3AD0，与原来的 FCS 相同。验证结果等于 0。初始化为全“1“，以及将寄存器组的值求反得到 CRC，都是 CRC-ITU 的要求。 事实上，不管初始化为全“1“还是全“0“，计算 CRC 取反还是不取反，得到的验 证结果都是 0。4 字节型算法比 特型算法逐位进行运算，效率比较低，不适用 于高速通信的场合。数字通信系统(各种通信标准)一般是对一帧数据进行 CRC 校验，而字节是帧的基本单位。最常 用的是一种按字节查表的快速算法。该算 法基于这样一个事实：计算本字节后的 CRC 码，等于上一字节余式 CRC 码的低
15、 8 位左移 8 位，加上上一字节 CRC 右移 8 位和本字节之和后所求得的 CRC 码。 如果我们把 8 位二进制序列数的 CRC(共 256 个)全部计算出来，放在一个表里 ，编码时只要从表中查找对应的值进行处理即可。 CRC-ITU 的计算算法如下：的计算算法如下： a.寄存器组初始化为全“1“(0xFFFF)。 b.寄存器组向右移动一个字节。 c.刚移出的那个字节与数据字节进行异或运算，得出一个指向值表的索引。d.索引所指的表值与寄存器组做异或运算。 f.数据指针加 1，如果数据没有全部处理完，则重复步骤 b。 g.寄存器组取反，得到 CRC，附加在数据之后。CRC-ITU 的验证算
16、法如下： a.寄存器组初始化为全“1“(0xFFFF)。b.寄存器组向右移动一个字节。 c.刚移出的那个字节与数据字节进行异或运算，得出一个指向值表的索引。d.索引所指的表值与寄存器组做异或运算。 e.数据指针加 1，如果数据没有全部处理完，则重复步骤 b (数据包括 CRC 的两个字节)。 f.寄存器组的值是否等于“Magic Value”(0xF0B8)，若相等则通过，否则失 败。 下面是通用的 CRC-ITU 查找表以及计算和验证 CRC 的 C 语言程序： / CRC-ITU 查找表 const u16 crctab16 = 0x0000, 0x1189, 0x2312, 0x329b, 0x4624, 0x57ad, 0x6536, 0
