<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<!-- saved from url=(0043)http://gyx.8800.org/files/read.php?recid=11 -->
<HTML><HEAD><TITLE>CRC算法与实现</TITLE>
<META http-equiv=Content-Type content="text/html; charset=gb2312"><LINK
href="CRC算法与实现.files/common.css" type=text/css rel=stylesheet>
<META content="MSHTML 6.00.2800.1106" name=GENERATOR></HEAD>
<BODY bgColor=#ffffff>
<P align=center><BR><B>CRC算法与实现</B></P>
<DIV align=center>
<CENTER>
<TABLE cellSpacing=0 cellPadding=0 width="85%" border=0>
<TBODY>
<TR>
<TD class=s noWrap><BR>阅读次数:5166</TD>
<TD class=s noWrap align=right><BR>2004-02-25 16:21:23</TD></TR>
<TR>
<TD colSpan=2>
<HR color=#c0c0c0 SIZE=1>
</TD></TR>
<TR>
<TD colSpan=2>
<DIV align=center>
<CENTER>
<TABLE border=0>
<TBODY>
<TR>
<TD>
<P>CRC算法与实现 bhw98(原作) <BR><BR>关键字 CRC, FCS, 生成多项式, 检错重传
<BR><BR><BR><BR>摘要:
本文首先讨论了CRC的代数学算法,然后以常见的CRC-ITU为例,通过硬件电路的实现,引出了比特型算法,最后重点介绍了字节型快速查表算法,给出了相应的C语言实现。
<BR><BR>关键词: CRC, FCS, 生成多项式, 检错重传 <BR><BR><BR><BR>引言
<BR><BR>CRC的全称为Cyclic Redundancy
Check,中文名称为循环冗余校验。它是一类重要的线性分组码,编码和解码方法简单,检错和纠错能力强,在通信领域广泛地用于实现差错控制。实际上,除数据通信外,CRC在其它很多领域也是大有用武之地的。例如我们读软盘上的文件,以及解压一个ZIP文件时,偶尔会碰到“Bad
CRC”错误,由此它在数据存储方面的应用可略见一斑。
<BR><BR>差错控制理论是在代数理论基础上建立起来的。这里我们着眼于介绍CRC的算法与实现,对原理只能捎带说明一下。若需要进一步了解线性码、分组码、循环码、纠错编码等方面的原理,可以阅读有关资料。
<BR><BR>利用CRC进行检错的过程可简单描述为:在发送端根据要传送的k位二进制码序列,以一定的规则产生一个校验用的r位监督码(CRC码),附在原始信息后边,构成一个新的二进制码序列数共k+r位,然后发送出去。在接收端,根据信息码和CRC码之间所遵循的规则进行检验,以确定传送中是否出错。这个规则,在差错控制理论中称为“生成多项式”。
<BR><BR><BR><BR>1 代数学的一般性算法
<BR><BR>在代数编码理论中,将一个码组表示为一个多项式,码组中各码元当作多项式的系数。例如 1100101 表示为
<BR>1·x6+1·x5+0·x4+0·x3+1·x2+0·x+1,即 x6+x5+x2+1。
<BR><BR>设编码前的原始信息多项式为P(x),P(x)的最高幂次加1等于k;生成多项式为G(x),G(x)的最高幂次等于r;CRC多项式为R(x);编码后的带CRC的信息多项式为T(x)。
<BR><BR>发送方编码方法:将P(x)乘以xr(即对应的二进制码序列左移r位),再除以G(x),所得余式即为R(x)。用公式表示为
<BR>T(x)=xrP(x)+R(x)
<BR><BR>接收方解码方法:将T(x)除以G(x),如果余数为0,则说明传输中无错误发生,否则说明传输有误。
<BR><BR>举例来说,设信息码为1100,生成多项式为1011,即P(x)=x3+x2,G(x)=x3+x+1,计算CRC的过程为
<BR><BR>xrP(x) x3(x3+x2) x6+x5 x <BR>-------- = ---------- =
-------- = (x3+x2+x) + -------- <BR>G(x) x3+x+1 x3+x+1 x3+x+1
<BR><BR>即 R(x)=x。注意到G(x)最高幂次r=3,得出CRC为010。 <BR><BR>如果用竖式除法,计算过程为
<BR><BR>1110 <BR>------- <BR>1011 /1100000 (1100左移3位) <BR>1011
<BR>---- <BR>1110 <BR>1011 <BR>----- <BR>1010 <BR>1011 <BR>-----
<BR>0010 <BR>0000 <BR>---- <BR>010
<BR><BR>因此,T(x)=(x6+x5)+(x)=x6+x5+x, 即 1100000+010=1100010
<BR><BR>如果传输无误, <BR><BR>T(x) x6+x5+x <BR>------ = --------- =
x3+x2+x, <BR>G(x) x3+x+1
<BR><BR>无余式。回头看一下上面的竖式除法,如果被除数是1100010,显然在商第三个1时,就能除尽。
<BR><BR>上述推算过程,有助于我们理解CRC的概念。但直接编程来实现上面的算法,不仅繁琐,效率也不高。实际上在工程中不会直接这样去计算和验证CRC。
<BR><BR>下表中列出了一些见于标准的CRC资料: <BR><BR>名称 生成多项式 简记式* 应用举例 <BR>CRC-4
x4+x+1 ITU G.704 <BR>CRC-12 x12+x11+x3+x+1 <BR>CRC-16 x16+x12+x2+1
1005 IBM SDLC <BR>CRC-ITU** x16+x12+x5+1 1021 ISO HDLC, ITU X.25,
V.34/V.41/V.42, PPP-FCS <BR>CRC-32 x32+x26+x23+...+x2+x+1 04C11DB7
ZIP, RAR, IEEE 802 LAN/FDDI, IEEE 1394, PPP-FCS <BR>CRC-32c
x32+x28+x27+...+x8+x6+1 1EDC6F41 SCTP <BR><BR>*
生成多项式的最高幂次项系数是固定的1,故在简记式中,将最高的1统一去掉了,如04C11DB7实际上是104C11DB7。 <BR>**
前称CRC-CCITT。ITU的前身是CCITT。 <BR><BR><BR>2 硬件电路的实现方法
<BR><BR>多项式除法,可用除法电路来实现。除法电路的主体由一组移位寄存器和模2加法器(异或单元)组成。以CRC-ITU为例,它由16级移位寄存器和3个加法器组成,见下图(编码/解码共用)。编码、解码前将各寄存器初始化为"1",信息位随着时钟移入。当信息位全部输入后,从寄存器组输出CRC结果。
<BR><BR><BR><BR><BR><BR>3 比特型算法
<BR><BR>上面的CRC-ITU除法电路,完全可以用软件来模拟。定义一个寄存器组,初始化为全"1"。依照电路图,每输入一个信息位,相当于一个时钟脉冲到来,从高到低依次移位。移位前信息位与bit0相加产生临时位,其中bit15移入临时位,bit10、bit3还要加上临时位。当全部信息位输入完成后,从寄存器组取出它们的值,这就是CRC码。
<BR><BR>typedef unsigned char bit; <BR>typedef unsigned char byte;
<BR>typedef unsigned short u16; <BR><BR>typedef union { <BR>u16 val;
<BR>struct { <BR>u16 bit0 : 1; <BR>u16 bit1 : 1; <BR>u16 bit2 : 1;
<BR>u16 bit3 : 1; <BR>u16 bit4 : 1; <BR>u16 bit5 : 1; <BR>u16 bit6 :
1; <BR>u16 bit7 : 1; <BR>u16 bit8 : 1; <BR>u16 bit9 : 1; <BR>u16
bit10 : 1; <BR>u16 bit11 : 1; <BR>u16 bit12 : 1; <BR>u16 bit13 : 1;
<BR>u16 bit14 : 1; <BR>u16 bit15 : 1; <BR>} bits; <BR>} CRCREGS;
<BR><BR>// 寄存器组 <BR>CRCREGS regs; <BR><BR>// 初始化CRC寄存器组:移位寄存器置为全"1"
<BR>void crcInitRegisters() <BR>{ <BR>regs.val = 0xffff; <BR>}
<BR><BR>// CRC输入一个bit <BR>void crcInputBit(bit in) <BR>{ <BR>bit a;
<BR><BR>a = regs.bits.bit0 ^ in; <BR><BR>regs.bits.bit0 =
regs.bits.bit1; <BR>regs.bits.bit1 = regs.bits.bit2;
<BR>regs.bits.bit2 = regs.bits.bit3; <BR>regs.bits.bit3 =
regs.bits.bit4 ^ a; <BR>regs.bits.bit4 = regs.bits.bit5;
<BR>regs.bits.bit5 = regs.bits.bit6; <BR>regs.bits.bit6 =
regs.bits.bit7; <BR>regs.bits.bit7 = regs.bits.bit8;
<BR>regs.bits.bit8 = regs.bits.bit9; <BR>regs.bits.bit9 =
regs.bits.bit10; <BR>regs.bits.bit10 = regs.bits.bit11 ^ a;
<BR>regs.bits.bit11 = regs.bits.bit12; <BR>regs.bits.bit12 =
regs.bits.bit13; <BR>regs.bits.bit13 = regs.bits.bit14;
<BR>regs.bits.bit14 = regs.bits.bit15; <BR>regs.bits.bit15 = a;
<BR>} <BR><BR>// 输出CRC码(寄存器组的值) <BR>u16 crcGetRegisters() <BR>{
<BR>return regs.val; <BR>} <BR><BR>crcInputBit中一步一步的移位/异或操作,可以进行简化:
<BR><BR>void crcInputBit(bit in) <BR>{ <BR>bit a; <BR>a =
regs.bits.bit0 ^ in; <BR>regs.val >>= 1; <BR>if(a) regs.val ^=
0x8408; <BR>}
<BR><BR>细心的话,可以发现0x8408和0x1021(CRC-ITU的简记式)之间的关系。由于我们是从低到高输出比特流的,将0x1021左右反转就得到0x8408。将生成多项式写成
G(x)=1+x5+x12+x16,是不是更好看一点? <BR><BR>下面是一个典型的PPP帧。最后两个字节称为FCS(Frame
Check Sequence),是前面11个字节的CRC。 <BR><BR>FF 03 C0 21 04 03 00 07 0D 03
06 D0 3A <BR>我们来计算这个PPP帧的CRC,并验证它。 <BR><BR>byte ppp[13] = {0xFF,
0x03, 0xC0, 0x21, 0x04, 0x03, 0x00, 0x07, 0x0D, 0x03, 0x06, 0x00,
0x00}; <BR>int i,j; <BR>u16 result; <BR><BR>/////////// 以下计算FCS
<BR><BR>// 初始化 <BR>crcInitRegisters(); <BR><BR>//
逐位输入,每个字节低位在先,不包括两个FCS字节 <BR>for(i = 0; i <
评论0