if (off < 0 || len < 0 || off + len > buf.Length) { throw new ArgumentOutOfRangeException(); } for (int i = off; i < len ; i ++) { Crc(buf[i]); } } } }
if (off < 0 || len < 0 || off + len > buf.Length) { throw new ArgumentOutOfRangeException(); } for (int i = off; i < len ; i ++) { Crc(buf[i]); } } } }
word 版的，先贴给你。
循环冗余校验 CRC的算法分析和程序实现
西南交通大学计算机与通信工程学院 刘东
摘要 通信的目的是要把信息及时可靠地传送给对方，因此要求一个通信系统传输消息必须可靠与快速，在数字通信系统中可靠与快速往往是一对矛盾。为了解决可靠性，通信系统都采用了差错控制。本文详细介绍了循环冗余校验CRC（Cyclic Redundancy Check）的差错控制原理及其算法实现。关键字 通信 循环冗余校验 CRC-32 CRC-16 CRC-4 概述
在数字通信系统中可靠与快速往往是一对矛盾。若要求快速，则必然使得每个数据码元所占地时间缩短、波形变窄、能量减少，从而在受到干扰后产生错误地可能性增加，传送信息地可靠性下降。若是要求可靠，则使得传送消息地速率变慢。因此，如何合理地解决可靠性也速度这一对矛盾，是正确设计一个通信系统地关键问题之一。为保证传输过程的正确性，需要对通信过程进行差错控制。差错控制最常用的方法是自动请求重发方式（ARQ）、向前纠错方式（FEC）和混合纠错（HEC）。在传输过程误码率比较低时，用FEC方式比较理想。在传输过程误码率较高时，采用FEC容易出现“乱纠”现象。HEC方式则式ARQ和FEC的结合。在许多数字通信中，广泛采用ARQ方式，此时的差错控制只需要检错功能。实现检错功能的差错控制方法很多，传统的有：奇偶校验、校验和检测、重复码校验、恒比码校验、行列冗余码校验等，这些方法都是增加数据的冗余量，将校验码和数据一起发送到接受端。接受端对接受到的数据进行相同校验，再将得到的校验码和接受到的校验码比较，如果二者一致则认为传输正确。但这些方法都有各自的缺点，误判的概率比较高。
循环冗余校验CRC（Cyclic Redundancy Check）是由分组线性码的分支而来，其主要应用是二元码组。编码简单且误判概率很低，在通信系统中得到了广泛的应用。下面重点介绍了CRC校验的原理及其 算法实现。一、循环冗余校验码（CRC）
CRC校验采用多项式编码方法。被处理的数据块可以看作是一个n阶的二进制多项式，由 。如一个8位二进制数10110101可以表示为： 。多项式乘除法运算过程与普通代数多项式的乘除法相同。多项式的加减法运算以2为模，加减时不进，错位，和逻辑异或运算一致。
采用CRC校验时，发送方和接收方用同一个生成多项式g（x）,并且g（x）的首位和最后一位的系数必须为1。CRC的处理方法是：发送方以g（x）去除t（x），得到余数作为CRC校验码。校验时，以计算的校正结果是否为0为据，判断数据帧是否出错。
CRC校验可以100％地检测出所有奇数个随机错误和长度小于等于k（k为g（x）的阶数）的突发错误。所以CRC的生成多项式的阶数越高，那么误判的概率就越小。CCITT建议：2048 kbit/s的PCM基群设备采用CRC-4方案，使用的CRC校验码生成多项式g（x）= 。采用16位CRC校验，可以保证在 bit码元中只含有一位未被检测出的错误 。在IBM的同步数据链路控制规程SDLC的帧校验序列FCS中，使用CRC-16，其生成多项式g（x）= ；而在CCITT推荐的高级数据链路控制规程HDLC的帧校验序列FCS中，使用CCITT-16，其生成多项式g（x）= 。CRC-32的生成多项式g（x）= 。CRC-32出错的概率比CRC-16低 倍 。由于CRC-32的可靠性，把CRC-32用于重要数据传输十分合适，所以在通信、计算机等领域运用十分广泛。在一些UART通信控制芯片（如MC6582、Intel8273和Z80-SIO）内，都采用了CRC校验码进行差错控制；以太网卡芯片、MPEG解码芯片中，也采用CRC-32进行差错控制。
CRC校验码的编码方法是用待发送的二进制数据t（x）除以生成多项式g（x），将最后的余数作为CRC校验码。其实现步骤如下：
（1） 设待发送的数据块是m位的二进制多项式t（x），生成多项式为r阶的g（x）。在数据块的末尾添加r个0，数据块的长度增加到m+r位，对应的二进制多项式为 。
（2） 用生成多项式g（x）去除 ，求得余数为阶数为r-1的二进制多项式y（x）。此二进制多项式y（x）就是t（x）经过生成多项式g（x）编码的CRC校验码。
（3） 用 以模2的方式减去y（x），得到二进制多项式 。 就是包含了CRC校验码的待发送字符串。
从CRC的编码规则可以看出，CRC编码实际上是将代发送的m位二进制多项式t（x）转换成了可以被g（x）除尽的m+r位二进制多项式 ，所以解码时可以用接受到的数据去除g（x），如果余数位零，则表示传输过程没有错误；如果余数不为零，则在传输过程中肯定存在错误。许多CRC的硬件解码电路就是按这种方式进行检错的。同时 可以看做是由t（x）和CRC校验码的组合，所以解码时将接收到的二进制数据去掉尾部的r位数据，得到的就是原始数据。
为了更清楚的了解CRC校验码的编码过程，下面用一个简单的例子来说明CRC校验码的编码过程。由于CRC-32、CRC-16、CCITT和CRC-4的编码过程基本一致，只有位数和生成多项式不一样。为了叙述简单，用一个CRC-4编码的例子来说明CRC的编码过程。
设待发送的数据t（x）为12位的二进制数据100100011100；CRC-4的生成多项式为g（x）= ，阶数r为4，即10011。首先在t（x）的末尾添加4个0构成 ，数据块就成了1001000111000000。然后用g（x）去除 ，不用管商是多少，只需要求得余数y（x）。下表为给出了除法过程。
除数次数 被除数/ g（x）/结果 余数
0 1 001000111000000 100111000000
1 0011
0 000100111000000
1 1 00111000000 1000000
1 0011
0 00001000000
2 1 000000 1100
1 0011
0 001100 从上面表中可以看出，CRC编码实际上是一个循环移位的模2运算。对CRC-4，我们假设有一个5 bits的寄存器，通过反复的移位和进行CRC的除法，那么最终该寄存器中的值去掉最高一位就是我们所要求的余数。所以可以将上述步骤用下面的流程描述：
//reg是一个5 bits的寄存器
把reg中的值置0.
把原始的数据后添加r个0.
While (数据未处理完)
Begin
If (reg首位是1)
reg = reg XOR 0011.
把reg中的值左移一位，读入一个新的数据并置于register的0 bit的位置。
End
reg的后四位就是我们所要求的余数。
这种算法简单，容易实现，对任意长度生成多项式的G（x）都适用。在发送的数据不长的情况下可以使用。但是如果发送的数据块很长的话，这种方法就不太适合了。它一次只能处理一位数据，效率太低。为了提高处理效率，可以一次处理4位、8位、16位、32位。由于处理器的结构基本上都支持8位数据的处理，所以一次处理8位比较合适。
为了对优化后的算法有一种直观的了解，先将上面的算法换个角度理解一下。在上面例子中，可以将编码过程看作如下过程：
由于最后只需要余数，所以我们只看后四位。构造一个四位的寄存器reg，初值为0，数据依次移入reg0（reg的0位），同时reg3的数据移出reg。有上面的算法可以知道，只有当移出的数据为1时，reg才和g（x）进行XOR运算；移出的数据为0时，reg不与g（x）进行XOR运算，相当与和0000进行XOR运算。就是说，reg和什么样的数据进行XOR移出的数据决定。由于只有一个bit，所以有 种选择。上述算法可以描述如下，
//reg是一个4 bits的寄存器
初始化t[]={0011,0000}
把reg中的值置0.
把原始的数据后添加r个0.
While (数据未处理完)
Begin
把reg中的值左移一位，读入一个新的数据并置于register的0 bit的位置。
reg = reg XOR t[移出的位]
End
上面算法是以bit为单位进行处理的，可以将上述算法扩展到8位，即以Byte为单位进行处理，即CRC-32。构造一个四个Byte的寄存器reg，初值为0x00000000，数据依次移入reg0（reg的0字节，以下类似），同时reg3的数据移出reg。用上面的算法类推可知，移出的数据字节决定reg和什么样的数据进行XOR。由于有8个bit，所以有 种选择。上述算法可以描述如下：
//reg是一个4 Byte的寄存器
初始化t[]＝{…}//共有 ＝256项
把reg中的值置0.
把原始的数据后添加r/8个0字节.
While (数据未处理完)
Begin
把reg中的值左移一个字节，读入一个新的字节并置于reg的第0个byte的位置。
reg = reg XOR t[移出的字节]
End
算法的依据和多项式除法性质有关。如果一个m位的多项式t（x）除以一个r阶的生成多项式g（x）， ，将每一位 （0=<k<m）提出来，在后面不足r个0后，单独去除g（x），得到的余式位 。则将 后得到的就是t（x）由生成多项式g（x）得到的余式。对于CRC-32，可以将每个字节在后面补上32个0后与生成多项式进行运算，得到余式和此字节唯一对应，这个余式就是上面算法种t[]中的值，由于一个字节有8位，所以t[]共有 ＝256项。多项式运算性质可以参见参考文献[1]。这种算法每次处理一个字节，通过查表法进行运算，大大提高了处理速度，故为大多数应用所采用。三、CRC-32的程序实现。
为了提高编码效率，在实际运用中大多采用查表法来完成CRC-32校验，下面是产生CRC-32校验吗的子程序。
unsigned long crc_32_tab[256]={
0x00000000, 0x77073096, 0xee0e612c, 0x990951ba, 0x076dc419, 0x706af48f, 0xe963a535, 0x9e6495a3,0x0edb8832,…, 0x5a05df1b, 0x2d02ef8d
};//事先计算出的参数表，共有256项，未全部列出。unsigned long GenerateCRC32(char xdata * DataBuf,unsigned long len)
{
unsigned long oldcrc32;
unsigned long crc32;
unsigned long oldcrc;
unsigned int charcnt;
char c,t;
oldcrc32 = 0x00000000; //初值为0
charcnt=0;
while (len--) {
t= (oldcrc32 >> 24) & 0xFF; //要移出的字节的值
oldcrc=crc_32_tab[t]; //根据移出的字节的值查表
c=DataBuf[charcnt]; //新移进来的字节值
oldcrc32= (oldcrc32 << 8) | c; //将新移进来的字节值添在寄存器末字节中
oldcrc32=oldcrc32^oldcrc; //将寄存器与查出的值进行xor运算
charcnt++;
}
crc32=oldcrc32;
return crc32;
}
参数表可以先在PC机上算出来，也可在程序初始化时完成。下面是用于计算参数表的c语言子程序，在Visual C++ 6.0下编译通过。
#include <stdio.h>
unsigned long int crc32_table[256];
unsigned long int ulPolynomial = 0x04c11db7;
unsigned long int Reflect(unsigned long int ref, char ch)
{ unsigned long int value(0);
// 交换bit0和bit7，bit1和bit6，类推
for(int i = 1; i < (ch + 1); i++)
{ if(ref & 1)
value |= 1 << (ch - i);
ref >>= 1; }
return value;
}
init_crc32_table()
{ unsigned long int crc,temp;
// 256个值
for(int i = 0; i <= 0xFF; i++)
{ temp=Reflect(i, 8);
crc32_table[i]= temp<< 24;
for (int j = 0; j < 8; j++){
unsigned long int t1,t2;
unsigned long int flag=crc32_table[i]&0x80000000;
t1=(crc32_table[i] << 1);
if(flag==0)
t2=0;
else
t2=ulPolynomial;
crc32_table[i] =t1^t2 ; }
crc=crc32_table[i];
crc32_table[i] = Reflect(crc32_table[i], 32);
}
}
结束语
CRC校验由于实现简单，检错能力强，被广泛使用在各种数据校验应用中。占用系统资源少，用软硬件均能实现，是进行数据传输差错检测地一种很好的手段。
{
/// <summary>
/// CRC8 的摘要说明。
/// </summary>
public class CRC8:ICRC
{
#region CRC 8 位校验表 /// <summary>
/// CRC 8 位校验表
/// </summary>
public byte[] CRC8_Table = new byte[]
{
0,94,188,226,97,63,221,131,194,156,126,32,163,253,31,65,
157,195,33,127,252,162,64,30, 95,1,227,189,62,96,130,220,
35,125,159,193,66,28,254,160,225,191,93,3,128,222,60,98,
190,224,2,92,223,129,99,61,124,34,192,158,29,67,161,255,
70,24,250,164,39,121,155,197,132,218,56,102,229,187,89,7,
219,133,103,57,186,228,6,88,25,71,165,251,120,38,196,154,
101,59,217,135,4,90,184,230,167,249,27,69,198,152,122,36,
248,166,68,26,153,199,37,123,58,100,134,216,91,5,231,185,
140,210,48,110,237,179,81,15,78,16,242,172,47,113,147,205,
17,79,173,243,112,46,204,146,211,141,111,49,178,236,14,80,
175,241,19,77,206,144,114,44,109,51,209,143,12,82,176,238,
50,108,142,208,83,13,239,177,240,174,76,18,145,207,45,115,
202,148,118,40,171,245,23,73,8,86,180,234,105,55,213,139,
87,9,235,181,54,104,138,212,149,203, 41,119,244,170,72,22,
233,183,85,11,136,214,52,106,43,117,151,201,74,20,246,168,
116,42,200,150,21,75,169,247,182,232,10,84,215,137,107,53
};
#endregion uint crc = 0;
/// <summary>
///返回 CRC8校验结果;
/// </summary>
public long Value
{
get
{
return crc;
}
set
{
crc = (uint)value;
}
}
/// <summary>
/// CRC校验前设置校验值
/// </summary>
public void Reset()
{
crc = 0;
} /// <summary>
/// 8 位 CRC 校验 产生校验码 需要被校验码和校验码
/// </summary>
/// <param name="CRC"></param>
/// <param name="OldCRC"> 初始为 0 ,以后为 返回值 ret </param>
/// <returns> 产生校验码时 ret 为校验码</returns>
public void Crc(byte CRC,byte OldCRC)
{
crc = CRC8_Table[OldCRC ^ CRC];
} /// <summary>
/// 8 位 CRC 校验 产生校验码 只要被校验码
/// </summary>
/// <param name="bval"></param>
public void Crc(int bval)
{
crc = CRC8_Table[crc ^ bval];
} /// <summary>
/// 8 位 CRC 校验 产生校验码 只要被校验的字节数组
/// </summary>
/// <param name="buffer"></param>
public void Crc(byte[] buffer)
{ Crc(buffer,0,buffer.Length);
} /// <summary>
/// 8 位 CRC 校验 产生校验码 要被校验的字节数组、起始结果位置和字节长度
/// </summary>
/// <param name="buf"></param>
/// <param name="off"></param>
/// <param name="len"></param>
public void Crc(byte[] buf,int off ,int len)
{
if (buf == null)
{
throw new ArgumentNullException("buf");
}
if (off < 0 || len < 0 || off + len > buf.Length)
{
throw new ArgumentOutOfRangeException();
}
for (int i = off; i < len ; i ++)
{
Crc(buf[i]);
}
}
}
}
{
/// <summary>
/// CRC8 的摘要说明。
/// </summary>
public class CRC8:ICRC
{
#region CRC 8 位校验表 /// <summary>
/// CRC 8 位校验表
/// </summary>
public byte[] CRC8_Table = new byte[]
{
0,94,188,226,97,63,221,131,194,156,126,32,163,253,31,65,
157,195,33,127,252,162,64,30, 95,1,227,189,62,96,130,220,
35,125,159,193,66,28,254,160,225,191,93,3,128,222,60,98,
190,224,2,92,223,129,99,61,124,34,192,158,29,67,161,255,
70,24,250,164,39,121,155,197,132,218,56,102,229,187,89,7,
219,133,103,57,186,228,6,88,25,71,165,251,120,38,196,154,
101,59,217,135,4,90,184,230,167,249,27,69,198,152,122,36,
248,166,68,26,153,199,37,123,58,100,134,216,91,5,231,185,
140,210,48,110,237,179,81,15,78,16,242,172,47,113,147,205,
17,79,173,243,112,46,204,146,211,141,111,49,178,236,14,80,
175,241,19,77,206,144,114,44,109,51,209,143,12,82,176,238,
50,108,142,208,83,13,239,177,240,174,76,18,145,207,45,115,
202,148,118,40,171,245,23,73,8,86,180,234,105,55,213,139,
87,9,235,181,54,104,138,212,149,203, 41,119,244,170,72,22,
233,183,85,11,136,214,52,106,43,117,151,201,74,20,246,168,
116,42,200,150,21,75,169,247,182,232,10,84,215,137,107,53
};
#endregion uint crc = 0;
/// <summary>
///返回 CRC8校验结果;
/// </summary>
public long Value
{
get
{
return crc;
}
set
{
crc = (uint)value;
}
}
/// <summary>
/// CRC校验前设置校验值
/// </summary>
public void Reset()
{
crc = 0;
} /// <summary>
/// 8 位 CRC 校验 产生校验码 需要被校验码和校验码
/// </summary>
/// <param name="CRC"></param>
/// <param name="OldCRC"> 初始为 0 ,以后为 返回值 ret </param>
/// <returns> 产生校验码时 ret 为校验码</returns>
public void Crc(byte CRC,byte OldCRC)
{
crc = CRC8_Table[OldCRC ^ CRC];
} /// <summary>
/// 8 位 CRC 校验 产生校验码 只要被校验码
/// </summary>
/// <param name="bval"></param>
public void Crc(int bval)
{
crc = CRC8_Table[crc ^ bval];
} /// <summary>
/// 8 位 CRC 校验 产生校验码 只要被校验的字节数组
/// </summary>
/// <param name="buffer"></param>
public void Crc(byte[] buffer)
{ Crc(buffer,0,buffer.Length);
} /// <summary>
/// 8 位 CRC 校验 产生校验码 要被校验的字节数组、起始结果位置和字节长度
/// </summary>
/// <param name="buf"></param>
/// <param name="off"></param>
/// <param name="len"></param>
public void Crc(byte[] buf,int off ,int len)
{
if (buf == null)
{
throw new ArgumentNullException("buf");
}
if (off < 0 || len < 0 || off + len > buf.Length)
{
throw new ArgumentOutOfRangeException();
}
for (int i = off; i < len ; i ++)
{
Crc(buf[i]);
}
}
}
}
问题解决，结帖！！谢谢 huangguangdou(人生最遗憾的，莫过于，轻易的放弃了不该放弃的)
zhangci226(三只熊熊)
谢谢了先！