CRC原理 及算法总结.docx

引言CRC 的全称为 Cyclic Redundancy Check ，中文名称为循环冗余校验它是一 类重要的线性分组码，编码和解码方法简单，检错和纠错能力强，在通信领域广 泛地用于实现差错控制实际上，除数据通信外，CRC在其它很多领域也是大有 用武之地的例如我们读软盘上的文件，以及解压一个ZIP文件时，偶尔会碰到 “Bad CRC ”错误，由此它在数据存储方面的应用可略见一斑差错控制理论是在代数理论基础上建立起来的这里我们着眼于介绍CRC 的算法与实现，对原理只能捎带说明一下若需要进一步了解线性码、分组码、 循环码、纠错编码等方面的原理，可以阅读有关资料利用 CRC 进行检错的过程可简单描述为：在发送端根据要传送的k位二进制码序列，以一定的规则产生一个校验用的r位监督码(CRC码)，附在原始信息后边，构成一个新的二进制码序列数共k+r位, 然后发送出去在接收端，根据信息码和CRC码之间所遵循的规则进行检验，以确定传送 中是否出错这个规则，在差错控制理论中称为“生成多项式”1 代数学的一般性算法 在代数编码理论中，将一个码组表示为一个多项式，码组中各码元当作多项 式的系数例如 1100101 表示为1 • xA6+1 • xA5+0 • xA4+0 • xA3+1 • xA2+0 • x+1，即 xA6+xA5+xA2+1o 设:编码前的原始信息多项式为P(x)，P(x)的最高幂次加1等于k；生成多项式为G(x)，G(x)的最高幂次等于r；CRC 多项式为 R(x)； 编码后的带 CRC 的信息多项式为 T(x)。

发送方编码方法：将P(x)乘以xAr(即对应的二进制码序列左移r位)，再除以G(x),所得余式即 为R(x)用公式表示为T (x)二 xrP( x) + R( x)接收方解码方法：将T(x)除以G(x)，如果余数为0，则说明传输中无错误发生，否则说明传输 有误举例来说，设信息码为 1100，生成多项式为 1011，即 P(x)=x3+x2， G(x)=x3+x+1，计算 CRC 的过程为XrP (x)).即R(x)=x注意到G(x)最高幂次r=3，得出CRC为010如果用竖式除法，计算过程为11101011 /1100000 （1100 左移3位）1011111010111010101100100000010因此，T(x)二 xrP(x) + R(x)二 x3(x3 + x2) + x 二 x6 + x5 + x，即 1100000+010=1100010如果传输无误，则接收端：T(x) x6 + x5 + x二 二 x3 + x2 + x 尢余式G(x) x3 + x +1回头看一下上面的竖式除法，如果被除数是1100010，显然在商第三个1时， 就能除尽上述推算过程，有助于我们理解CRC的概念。

但直接编程来实现上面的算法, 不仅繁琐，效率也不高实际上在工程中不会直接这样去计算和验证 CRC下表中列出了一些见于标准的 CRC 资料： 名称生成多项式简记式* 应用举例CRC-4x4+x+1ITU G.704CRC-12x12+x11+x3+x+1CRC-16 x16+x12+x2+1 1005IBM SDLCCRC-ITU**x16+x12+x5+11021ISO HDLC, ITU X.25, V.34/V.41/V.42, PPP-FCSCRC-32x32+x26+x23+...+x2+x+104C11DB7ZIP, RAR, IEEE 802 LAN/FDDI, IEEE 1394, PPP-FCSCRC-32cx32+x28+x27+...+x8+x6+11EDC6F41SCTP* 生成多项式的最高幂次项系数是固定的 1 ，故在简记式中，将最高 的 1 统一去掉了，如 04C11DB7 实际上是 104C11DB7 前称 CRC-CCITTITU 的前身是 CCITT2 硬件电路的实现方法多项式除法，可用除法电路来实现除法电路的主体由一组移位寄存器和模 2加法器（异或单元）组成。

