CRC校验算法
这两天做项目，需要用到 CRC 校验。以前没搞过这东东，以为挺简单的。结果看看别人提供的汇编源程序，居然看不懂。花了两天时间研究了一下 CRC 校验，希望我写的这点东西能够帮助和我有同样困惑的朋友节省点时间。
先是在网上下了一堆乱七八遭的资料下来，感觉都是一个模样，全都是从CRC 的数学原理开始，一长串的表达式看的我头晕。第一次接触还真难以理解。这些东西不想在这里讲，随便找一下都是一大把。我想根据源代码来分析会比较好懂一些。
费了老大功夫，才搞清楚 CRC 根据”权”(即多项表达式)的不同而相应的源代码也有稍许不同。以下是各种常用的权。
CRC8=X8+X5+X4+1
CRC-CCITT=X16+X12+X5+1
CRC16=X16+X15+X5+1
CRC12=X12+X11+X3+X2+1
CRC32=X32+X26+X23+X22+X16+X12+X11+X10+X8+X7+X5+X4+X2+X1+1
以下的源程序全部以 CCITT 为例。其实本质都是一样，搞明白一种，其他的都是小菜。
图 1，图 2 说明了 CRC 校验中 CRC 值是如何计算出来的，体现的多项式正是 X16+X12+X5+1。 Serial Data 即是需要校验的数据。从把数据移位开始计算，将数据位（从最低的数据位开始）逐位移入反向耦合移位寄存器(这个名词我也不懂，觉得蛮酷的，就这样写了，嘿)。当所有数据位都这样操作后，计算结束。此时，16 位移位寄存器中的内容就是 CRC 码。
图中进行 XOR 运算的位与多项式的表达相对应。
X5 代表 Bit5，X12 代表 Bit12，1 自然是代表 Bit0，X16 比较特别，是指移位寄存器移出的数据，即图中的DATA OUT。可以这样理解，与数据位做XOR 运算的是上次 CRC值的 Bit15。
根据以上说明，可以依葫芦画瓢的写出以下程序。(程序都是在 keil C 7.10 下调试的)
typedef unsigned char uchar;
typedef unsigned int uint;
code uchar crcbuff [] = { 0x00,0x00,0x00,0x00,0x06,0x0d,0xd2,0xe3};
uint crc; // CRC 码
void main(void)
{
uchar *ptr;
crc = 0; // CRC 初值
ptr = crcbuff; // 指向第一个 Byte 数据
crc = crc16l(ptr,8);
while(1);
}
uint crc16l(uchar *ptr,uchar len) // ptr 为数据指针，len 为数据长度
{
uchar i;
while(len--)
{
for(i=0x80; i!=0; i>>=1)
{
if((crc&0x8000)!=0) {crc<<=1; crc^=0x1021;} 1-1
else crc<<=1; 1-2
if((*ptr&i)!=0) crc^=0x1021; 1-3
}
ptr++;
}
return(crc);
}
执行结果 crc = 0xdbc0;
程序 1-1,1-2,1-3 可以理解成移位前 crc 的 Bit15 与数据对应的
Bit(*ptr&i)做 XOR运算，根据此结果来决定是否执行 crc^=0x1021。只要明白两次异或运算与原值相同，就不难理解这个程序。
很多资料上都写了查表法来计算，当时是怎么也没想通。其实蛮简单的。假设通过移位处理了 8 个 bit 的数据，相当于把之前的 CRC 码的高字节(8bit)全部移出，与一个 byte 的数据做XOR 运算，根据运算结果来选择一个值(称为余式)，与原来的 CRC 码再做一次 XOR 运算，就可以得到新的 CRC 码。
不难看出，余式有 256 种可能的值，实际上就是 0~255 以 X16+X12+X5+1 为权得到的 CRC码，可以通过函数 crc16l来计算。以1 为例。
code test[]={0x01};
crc = 0;
ptr = test;
crc = crc16l(ptr,1);
执行结果 crc = 1021，这就是1 对应的余式。
进一步修改函数，我这里就懒得写了，可得到 X16+X12+X5+1 的余式表。
code uint crc_ta[256]={ // X16+X12+X5+1 余式表
0x0000, 0x1021, 0x2042, 0x3063, 0x4084, 0x50a5, 0x60c6, 0x70e7,
0x8108, 0x9129, 0xa14a, 0xb16b, 0xc18c, 0xd1ad, 0xe1ce, 0xf1ef,
0x1231, 0x0210, 0x3273, 0x2252, 0x52b5, 0x4294, 0x72f7, 0x62d6,
0x9339, 0x8318, 0xb37b, 0xa35a, 0xd3bd, 0xc39c, 0xf3ff, 0xe3de,
0x2462, 0x3443, 0x0420, 0x1401, 0x64e6, 0x74c7, 0x44a4, 0x5485,
0xa56a, 0xb54b, 0x8528, 0x9509, 0xe5ee, 0xf5cf, 0xc5ac, 0xd58d,
0x3653, 0x2672, 0x1611, 0x0630, 0x76d7, 0x66f6, 0x5695, 0x46b4,
0xb75b, 0xa77a, 0x9719, 0x8738, 0xf7df, 0xe7fe, 0xd79d, 0xc7bc,
0x48c4, 0x58e5, 0x6886, 0x78a7, 0x0840, 0x1861, 0x2802, 0x3823,
0xc9cc, 0xd9ed, 0xe98e, 0xf9af, 0x8948, 0x9969, 0xa90a, 0xb92b,
0x5af5, 0x4ad4, 0x7ab7, 0x6a96, 0x1a71, 0x0a50, 0x3a33, 0x2a12, 0xdbfd, 0xcbdc, 0xfbbf, 0xeb9e, 0x9b79, 0x8b58, 0xbb3b, 0xab1a, 0x6ca6, 0x7c87, 0x4ce4, 0x5cc5, 0x2c22, 0x3c03, 0x0c60, 0x1c41, 0xedae, 0xfd8f, 0xcdec, 0xddcd, 0xad2a, 0xbd0b, 0x8d68, 0x9d49, 0x7e97, 0x6eb6, 0x5ed5, 0x4ef4, 0x3e13, 0x2e32, 0x1e51, 0x0e70, 0xff9f, 0xefbe, 0xdfdd, 0xcffc, 0xbf1b, 0xaf3a, 0x9f59, 0x8f78, 0x9188, 0x81a9, 0xb1ca, 0xa1eb, 0xd10c, 0xc12d, 0xf14e, 0xe16f, 0x1080, 0x00a1, 0x30c2, 0x20e3, 0x5004, 0x4025, 0x7046, 0x6067, 0x83b9, 0x9398, 0xa3fb, 0xb3da, 0xc33d, 0xd31c, 0xe37f, 0xf35e, 0x02b1, 0x1290, 0x22f3, 0x32d2, 0x4235, 0x5214, 0x6277, 0x7256, 0xb5ea, 0xa5cb, 0x95a8, 0x8589, 0xf56e, 0xe54f, 0xd52c, 0xc50d, 0x34e2, 0x24c3, 0x14a0, 0x0481, 0x7466, 0x6447, 0x5424, 0x4405, 0xa7db, 0xb7fa, 0x8799, 0x97b8, 0xe75f, 0xf77e, 0xc71d, 0xd73c, 0x26d3, 0x36f2, 0x0691, 0x16b0, 0x6657, 0x7676, 0x4615, 0x5634, 0xd94c, 0xc96d, 0xf90e, 0xe92f, 0x99c8, 0x89e9, 0xb98a, 0xa9ab, 0x5844, 0x4865, 0x7806, 0x6827, 0x18c0, 0x08e1, 0x3882, 0x28a3, 0xcb7d, 0xdb5c, 0xeb3f, 0xfb1e, 0x8bf9, 0x9bd8, 0xabbb, 0xbb9a, 0x4a75, 0x5a54, 0x6a37, 0x7a16, 0x0af1, 0x1ad0, 0x2ab3, 0x3a92, 0xfd2e, 0xed0f, 0xdd6c, 0xcd4d, 0xbdaa, 0xad8b, 0x9de8, 0x8dc9, 0x7c26, 0x6c07, 0x5c64, 0x4c45, 0x3ca2, 0x2c83, 0x1ce0, 0x0cc1, 0xef1f, 0xff3e, 0xcf5d, 0xdf7c, 0xaf9b, 0xbfba, 0x8fd9, 0x9ff8, 0x6e17, 0x7e36, 0x4e55, 0x5e74, 0x2e93, 0x3eb2, 0x0ed1, 0x1ef0 };
根据这个思路，可以写出以下程序：
uint table_crc(uchar *ptr,uchar len) // 字节查表法求 CRC
{
uchar da;
while(len--!=0)
{
da=(uchar) (crc/256); // 以 8 位二进制数暂存 CRC 的高 8 位
crc<<=8; // 左移 8 位
crc^=crc_ta[da^*ptr]; // 高字节和当前数据 XOR 再查表
ptr++;
}
return(crc);
}
本质上 CRC 计算的就是移位和异或。所以一次处理移动几位都没有关系，只要做相应的处理就好了。
下面给出半字节查表的处理程序。其实和全字节是一回事。
code uint crc_ba[16]={
0x0000, 0x1021, 0x2042, 0x3063, 0x4084, 0x50a5, 0x60c6, 0x70e7,
0x8108, 0x9129, 0xa14a, 0xb16b, 0xc18c, 0xd1ad, 0xe1ce, 0xf1ef,
};
uint ban_crc(uchar *ptr,uchar len)
{
uchar da;
while(len--!=0)
{
da = ((uchar)(crc/256))/16;
crc <<= 4;
crc ^=crc_ba[da^(*ptr/16)];
da = ((uchar)(crc/256)/16);
crc <<= 4;
crc ^=crc_ba[da^(*ptr&0x0f)];
ptr++;
}
return(crc);
}
crc_ba[16]和crc_ta[256]的前 16 个余式是一样的。
其实讲到这里，就已经差不多了。反正当时我以为自己是懂了。结果去看别人的源代码的时候，也是说采用 CCITT，但是是反相的。如图 3
反过来，一切都那么陌生，faint.吐血，吐血。
仔细分析一下，也可以很容易写出按位异或的程序。只不过由左移变成右移。
uint crc16r(unsigned char *ptr, unsigned char len)
{
unsigned char i;
while(len--!=0)
{
for(i=0x01;i!=0;i <<= 1)
{
if((crc&0x0001)!=0) {crc >>= 1; crc ^= 0x8408;}
else crc >>= 1;
if((*ptr&i)!=0) crc ^= 0x8408;
}
ptr++;
}
return(crc);
}
0x8408 就是 CCITT 的反转多项式。
套用别人资料上的话
“反转多项式是指在数据通讯时，信息字节先传送或接收低位字节，如重新排位影响 CRC计算速度，故设反转多项式。”
如
code uchar crcbuff [] = { 0x00,0x00,0x00,0x00,0x06,0x0d,0xd2,0xe3};
反过来就是
code uchar crcbuff_fan[] =
{0xe3,0xd2,0x0d,0x06,0x00,0x00,0x00,0x00};
crc = 0;
ptr = crcbuff_fan;
crc = crc16r(ptr,8);
执行结果 crc = 0x5f1d;
如想验证是否正确，可改
code uchar crcbuff_fan_result[] =
{0xe3,0xd2,0x0d,0x06,0x00,0x00,0x00,0x00,0x1d,0x5f};
ptr = crcbuff_fan_result;
crc = crc16r(ptr,10);
执行结果 crc = 0; 符合 CRC 校验的原理。
请注意 0x5f1d 在数组中的排列中低位在前，正是反相运算的特点。不过当时是把我搞的晕头转向。
在用半字节查表法进行反相运算要特别注意一点，因为是右移，所以 CRC 移出的 4Bit与数据 XOR 的操作是在 CRC 的高位端。因此余式表的产生是要以下列数组通过修改函数crc16r 产生。
code uchar ban_fan[]=
{0,0x10,0x20,0x30,0x40,0x50,0x60,0x70,0x80,0x90,0xa0,0xb0,0xc0,0x d0,0xe0,0xf0};
得出余式表
code uint fan_yushi[16]={
0x0000, 0x1081, 0x2102, 0x3183,
0x4204, 0x5285, 0x6306, 0x7387,
0x8408, 0x9489, 0xa50a, 0xb58b,
0xc60c, 0xd68d, 0xe70e, 0xf78f
};
uint ban_fan_crc(uchar *ptr,uchar len)
{
uchar da;
while(len--!=0)
{
da = (uchar)(crc&0x000f);
crc >>= 4;
crc ^= fan_yushi [da^(*ptr&0x0f)];
da = (uchar)(crc&0x000f);
crc >>= 4;
crc ^= fan_yushi [da^(*ptr/16)];
ptr++;
}
return(crc);
}
主程序中
crc = 0;
ptr = crcbuff_fan;
crc = ban_fan_crc(ptr,8);
执行结果 crc = 0x5f1d;
反相运算的全字节查表法就很容易了，懒的写了。
CRC校验码 CRC即循环冗余校验码（Cyclic Redundancy Check）：是数据通信领域中最常用的一种差错校验码，其特征是信息字段和校验字段的长度可以任意选定。 目录 详细介绍 代数学的一般性运算 详细介绍 循环冗余校验码（CRC）的基本原理是：在K位信息码后再拼接R位的校验码，整个编码长度为N位，因此，这种编码又叫（N，K）码。对于一个给定的（N，K）码，可以证明存在一个最高次幂为N-K=R的多项式G(x)。根据G(x)可以生成K位信息的校验码，而G(x)叫做这个CRC码的生成多项式。校验码的具体生成过程为：假设发送信息用信息多项式C(X)表示，将C(x)左移R位，则可表示成C(x)*2的R次方，这样C(x)的右边就会空出R位，这就是校验码的位置。通过C(x)*2的R次方除以生成多项式G(x)得到的余数就是校验码。 几个基本概念 1、多项式与二进制数码 多项式和二进制数有直接对应关系：x的最高幂次对应二进制数的最高位，以下各位对应多项式的各幂次，有此幂次项对应1，无此幂次项对应0。可以看出：x的最高幂次为R，转换成对应的二进制数有R+1位。 多项式包括生成多项式G(x)和信息多项式C(x)。 如生成多项式为G(x)=x4+x3+x+1，可转换为二进制数码11011。 而发送信息位1111，可转换为数据多项式为C(x)=x3+x2+x+1。 2、生成多项式 是接受方和发送方的一个约定，也就是一个二进制数，在整个传输过程中，这个数始终保持不变。 在发送方,利用生成多项式对信息多项式做模2除生成校验码。在接受方利用生成多项式对收到的编码多项式做模2除检测和确定错误位置。 应满足以下条件： a、生成多项式的最高位和最低位必须为1。 b、当被传送信息（CRC码）任何一位发生错误时，被生成多项式做除后应该使余数不为0。 c、不同位发生错误时，应该使余数不同。 d、对余数继续做除，应使余数循环。
实验三CRC校验 一、CRC校验码的基本原理 编码过程： 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 将y(x)的尾部加上校验码，得到二进制多项式。就是包含 了CRC校验码的待发送字符串。 解码过程： 从CRC的编码规则可以看出，CRC编码实际上是将代发送的m位 二进制多项式t(x)转换成了可以被g(x)除尽的m+r位二进制多项式 所以解码时可以用接收到的数据去除g（x），如果余数位零，则
表示传输过程没有错误；如果余数不为零，则在传输过程中肯定 存在错误。许多CRC的硬件解码电路就是按这种方式进行检错的。 同时,可以看做是由t（x）和CRC校验码的组合，所以解码时将接 收到的二进制数据去掉尾部的r位数据，得到的就是原始数据。 解码过程示例：
运行结果： 附录（实现代码）：using System; using ; namespace CRC
{ public abstract class Change { oString("x2").ToUpper(); } } return returnStr; } um; } (databuff);eight < max1) && (data[j].Parent == -1)) { max2 = max1; tmp2 = tmp1; tmp1 = j; max1 =
三种常用的CRC16校验算法的C51程序的优化2009-10-10 09:34:17| 分类：技术知识| 标签：|字号大 CRC校验又称为循环冗余校验，是数据通讯中常用的一种校验算法。它可以有效的判别出数据在传输过程中是否发生了错误，从而保障了传输的数据可靠性。 CRC校验有多种方式，如：CRC8、CRC16、CRC32等等。在实际使用中，我们经常使用CRC16校验。CRC16校验也有多种，如：1005多项式、1021多项式（CRC-ITU）等。在这里我们不讨论CRC算法是怎样产生的，而是重点落在几种算法的C51程序的优化上。 计算CRC校验时，最常用的计算方式有三种：查表、计算、查表＋计算。一般来说，查表法最快，但是需要较大的空间存放表格；计算法最慢，但是代码最简洁、占用空间最小；而在既要求速度，空间又比较紧张时常用查表＋计算法。 下面我们分别就这三种方法进行讨论和比较。这里以使用广泛的51单片机为例，分别用查表、计算、查表＋计算三种方法计算1021多项式（CRC-ITU）校验。原始程序都是在网上或杂志上经常能见到的，相信大家也比较熟悉了，甚至就是正在使用或已经使用过的程序。 编译平台采用Keil C51 7.0，使用小内存模式，编译器默认的优化方式。 常用的查表法程序如下，这是网上经常能够看到的程序范例。因为篇幅关系，省略了大部分表格的内容。 code unsigned int Crc1021Table[256] = { 0x0000, 0x1021, 0x2042, 0x3063,... 0x1ef0 }; unsigned int crc0(unsigned char *pData, unsigned char nLength) { unsigned int CRC16 = 0;
C R C校验原理及步骤 This model paper was revised by the Standardization Office on December 10, 2020
CRC校验原理及步骤 什么是CRC校验 CRC即循环冗余校验码：是数据通信领域中最常用的一种查错校验码，其特征是信息字段和校验字段的长度可以任意选定。循环冗余检查（CRC）是一种数据传输检错功能，对数据进行多项式计算，并将得到的结果附在帧的后面，接收设备也执行类似的算法，以保证数据传输的正确性和完整性。 CRC校验原理： 其根本思想就是先在要发送的帧后面附加一个数（这个就是用来校验的校验码，但要注意，这里的数也是二进制序列的，下同），生成一个新帧发送给接收端。当然，这个附加的数不是随意的，它要使所生成的新帧能与发送端和接收端共同选定的某个特定数整除（注意，这里不是直接采用二进制除法，而是采用一种称之为“模2除法”）。到达接收端后，再把接收到的新帧除以（同样采用“模2除法”）这个选定的除数。因为在发送端发送数据帧之前就已通过附加一个数，做了“去余”处理（也就已经能整除了），所以结果应该是没有余数。如果有余数，则表明该帧在传输过程中出现了差错。 模2除法： 模2除法与算术除法类似，但每一位除的结果不影响其它位，即不向上一位借位，所以实际上就是异或。在循环冗余校验码（CRC）的计算中有应用到模2除法。 例： CRC校验步骤：
CRC校验中有两个关键点，一是预先确定一个发送送端和接收端都用来作为除数的二进制比特串（或多项式），可以随机选择，也可以使用国际标准，但是最高位和最低位必须为1；二是把原始帧与上面计算出的除数进行模2除法运算，计算出CRC码。 具体步骤： 1. 选择合适的除数 2. 看选定除数的二进制位数，然后再要发送的数据帧上面加上这个位数-1位的0，然后用新生成的帧以模2除法的方式除上面的除数，得到的余数就是该帧的CRC校验码。注意，余数的位数一定只比除数位数少一位，也就是CRC校验码位数比除数位数少一位，如果前面位是0也不能省略。 3. 将计算出来的CRC校验码附加在原数据帧后面，构建成一个新的数据帧进行发送；最后接收端在以模2除法方式除以前面选择的除数，如果没有余数，则说明数据帧在传输的过程中没有出错。 CRC校验码计算示例： 现假设选择的CRC生成多项式为G（X）= X4+ X3+ 1，要求出二进制序列的CRC校验码。下面是具体的计算过程： ①将多项式转化为二进制序列，由G（X）= X4+ X3+ 1可知二进制一种有五位，第4位、第三位和第零位分别为1，则序列为11001 ②多项式的位数位5，则在数据帧的后面加上5-1位0，数据帧变为，然后使用模2除法除以除数11001，得到余数。【补几位0与x的最高次幂相同，模除就是进行异或】
循环冗余校验码( CRC)的基本原理是：在K 位信息码后再拼接R位的校验码，整个编码长度为N 位，因此，这种编码又叫( N，K)码。对于一个给定的(N，K)码，可以证明存在一个最高次幂为N-K=R的多项式G(x) 。根据G(x) 可以生成K位信息的校验码，而G(x)叫做这个CRC码的生成多项式。校验码的具体生成过程为：假设发送信息用信息多项式C(X)表示，将C(x) 左移R位，则可表示成C(x)*2 的R次方，这样C(x) 的右边就会空出R位，这就是校验码的位置。通过C(x)*2 的R次方除以生成多项式G(x) 得到的余数就是校验码。编辑本段几个基本概念 1、多项式与二进制数码 多项式和二进制数有直接对应关系：x 的最高幂次对应二进制数的最高位，以下各位对应多项式的各幂次，有此幂次项对应1，无此幂次项对应0。可以看出：x 的最高幂次为R，转换成对应的二进制数有R+1位。 多项式包括生成多项式G(x)和信息多项式C(x) 。如生成多项式为 G(x)=x^4+x^3+x+1 ，可转换为二进制数码11011。而发送信息位1111 ，可转换为数据多项式为C(x)=x^3+x^2+x+1 。 2、生成多项式是接受方和发送方的一个约定，也就是一个二进制数，在整个传输过程中，这个数始终保持不变。 在发送方，利用生成多项式对信息多项式做模2 除生成校验码。在接受方利用生成多项式对收到的编码多项式做模2 除检测和确定错误位置。 应满足以下条件： a、生成多项式的最高位和最低位必须为1。 b、当被传送信息( CRC码)任何一位发生错误时，被生成多项式做除后应该使余数不为0。 c、不同位发生错误时，应该使余数不同。 d、对余数继续做除，应使余数循环。 3 CRC码的生成步骤 1、将x 的最高次幂为R的生成多项式G(x) 转换成对应的R+1位二进制数。 2、将信息码左移R位，相当与对应的信息多项式C(x)*2 的R次方。 3、用生成多项式(二进制数)对信息码做除，得到R 位的余数。 4、将余数拼到信息码左移后空出的位置，得到完整的CRC码。 例】假设使用的生成多项式是G(x)=x^3+x+1 。4 位的原始报文为1010， 求编码后的报文。 解：
计算法简单实现crc校验 计算法简单实现crc校验 前一段时间做协议转换器的时间用到CRC-16校验，查了不少资料发现都不理想。查表法要建表太麻烦，而计算法觉得那些例子太罗嗦。最后只好自己写了，最后发现原来挺简单嘛：）两个子程序搞定。这里用的多项式为：CRC-16=X16+X12+X5+X0=2 +2 +2+2 =0x11021 因最高位一定为“1”，故略去计算只采用0x1021即可 CRC_Byte：计算单字节的CRC值 CRC_Data：计算一帧数据的CRC值 CRC_HighCRC_Low：存放单字节CRC值 CRC16_HighCRC16_Low：存放帧数据CRC值; ------------------------------------------------------------- ;Functi on:CRConebyte ;Input:CRCByte ;Output:CRC_HighCRC_Low ; ------------------------------------------------------------- CRC_Byte: clrfCRC_Low clrfCRC_High movlw09H movwfv_Loop1 movfCRCByte,w movwfCRC_High CRC: decfszv_Loop1；8次循环，每一位相应计算 gotoCRC10 gotoCRCend CRC10 bcfSTATUS,C rlfCRC_Low rlfCRC_High btfssSTATUS,C ;gotoCRC；为0不需计算movlw10H;若多项式改变，这里作相应变化xorwfCRC_High,f movlw21H;若多项式改变，这里作相应变化 xorwfCRC_Low,f gotoCRC CRCend: nop nop return ; ------------------------------------------------------------- ;CRCone byteend ; ------------------------------------------------------------- ; ------------------------------------------------------------- ;Functi on:CRCdate ;Input:BufStart(A,B,C)（一帧数据的起始地址）v_Count（要做CRC的字节数）;Output:CRC16_HighCRC16_Low（结果）; ------------------------------------------------------------- CRC_Data: clrfCRC16_High clrfCRC16_Low CRC_Data10 movfINDF,w
循环冗余校验码（CRC）的基本原理是：在K位信息码后再拼接R位的校验码，整个编码长度为N位，因此，这种编码又叫（N，K）码。对于一个给定的（N，K）码，可以证明存在一个最高次幂为N-K=R的多项式G(x)。根据G(x)可以生成K位信息的校验码，而G(x)叫做这个CRC码的生成多项式。校验码的具体生成过程为：假设发送信息用信息多项式C(X)表示，将C(x)左移R位，则可表示成C(x)*2的R次方，这样C(x)的右边就会空出R位，这就是校验码的位置。通过C(x)*2的R次方除以生成多项式G(x)得到的余数就是校验码。 编辑本段 几个基本概念 1、多项式与二进制数码 多项式和二进制数有直接对应关系：x的最高幂次对应二进制数的最高位，以下各位对应多项式的各幂次，有此幂次项对应1，无此幂次项对应0。可以看出：x的最高幂次为R，转换成对应的二进制数有R+1位。 多项式包括生成多项式G(x)和信息多项式C(x)。 如生成多项式为G(x)=x^4+x^3+x+1，可转换为二进制数码11011。 而发送信息位1111，可转换为数据多项式为C(x)=x^3+x^2+x+1。 2、生成多项式 是接受方和发送方的一个约定，也就是一个二进制数，在整个传输过程中，这个数始终保持不变。 在发送方，利用生成多项式对信息多项式做模2除生成校验码。在接受方利用生成多项式对收到的编码多项式做模2除检测和确定错误位置。 应满足以下条件： a、生成多项式的最高位和最低位必须为1。 b、当被传送信息（CRC码）任何一位发生错误时，被生成多项式做除后应该使余数不为0。 c、不同位发生错误时，应该使余数不同。 d、对余数继续做除，应使余数循环。 3 CRC码的生成步骤 1、将x的最高次幂为R的生成多项式G(x)转换成对应的R+1位二进制数。 2、将信息码左移R位，相当与对应的信息多项式C(x)*2的R次方。 3、用生成多项式（二进制数）对信息码做除，得到R位的余数。 4、将余数拼到信息码左移后空出的位置，得到完整的CRC码。 【例】假设使用的生成多项式是G(x)=x^3+x+1。4位的原始报文为1010，求编码后的报文。 解： 1、将生成多项式G(x)=x^3+x+1转换成对应的二进制除数1011。 2、此题生成多项式有4位（R+1），要把原始报文C(x)左移3（R）位变成1010000 3、用生成多项式对应的二进制数对左移3位后的原始报文进行模2除，相当于按位异或： 1010000
crc校验码计算例题 1、若信息码字为11100011，生成多项式G（X）=X5+X4+X+1，则计算出的CRC 校验码为？x的最高次幂5则信息码(被除数)补五个0为：1110001100000 除数为110011 ------------10110110 --------------------- 110011/1110001100000 -------110011 ------------------ ---------101111 ---------110011 ------------------ ----------111000 ----------110011 ------------------ ------------101100 ------------110011 ------------------------ -------------111110 -------------110011 ------------------------- ---------------11010 2、信息码为101110101，生成多项式X4+X2+1，求冗余位？？？ 算法同上被除数补四个0 为：1011101010000 除数为：10101 答案：1100 7E 00 05 60 31 32 33 计算CRC16结果应该是：5B3E 方法如下： CRC-16码由两个字节构成，在开始时CRC寄存器的每一位都预置为1，然后把CRC寄存器与8-bit的数据进行异或(异或：二进制运算相同为0，不同为1；0^0=0;0^1=1;1^0=1;1^1=0)，之后对CRC寄存器从
CRC算法及C实现 学习体会2008-09-20 15:21:13 阅读161 评论0 字号：大中小订 阅 一、CRC算法原理 CRC校验的基本思想是利用线性编码理论，在发送端根据要传送的k位二进制码序列，以一定的规则产生一个校验用的监督码（既CRC码）r位，并附在信息后边，构成一个新的二进制码序列数共(k+r)位，最后发送出去。在接收端，则根据信息码和CRC码之间所遵循的规则进行检验，以确定传送中是否出错。 16位的CRC码产生的规则是先将要发送的二进制序列数左移16位（既乘以）后，再除以一个多项式，最后所得到的余数既是 CRC码。 假设数据传输过程中需要发送15位的二进制信息 g=101001110100001，这串二进制码可表示为代数多项式g(x) = x^14 + x^12 + x^9 + x^8 + x^7 + x^5 + 1，其中g中第k位的值，对应g(x)中x^k的系数。将g(x)乘以x^m，既将g后加m个0，然后除以m阶多项式h(x)，得到的(m-1)阶余项 r(x)对应的二进制码r就是 CRC编码。 h(x)可以自由选择或者使用国际通行标准，一般按照h(x)的阶数m，将CRC算法称为CRC-m，比如CRC-32、CRC-64等。国际通行标准可
以参看 https://www.doczj.com/doc/d4558739.html,/wiki/Cyclic_redundancy_check g(x)和h(x)的除运算，可以通过g和h做xor（异或）运算。比如将 11001与10101做xor运算： 明白了xor运算法则后，举一个例子使用CRC-8算法求101001110100001的效验码。CRC-8标准的h(x) = x^8 + x^7 + x^6 + x^4 + x^2 + 1，既h是9位的二进制串111010101。
CRC 校验码的原理 在通信与数字信号处理等领域中循环冗余校验码（Cyclic Redundancy Check,CRC ）是一种很常用的设计。一般来说数据通信中的编码可以分为信源编码和信道编码两大类，其中，为了提高数据通信的可靠性而采取的编码称为信道编码，即抗干扰编码。在通信系统中，要求数据传输过程中的误码率足够低，而为了降低数据传输过程中的误码率，经常采用的一种方法是差错检测控制。 在实际的通信系统中，差错检测控制的主要方法又3种：前向纠错（FEC ），自动重发（ARQ ）和反馈检验法。FEC 指接收端不仅能够在收到的信码中发现错码，而且还能够纠正错码。一般来说，这种方法不需要反向信道，实时性很好，不过设备较复杂。ARQ 是指接收端在收到的信码中检测出错码时，即设法通知发送端重新发送信号，直到能够正确接收为止。通常，这种方法只用来检测误码，而且只能在双向信道中使用。反馈检验法是指接收端将收到的信码一字不差地转发回发送端，同时与原发送信码进行比较，如果有错，则发端重发。这种方法的原理和设备都比较简单，但需要双向信道的支持，而且传输效率低下； 通过实践检验，在这三中方法中，如果传输过程中的误码率较低，那么采用前向纠错法比较理想，但如果误码率较高时，这种方法又会出现“乱纠”的现象；在网络通信中，广泛的采用差错检测方法时自动请求重发，这种方法只要检错功能即可；反馈检验法时前向纠错法和自动请求重发的结合。 在实现差错检测控制的众多方法中，循环冗余校验就是一类重要的线性分组码。它时一种高效的差错控制方法，它广泛应用于测控及数据通信领域，同时具有编码和解码方法简单，检错能力强，误判概率很低和具有纠错能力等优点。 循环冗余校验码实现的方法 CRC 的基本原理就是在一个P 位二进制数据序列之后附加一个R 位二进制检验码序列，从而构成一个总长位N=P+R 位的二进制序列。例如，P 位二进制数据序列D=[d 1-p d 2-p …d 1d 0]，R 位二进制检验码R = [r 1-r r 2-r …r 1r 0],那么所得到的这个N 位二进制序列就是M=[d 1-p d 2-p …d 1d 0 r 1-r r 2-r …r 1r 0]，这里附加在数据序列之后的CRC 码与数据序列的内容之间存在着某种特定的关系。如果在数据传输过程中，由于噪声或传输特性不理想而使数据序列中的某一位或某些位发生错误，这种特定关系就会被破坏。可见在数据的接收端通过检查这种特定关系，可以很容易地实现对数据传输正确性的检验。 在CRC 中，检验码R 使通过对数据序列D 进行二进制除法取余式运算得到的，他被一个称为生成多项式的（r+1）位二进制序列G=[g r g 1-r …g 1g 0]来除，具体的多项式除法形式如下： ) ()(x G x D x r =Q(x)+ ) ()(x G x R 其中，)(x D x r 表示将数据序列D 左移r 位，即在D 的末尾再增加r 个0位；Q （x ）代表这一除法所得的商，R （x ）就是所需的余式。此外，这一运算关系还可以表示为 ?? ? ???=)()(Re )(x G x D x x R r ?? ? ? ??=)()(Re )(x G x M x R 通过上面CRC 基本原理的介绍，可以发现生成多项式使一个非常重要的概念，它决定了CRC 的具体算法。目前，生成多项式具有一下一些通用标准，其中CRC -12，CRC -16，
1、循环冗余校验码原理 CRC 校验采用多项式编码方法，如一个8 位二进制数(B7B6B5B4B3B2B1B0)可以用7 阶二进制码多项式B7X7+B6X6+B5X5+B4X4+B3X3+B2X2+B1X1+B0X0表示。 例如11000001 可表示为 1X7+1X6+0X5+0X4+0X3+0X2+0X1+0X0 一般说，n 位二进制数可用(n-1)阶多项式表示。它把要发送的数据位串看成是系数只能为“1”或“0”的多项式。一个n 位的数据块可以看成是从Xn-1到X0的n 项多项式的系数 序列，位于数据块左边的最高位是X n-1项的系数，次高位是X n-2项的系数，依此类推，位 于数据块右边的最低位是X0项的系数，这个多项式的阶数为n-1。 多项式乘除法运算过程与普通代数多项式的乘除法相同。多项式的加减法运算以2 为模，加减时不进、错位，如同逻辑异或运算。 采用CRC 校验时，发送方和接收方事先约定一个生成多项式G(X)，并且G(X)的最高项和最低项的系数必须为1。设m 位数据块的多项式为M(X)，生成多项式G(X)的阶数必需 比M(X)的阶数低。CRC 校验码的检错原理是：发送方先为数据块生成CRC 校验码，使这 个CRC 校验码的多项式能被G(X)除尽，实际发送此CRC 校验码；接收方用收到的CRC 校 验码除以G(X)，如果能除尽，表明传输正确，否则，表示有传输错误，请求重发。 生成数据块的CRC 校验码的方法是： (1) 设G(X)为r 阶，在数据块末尾添加r 个0，使数据块为m+r 位，则相应的多项式 为XrM(X)； (2) 以2 为模，用对应于G(X)的位串去除对应于XrM(X)的位串，求得余数位串； (3) 以2 为模，从对应于XrM(X)的位串中减去余数位串，结果就是为数据块生成的带足够校验信息的CRC 校验码位串。 例如，设要发送的数据为1101011011，G(X)=X4+X+1，则首先在发送数据块的末尾加4 个0，得到11010110110000，然后用G(X)的位串10011 去除，再用11010110110000 减去余 数位串1110，得到的即为CRC 位串11010110111110，将对应多项式称为T(X)，显然，T(X) 能被G(X)除尽。这样，一旦接收到的CRC 位串不能被同样的G(X)的位串除尽，那么一定 有传输错误。 当使用CRC校验码进行差错控制时，除了为G(X)的整数倍的差错多项式不能被检测外，其它差错均能被查出。CRC 校验码的差错控制效果取决于G(X)的阶数，阶数越高，效果越 好。目前，常用的有两种生成多项式G(X)的方法，分别是： CRC-16 X16+X15+X2+1 CCITT X16+X12+X5+1
校验原理 1、循环校验码（CRC码）：是数据通信领域中最常用的一种差错校验码，其特征是信息字段和校验字段的长度可以任意选定。 2、生成CRC码的基本原理：任意一个由二进制位串组成的代码都可以和一个系数仅为‘0’和‘1’取值的多项式一一对应。例如：代码1010111对应的多项式为x6+x4+x2+x+1，而多项式为x5+x3+x2+x+1对应的代码101111。 3、CRC码集选择的原则：若设码字长度为N，信息字段为K位，校验字段为R 位(N=K+R)，则对于CRC码集中的任一码字，存在且仅存在一个R次多项式g(x)，使得 V(x)=A(x)g(x)=x R m(x)+r(x); 其中: m(x)为K次信息多项式， r(x)为R-1次校验多项式， g(x)称为生成多项式： g(x)=g0+g1x+g2x2+...+g(R-1)x(R-1)+g R x R 发送方通过指定的g(x)产生CRC码字，接收方则通过该g(x)来验证收到的CRC 码字。 4、CRC校验码软件生成方法： 借助于多项式除法，其余数为校验字段。 例如：信息字段代码为: 1011001；对应m(x)=x6+x4+x3+1 假设生成多项式为：g(x)=x4+x3+1；则对应g(x)的代码为: 11001 x4m(x)=x10+x8+x7+x4对应的代码记为：10110010000； 采用多项式除法: 得余数为: 1010 (即校验字段为：1010） 发送方：发出的传输字段为: 1 0 1 1 0 0 1 1 0 10
信息字段校验字段 接收方：使用相同的生成码进行校验:接收到的字段/生成码（二进制除法）如果能够除尽，则正确，
CRC算法原理及其Verilog实现 1CRC简介 CRC校验是一种在数据通信系统和其它串行传输系统中广泛使用的错误检测手段。通用的CRC标准有CRC-8、CRC-16、CRC-32、CRC-CCIT，其中在网络通信系统中应用最广泛的是CRC-32标准。本文将以CRC-32为例，说明CRC编码的实现方式以及如何用verilog语言对CRC编码进行描述。 2二．模2运算 在说明CRC编码方式之前，首先介绍一下模2运算法则，在CRC运算过程中会使用到模2除法运算。模2运算是一种二进制运算法则，与四则运算相同，模2运算也包括模2加、模2减、模2乘、模2除四种运算。模2运算用“+”表示加法运算，用“-”、“×”或“.”、“/”分别表示减法、乘法和除法运算。与普通四则运算法则不同的是，模2加法是不带进位的二进制加法运算，模2减法是不带借位的二进制减法运算。同时，模2乘法在累加中间结果时采用的是模2加法运算；模2除法求商过程中余数减除数采用的是模2减法运算。因此，两个二进制数进行模2加减法运算时，相当于两个二进制数进行按位异或运算，每一位的结果只与两个数的当前位有关。模2除法在确定商时，与普通二进制除法也略有区别。普通二进制除法中，当余数小于除数时，当前位的商为0，当余数大于等于除数时，当前位的商为1。模2除法在确定当前位的商时，只关心余数的首位，首位为1则商为1，首位为0则商为0。 1.模2加法的定义： 0+0=0，0+1=1，1+0=1，1+1=0。 举例如下： 1010+0110=1100。 2.模2减法的定义：
0-0=0，0-1=1，1-0=1，1-1=0。 举例如下： 1010-0110=1100。 3.模2乘法的定义： 0×0=0，0×1=0，1×0=0，1×1=1。 举例如下： 1011×101=100111 列竖式计算： 1011 × 101 —————— 1011 0000 1011 —————— 100111 其中横线之间的累加过程，采用的是2进制加法，不进位。 4.模2除法： 0/1=0，1/1=1。 举例如下： 1011/101=10，余数为100。 列竖式计算： 10 ———— 101 ）1011 101 ———— 001 101
CRC校验 校验原理: 1、循环校验码（CRC码）：是数据通信领域中最常用的一种差错校验码，其特征是信息字段和校验字段的长度可以任意选定。 2、生成CRC码的基本原理：任意一个由二进制位串组成的代码都可以和一个系数仅为‘0’和‘1’取值的多项式一一对应。例如：代码1010111对应的多项式为x6+x4+x2+x+1，而多项式为x5+x3+x2+x+1对应的代码101111。 3、CRC码集选择的原则：若设码字长度为N，信息字段为K位，校验字段为R 位(N=K+R)，则对于CRC码集中的任一码字，存在且仅存在一个R次多项式g(x)，使得 V(x)=A(x)g(x)=x R m(x)+r(x); 其中: m(x)为K次信息多项式， r(x)为R-1次校验多项式， g(x)称为生成多项式： g(x)=g 0+g 1 x+g 2 x2+...+g (R-1) x(R-1)+g R x R 发送方通过指定的g(x)产生CRC码字，接收方则通过该g(x)来验证收到的CRC 码字。 4、CRC校验码软件生成方法： 借助于多项式除法，其余数为校验字段。 例如：信息字段代码为: 1011001；对应m(x)=x6+x4+x3+1 假设生成多项式为：g(x)=x4+x3+1；则对应g(x)的代码为: 11001 x4m(x)=x10+x8+x7+x4对应的代码记为：10110010000； 采用多项式除法: 得余数为: 1010 (即校验字段为：1010）
发送方：发出的传输字段为: 1 0 1 1 0 0 1 1 0 10 信息字段校验字段 接收方：使用相同的生成码进行校验:接收到的字段/生成码（二进制除法）如果能够除尽，则正确，
CRC校验算法学习(这个算法看了很多遍了,都是囫囵吞枣,这次将资料拷贝到这里,好好学习一下) (2008-2-23 23:18)CRC校验采用多项式编码方法。 被处理的数据块可以看作是一个二进制多项式，例如，10110101可以看作是2^7+2^5+2^4+2^2+2^0,多项式乘除法运算过程与普通代数多项式的乘除法相同。多项式的加减法运算以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校验采用16位CRC校验。在IBM的同步数据链路控制规程SDLC的帧校验序列FCS中，使用CRC-16。g（x）的位数越高，检错能力就越强。由于CRC-32的可靠性，把CRC-32用于重要数据传输十分合适，所以在通信、计算机等领域运用十分广泛。在一些UART通信控制芯片（如MC6582、Intel8273和Z80-SIO）内，都采用了CRC校验码进行差错控制；以太网卡芯片、MPEG解码芯片中，也采用CRC-32进行差错控制。>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> >>> (转自https://www.doczj.com/doc/d4558739.html,/forum/viewthread.php?tid=5470&sid=3rrqV omR) CRC校验码的基本思想是利用线性编码理论，在发送端根据要传送的k位二进制码序列，以一定的规则产生一个校验用的监督码（既CRC码）r位，并附在信息后边，构成一个新的二进制码序列数共(k+r)位，最后发送出去。在接收端，则根据信息码和CRC码之间所遵循的规则进行检验，以确定传送中是否出错。 在数据存储和数据通讯领域，CRC无处不在:著名的通讯协议X.25的FCS(帧检错序列)采用的是CRC. CCITT，ARJ、LHA等压缩工具软件采用的是CRC32，磁盘驱动器的读写采用了CRC16，通用的图像存储格式GIF、TIFF等也都用CRC作为检错手段。 CRC的本质是模-2除法的余数，采用的除数不同，CRC的类型也就不一样。通常，CRC 的除数用生成多项式来表示。最常用的CRC码的生成多项式有CRC16,CRC32. 以CRC16为例,16位的CRC码产生的规则是先将要发送的二进制序列数左移16位（既乘以2^16）后，再除以一个多项式，最后所得到的余数既是CRC码，如下式所示，其中K(X)表示n位的二进制序列数，G(X)为多项式，Q(X)为整数，R(X)是余数（既CRC码）。K(X)>>16=G(x)Q(x)+R(x) 求CRC码所采用模2加减运算法则，既是不带进位和借位的按位加减，这种加减运算实际上就是逻辑上的异或运算，加法和减法等价，乘法和除法运算与普通代数式的乘除法运算是一样，符合同样的规律。生成CRC码的多项式如下，其中CRC-16和CRC-CCITT产生16位的CRC码，而CRC-32则产生的是32位的CRC码 接收方将接收到的二进制序列数（包括信息码和CRC码）除以多项式，如果余数为0，则说明传输中无错误发生，否则说明传输有误，关于其原理这里不再多述。用软件计算CRC 码时，接收方可以将接收到的信息码求CRC码，比较结果和接收到的CRC码是否相同。 CCITT推荐的高级数据链路控制规程HDLC的帧校验序列FCS中，使用CCITT-16即CRC16,其生成多项式为G(x)=x16+x12+x5+1, CRC-32的生成多项式为G(x)=x32+x26+x23+x22+x16+x11+x10+x16+x8+x7+x5+x4+x2+x+1 >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
CRC校验函数 cBuffer：计算CRC校验码的数组。 iBufLen：该数组的长度。 unsigned int CRC_Verify(unsigned char *cBuffer, unsigned int iBufLen) { unsigned int i, j; //#define wPolynom 0xA001 unsigned int wCrc = 0xffff; unsigned int wPolynom = 0xA001; /*---------------------------------------------------------------------------------*/ for (i = 0; i < iBufLen; i++) { wCrc ^= cBuffer[i]; for (j = 0; j < 8; j++) { if (wCrc &0x0001) { wCrc = (wCrc >> 1) ^ wPolynom; } else { wCrc = wCrc >> 1; } } } return wCrc; } 如何用PLC写上述的CRC校验函数，笔者整理了一个CRC校验计算的子程序。 CRC-16码由两个字节构成，在开始时CRC寄存器的每一位都预置为1（0xffff），然后把CRC寄存器与8-bit的数据进行异或，之后对CRC寄存器从高到低进行移位，在最高位（MSB）的位置补零，而最低位（LSB），移位后已经被移出CRC寄存器）如果为1，则把寄存器与预定义的多项式码（16#A001）进行异或，否则如果LSB为零，则无需进行异或。重复上述的由高至低的移位8次，第一个8-bit数据处理完毕，用此时CRC寄存器的值与下一个8-bit 数据异或并进行如前一个数据似的8次移位。所有的字符处理完成后CRC寄存器内的值即为最终的CRC值。 下面为CRC的计算过程： 1．设置CRC寄存器，并给其赋值FFFF(hex)。 2．将数据的第一个8-bit字符与16位CRC寄存器的低8位进行异或，并把结果存入CRC寄存器。 3．CRC寄存器向右移一位，MSB补零，移出并检查LSB。 4．如果LSB为0，重复第三步；若LSB为1，CRC寄存器与多项式码相异或。 5．重复第3与第4步直到8次移位全部完成。此时一个8-bit数据处理完毕。 6．重复第2至第5步直到所有数据全部处理完成。 7．最终CRC寄存器的内容即为CRC值。 输入参数： 待校验数据区指针，第一个字节为数据长度
CCITT CRC-16计算原理与实现 CRC的全称为Cyclic Redundancy Check，中文名称为循环冗余校验。它是一类重要的线性分组码，编码和解码方法简单，检错和纠错能力强，在通信领域广泛地用于实现差错控制。实际上，除数据通信外，CRC在其它很多领域也是大有用武之地的。例如我们读软盘上的文件，以及解压一个ZIP文件时，偶尔会碰到“Bad CRC”错误，由此它在数据存储方面的应用可略见一斑。 差错控制理论是在代数理论基础上建立起来的。这里我们着眼于介绍CRC的算法与实现，对原理只能捎带说明一下。若需要进一步了解线性码、分组码、循环码、纠错编码等方面的原理，可以阅读有关资料。 利用CRC进行检错的过程可简单描述为：在发送端根据要传送的k位二进制码序列，以一定的规则产生一个校验用的r位监督码(CRC码)，附在原始信息后边，构成一个新的二进制码序列数共k+r位，然后发送出去。在接收端，根据信息码和CRC码之间所遵循的规则进行检验，以确定传送中是否出错。这个规则，在差错控制理论中称为“生成多项式”。 1 代数学的一般性算法 在代数编码理论中，将一个码组表示为一个多项式，码组中各码元当作多项式的系数。例如 1100101 表示为 1·x6+1·x5+0·x4+0·x3+1·x2+0·x+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)。用公式表示为 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) x3(x3+x2) x6+x5 x -------
CRC 校验码的计算方法 CRC从原理到实现=============== 作者：Spark Huang(hcpp@https://www.doczj.com/doc/d4558739.html,) 日期：2004/12/8 摘要：CRC(Cyclic Redundancy Check)被广泛用于数据通信过程中的差错检测，具有很强的检错能力。本文详细介绍了CRC的基本原理，并且按照解释通行的查表算法的由来的思路介绍了各种具体的实现方法。 1.差错检测 数据通信中，接收端需要检测在传输过程中是否发生差错，常用的技术有奇偶校验(Parity Check)，校验和(Checksum)和CRC(Cyclic Redundancy Check)。它们都是发送端对消息按照某种算法计算出校验码，然后将校验码和消息一起发送到接收端。接收端对接收到的消息按照相同算法得出校验码，再与接收到的校验码比较，以判断接收到消息是否正确。 奇偶校验只需要1位校验码，其计算方法也很简单。以奇检验为例，发送端只需要对所有消息位进行异或运算，得出的值如果是0，则校验码为1，否则为0。接收端可以对消息进行相同计算，然后比较校验码。也可以对消息连同校验码一起计算，若值是0则有差错，否则校验通过。 通常说奇偶校验可以检测出1位差错，实际上它可以检测出任何奇数位差错。 校验和的思想也很简单，将传输的消息当成8位(或16/32位)整数的序列，将这些整数加起来而得出校验码，该校验码也叫校验和。校验和被用在IP协议中，按照16位整数运算，而且其MSB(Most Significant Bit)的进位被加到结果中。 显然，奇偶校验和校验和都有明显的不足。奇偶校验不能检测出偶数位差错。对于校验和，如果整数序列中有两个整数出错，一个增加了一定的值，另一个减小了相同的值，这种差错就检测不出来。 2.CRC算法的基本原理------------------- CRC算法的是以GF(2)(2元素伽罗瓦域)多项式算术为数学基础的，听起来很恐怖，但实际上它 的主要特点和运算规则是很好理解的。 GF(2)多项式中只有一个变量x，其系数也只有0和1，如： 1*x^7 + 0*x^6 + 1*x^5 + 0*x^4 + 0*x^3 + 1*x^2 +1*x^1 + 1*x^0
CAN总线中循环冗余校验码的原理 在ＣＡＮ系统中为保证报文传输的正确性，需要对通信过程进行差错控制。目前常用的方法是反馈重发，即一旦收到接收端发出的出错信息，发送端便自动重发，此时的差错控制只需要检错功能。常用的检错码有两类：奇偶校验码和循环冗余校验码。奇偶校验码是一种最常见的检错码，其实现方法简单，但检错能力较差；循环冗余校验码的编码也很简单且误判率低，所以在通信系统中获得了广泛的应用。下面介绍ＣＡＮ网络中循环冗余校验码（即ＣＲＣ码）的原理和实现方法。 １ＣＲＣ码检错的工作原理 ＣＲＣ码检错是将被处理报文的比特序列当作一个二进制多项式Ａ（ｘ）的系数，该系数除以发送方和接收方预先约定好的生成多项式ｇ（ｘ）后，将求得的余数ｐ（ｘ）作为ＣＲＣ校验码附加到原始的报文上，并一起发给接收方。接收方用同样的ｇ（ｘ）去除收到的报文Ｂ（ｘ），如果余数等于ｐ（ｘ），则传输无误（此时Ａ（ｘ）和Ｂ（ｘ）相同）；否则传输过程中出错，由发送端重发，重新开始ＣＲＣ校验，直到无误为止。 上述校验过程中有几点需注意：①在进行ＣＲＣ计算时，采用二进制（模２）运算法，即加法不进位，减法不借位，其本质就是两个操作数进行逻辑异或运算；②在进行ＣＲＣ计算前先将发送报文所表示的多项式Ａ（ｘ）乘以ｘn，其中ｎ为生成多项式ｇ（ｘ）的最高幂值。对二进制乘法来讲，Ａ（ｘ）·ｘn 就是将Ａ（ｘ）左移ｎ位，用来存放余数（ｘ），所以实际发送的报文就变为Ａ（ｘ）·ｘn＋ｐ（ｘ）；③生成多项式ｇ（ｘ）的首位和最后一位的系数必须为１。 图１为ＣＲＣ校验的工作过程。 目前已经有多种生成多项式被列入国际标准中，如：ＣＲＣ－４、ＣＲＣ－１２、ＣＲＣ－１６、ＣＣＩＴＴ－１６、ＣＲＣ－３２等。ＣＡＮ总线中采