资源预览内容
第1页 / 共9页
第2页 / 共9页
第3页 / 共9页
第4页 / 共9页
第5页 / 共9页
第6页 / 共9页
第7页 / 共9页
第8页 / 共9页
第9页 / 共9页
亲,该文档总共9页全部预览完了,如果喜欢就下载吧!
资源描述
引言引言CRC 的全称为 Cyclic Redundancy Check,中文名称为循环冗余校验。它是一 类重要的线性分组码,编码和解码方法简单,检错和纠错能力强,在通信领域 广泛地用于实现差错控制。实际上,除数据通信外,CRC 在其它很多领域也是 大有用武之地的。例如我们读软盘上的文件,以及解压一个 ZIP 文件时,偶尔 会碰到“Bad CRC”错误,由此它在数据存储方面的应用可略见一斑。差错控制理论是在代数理论基础上建立起来的。这里我们着眼于介绍 CRC的算法与实现,对原理只能捎带说明一下。若需要进一步了解线性码、分组码、 循环码、纠错编码等方面的原理,可以阅读有关资料。 利用利用 CRC 进行检错进行检错的过程可简单描述为:在发送端根据要传送的 k 位二进制码序列,以一定的规则产生一个校验用的 r 位监督码(CRC 码),附在原始信息后边,构成一个新的二进制码序列数共 k+r 位,然后发送出去。在接收端,根据信息码和 CRC 码之间所遵循的规则进行检验,以确定传送中是否出错。这个规则,在差错控制理论中称为“生成多项式” 。1 代数学的一般性算法代数学的一般性算法 在代数编码理论中,将一个码组码组表示为一个多项式,码组中各码元当作多 项式的系数。例如 1100101 表示为1x6+1x5+0x4+0x3+1x2+0x+1,即 x6+x5+x2+1。设: 编码前的原始信息原始信息多项式为 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+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回头看一下上面的竖式除法,如果被除数是 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 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 级移位寄存器和 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 输入一个 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 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;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-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, 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 = 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)。 b.寄存器组向右移动一个字节。 c.刚移出的那个字节与数据字节进行异或运算,得出一个指向值表的索引。d.索引所指的表值与寄存器组做异或运算。 f.数据指针加 1,如果数据没有全部处理完,则重复步骤 b。 g.寄存器组取反,得到 CRC,附加在数据之后。CRC-ITU 的验证算法如下: 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
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号