以CRC-ITU为例，它由16级移位寄存器和3个加法器 组成，见下图（编码/解码共用）编码、解码前将各寄存器初始化为"1"，信息位 随着时钟移入当信息位全部输入后，从寄存器组输出 CRC 结果3 比特型算法上面的 CRC-ITU 除法电路，完全可以用软件来模拟定义一个寄存器组，初 始化为全"1"依照电路图，每输入一个信息位，相当于一个时钟脉冲到来，从 高到低依次移位移位前信息位与 bit0 相加产生临时位，其中 bit15 移入临时位， bit10、bit3 还要加上临时位当全部信息位输入完成后，从寄存器组取出它们的 值，这就是 CRC 码typedef unsigned char bit;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;} bits;} CRCREGS;// 寄存器组CRCREGS regs;// 初始化 CRC 寄存器组：移位寄存器置为全"1 void crcInitRegisters(){regs.val = 0xffff;}// CRC输入一个bitvoid crcInputBit(bit in){bit a;a = regs.bits.bit0 A 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 A 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 a;regs.bits.bit11 = regs.bits.bit12;regs.bits.bit12 = regs.bits.bit13;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 A in;regs.val >>= 1;if(a) regs.val A= 0x8408;}细心的话，可以发现0x8408和0x1021(CRC-ITU的简记式)之间的关系。

由于 我们是从低到高输出比特流的，将0x1021左右反转就得到0x8408将生成多项 式写成G(x)=1+x5+x12+x16,是不是更好看一点？下面是一个典型的 PPP 帧最后两个字节称为 FCS(Frame Check Sequence)， 是前面 11 个字节的 CRCFF 03 C0 21 04 03 00 07 0D 03 06 D0 3A 我们来计算这个PPP帧的CRC，并验 证它byte ppp[13] = {0xFF, 0x03, 0xC0, 0x21, 0x04, 0x03, 0x00, 0x07, 0x0D, 0x03, 0x06, 0x00, 0x00};int i,j;u16 result;/////////// 以下计算 FCS// 初始化crcInitRegisters();// 逐位输入，每个字节低位在先，不包括两个 FCS 字节for(i = 0; i < 11; i++){for(j = 0; j < 8; j++){crcInputBit((ppp[i] >> j) & 1);}}//得到CRC：将寄存器组的值求反result = ~crcGetRegisters();//填写FCS,先低后咼 ppp[11] = result & 0xff; ppp[12] = (result >> 8) & 0xff;/////////// 以下验证 FCS// 初始化crcInitRegisters();// 逐位输入,每个字节低位在先,包括两个 FCS 字节for(i = 0; i < 13; i++){for(j = 0; j < 8; j++){crcInputBit((ppp[i] >> j) & 1);}}// 得到验证结果result = crcGetRegisters();可以看到，计算出的CRC等于0X3AD0,与原来的FCS相同。

验证结果等于 0初始化为全"1"，以及将寄存器组的值求反得到CRC，都是CRC-ITU的要求 事实上，不管初始化为全"1"还是全"0"，计算 CRC 取反还是不取反，得到的验证 结果都是 0 4 字节型算法比特型算法逐位进行运算，效率比较低，不适用于咼 速通信的场合数字通信系统(各种通信标准)一般是对一帧数据进行 CRC 校验， 而字节是帧的基本单位最常用的是一种按字节查表的快速算法该算法基于这 样一个事实：计算本字节后的 CRC 码，等于上一字节余式 CRC 码的低 8 位左移 8 位，加上上一字节 CRC 右移 8 位和本字节之和后所求得的 CRC 码如果我们把 8位二进制序列数的CRC(共256个)全部计算出来，放在一个表里，编码时只要 从表中查找对应的值进行处理即可CRC-ITU 的计算算法如下：a. 寄存器组初始化为全"1"(0xFFFF)ob. 寄存器组向右移动一个字节c. 刚移出的那个字节与数据字节进行异或运算，得出一个指向值表的索引d. 索引所指的表值与寄存器组做异或运算f. 数据指针加1,如果数据没有全部处理完，则重复步骤bg. 寄存器组取反，得到CRC，附加在数据之后。

CRC-ITU 的验证算法如下：a. 寄存器组初始化为全"1"(0xFFFF)ob. 寄存器组向右移动一个字节c. 刚移出的那个字节与数据字节进行异或运算，得出一个指向值表的索引。