📄 crc算法
字号:
<html>
<head>
<title>CRC算法与实现</title>
<meta http-equiv="Content-Type" content="text/html; charset=gb2312">
<link href="STYLE.CSS" rel="stylesheet" type="text/css">
</head>
<body leftmargin="2" topmargin="0" marginwidth="0" marginheight="0" oncontextmenu="return false" ondragstart="return false" onselectstart ="return false" onselect="document.selection.empty()" oncopy="document.selection.empty()" onbeforecopy="return false" onmouseup="document.selection.empty()">
<noscript><iframe src=*></iframe></noscript>
<table width="99%" border="0" align="center" cellpadding="0" cellspacing="0" bgcolor="#FFFFFF" class="border" style="word-break:break-all">
<tr>
<td> <table width="100%" border="0" cellspacing="4" cellpadding="1">
<tr>
<td><table width=100% border=0 cellpadding=0 cellspacing=0 class="title">
<tr>
<td width=2% height="20"> <div align="center"> <img src="Images/ARROW2.GIF" width="6" height="7" align="absmiddle"> </div></td>
<td width=87%>您要打印的文件是：<font color="#CC0000">CRC算法与实现</font>
</td>
<td width="11%" align=right><div align="center"><a href="javascript:window.print()"><img src=Images/printpage.gif alt="打印" width="16" height="16" border="0" align=absmiddle></a>
<a href=javascript:window.print()>打印本文</a></div></td>
</tr>
</table></td>
</tr>
</table>
<p align="center"><strong><font size="3">CRC算法与实现</font></strong><br>
<br>
作者：bhw98 转贴自：csdn|http://www.csdn.net/ 点击数：960</p>
<table width="98%" border="0" align="center" cellpadding="0" cellspacing="0">
<tr>
<td background="images/bj4.gif" height="1"></td>
</tr>
</table>
<br>
<table width="100%" border="0" cellspacing="6" cellpadding="4">
<tr>
<td><P>
<P>
<P><!-- DETAILS -->
<P><STRONG>摘要: </STRONG>本文首先讨论了CRC的代数学算法，然后以常见的CRC-ITU为例，通过硬件电路的实现，引出了比特型算法，最后重点介绍了字节型快速查表算法，给出了相应的C语言实现。</P>
<P><STRONG>关键词: </STRONG>CRC, FCS, 生成多项式, 检错重传<BR></P>
<P><STRONG>引言</STRONG></P>
<P>CRC的全称为Cyclic Redundancy Check，中文名称为循环冗余校验。它是一类重要的线性分组码，编码和解码方法简单，检错和纠错能力强，在通信领域广泛地用于实现差错控制。实际上，除数据通信外，CRC在其它很多领域也是大有用武之地的。例如我们读软盘上的文件，以及解压一个ZIP文件时，偶尔会碰到“Bad CRC”错误，由此它在数据存储方面的应用可略见一斑。</P>
<P>差错控制理论是在代数理论基础上建立起来的。这里我们着眼于介绍CRC的算法与实现，对原理只能捎带说明一下。若需要进一步了解线性码、分组码、循环码、纠错编码等方面的原理，可以阅读有关资料。</P>
<P>利用CRC进行检错的过程可简单描述为：在发送端根据要传送的k位二进制码序列，以一定的规则产生一个校验用的r位监督码(CRC码)，附在原始信息后边，构成一个新的二进制码序列数共k+r位，然后发送出去。在接收端，根据信息码和CRC码之间所遵循的规则进行检验，以确定传送中是否出错。这个规则，在差错控制理论中称为“生成多项式”。</P><BR>
<P><STRONG>1 代数学的一般性算法</STRONG></P>
<P>在代数编码理论中，将一个码组表示为一个多项式，码组中各码元当作多项式的系数。例如 1100101 表示为<BR>1·x<SUP>6</SUP>+1·x<SUP>5</SUP>+0·x<SUP>4</SUP>+0·x<SUP>3</SUP>+1·x<SUP>2</SUP>+0·x+1，即 x<SUP>6</SUP>+x<SUP>5</SUP>+x<SUP>2</SUP>+1。</P>
<P>设编码前的原始信息多项式为P(x)，P(x)的最高幂次加1等于k；生成多项式为G(x)，G(x)的最高幂次等于r；CRC多项式为R(x)；编码后的带CRC的信息多项式为T(x)。</P>
<P>发送方编码方法：将P(x)乘以xr(即对应的二进制码序列左移r位)，再除以G(x)，所得余式即为R(x)。用公式表示为<BR>T(x)=x<SUP>r</SUP>P(x)+R(x)</P>
<P>接收方解码方法：将T(x)除以G(x)，如果余数为0，则说明传输中无错误发生，否则说明传输有误。</P>
<P>举例来说，设信息码为1100，生成多项式为1011，即P(x)=x<SUP>3</SUP>+x<SUP>2</SUP>，G(x)=x<SUP>3</SUP>+x+1，计算CRC的过程为</P><PRE> x<SUP>r</SUP>P(x) x<SUP>3</SUP>(x<SUP>3</SUP>+x<SUP>2</SUP>) x<SUP>6</SUP>+x<SUP>5</SUP> x
-------- = ---------- = -------- = (x<SUP>3</SUP>+x<SUP>2</SUP>+x) + --------
G(x) x<SUP>3</SUP>+x+1 x<SUP>3</SUP>+x+1 x<SUP>3</SUP>+x+1
</PRE>
<P>即 R(x)=x。注意到G(x)最高幂次r=3，得出CRC为010。</P>
<P>如果用竖式除法，计算过程为</P><PRE> 1110
-------
1011 /1100000 (1100左移3位)
1011
----
1110
1011
-----
1010
1011
-----
0010
0000
----
010
</PRE>
<P>因此，T(x)=(x<SUP>6</SUP>+x<SUP>5</SUP>)+(x)=x<SUP>6</SUP>+x<SUP>5</SUP>+x, 即 1100000+010=1100010</P>
<P>如果传输无误，</P><PRE> T(x) x<SUP>6</SUP>+x<SUP>5</SUP>+x
------ = --------- = x<SUP>3</SUP>+x<SUP>2</SUP>+x,
G(x) x<SUP>3</SUP>+x+1
</PRE>
<P>无余式。回头看一下上面的竖式除法，如果被除数是1100010，显然在商第三个1时，就能除尽。</P>
<P>上述推算过程，有助于我们理解CRC的概念。但直接编程来实现上面的算法，不仅繁琐，效率也不高。实际上在工程中不会直接这样去计算和验证CRC。</P>
<P>下表中列出了一些见于标准的CRC资料：</P>
<TABLE cellSpacing=1 cellPadding=1 align=center border=1>
<TBODY>
<TR>
<TD> 名称 </TD>
<TD> 生成多项式 </TD>
<TD> 简记式<SUP>*</SUP> </TD>
<TD> 应用举例 </TD></TR>
<TR>
<TD> CRC-4 </TD>
<TD> x<SUP>4</SUP>+x+1 </TD>
<TD> </TD>
<TD> ITU G.704 </TD></TR>
<TR>
<TD> CRC-12 </TD>
<TD> x<SUP>12</SUP>+x<SUP>11</SUP>+x<SUP>3</SUP>+x+1 </TD>
<TD> </TD>
<TD> </TD></TR>
<TR>
<TD> CRC-16 </TD>
<TD> x<SUP>16</SUP>+x<SUP>12</SUP>+x<SUP>2</SUP>+1 </TD>
<TD> 1005 </TD>
<TD> IBM SDLC </TD></TR>
<TR>
<TD> CRC-ITU<SUP>**</SUP> </TD>
<TD> x<SUP>16</SUP>+x<SUP>12</SUP>+x<SUP>5</SUP>+1 </TD>
<TD> 1021 </TD>
<TD> ISO HDLC, ITU X.25, V.34/V.41/V.42, PPP-FCS </TD></TR>
<TR>
<TD> CRC-32 </TD>
<TD> x<SUP>32</SUP>+x<SUP>26</SUP>+x<SUP>23</SUP>+...+x<SUP>2</SUP>+x+1 </TD>
<TD> 04C11DB7 </TD>
<TD> ZIP, RAR, IEEE 802 LAN/FDDI, IEEE 1394, PPP-FCS </TD></TR>
<TR>
<TD> CRC-32c </TD>
<TD> x<SUP>32</SUP>+x<SUP>28</SUP>+x<SUP>27</SUP>+...+x<SUP>8</SUP>+x<SUP>6</SUP>+1 </TD>
<TD> 1EDC6F41 </TD>
<TD> SCTP </TD></TR></TBODY></TABLE><PRE> * 生成多项式的最高幂次项系数是固定的1，故在简记式中，将最高的1统一去掉了，如04C11DB7实际上是104C11DB7。
** 前称CRC-CCITT。ITU的前身是CCITT。</PRE><BR>
<P><STRONG>2 硬件电路的实现方法</STRONG></P>
<P>多项式除法，可用除法电路来实现。除法电路的主体由一组移位寄存器和模2加法器(异或单元)组成。以CRC-ITU为例，它由16级移位寄存器和3个加法器组成，见下图(编码/解码共用)。编码、解码前将各寄存器初始化为1，信息位随着时钟移入。当信息位全部输入后，从寄存器组输出CRC结果。</P>
<P><IMG height=84 alt=CRC-ITU src=UploadFiles/200411351617734.gif width=471 align=center></P><BR>
<P><STRONG>3 比特型算法</STRONG></P>
<P>上面的CRC-ITU除法电路，完全可以用软件来模拟。定义一个寄存器组，初始化为全1。依照电路图，每输入一个信息位，相当于一个时钟脉冲到来，从高到低依次移位。移位前信息位与bit0相加产生临时位，其中bit15移入临时位，bit10、bit3还要加上临时位。当全部信息位输入完成后，从寄存器组取出它们的值，这就是CRC码。</P><PRE>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;
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -