crc算法原理及实现

❶ 高手解释下crc的具体算法和用法

一、循环冗余码校验英文名称为Cyclical Rendancy
Check，简称CRC。它是利用除法及余数的原理来作错误侦测（Error
Detecting）的。实际应用时，发送装置计算出CRC值并随数据一同发送给接收装置，接收装置对收到的数据重新计算CRC并与收到的CRC相比较，若两个CRC值不同，则说明数据通讯出现错误。
根据应用环境与习惯的不同，CRC又可分为以下几种标准：
①CRC-12码；
②CRC-16码；
③CRC-CCITT码；
④CRC-32码。
CRC-12码通常用来传送6-bit字符串。CRC-16及CRC-CCITT码则用是来传送8-bit字符，其中CRC-16为美国采用，而CRC-CCITT为欧洲国家所采用。CRC-32码大都被采用在一种称为Point-to-Point的同步传输中。
下面以最常用的CRC-16为例来说明其生成过程。
CRC-16码由两个字节构成，在开始时CRC寄存器的每一位都预置为1，然后把CRC寄存器与8-bit的数据进行异或，之后对CRC寄存器从高到低进行移位，在最高位（MSB）的位置补零，而最低位（LSB，移位后已经被移出CRC寄存器）如果为1，则把寄存器与预定义的多项式码进行异或，否则如果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值。
常用的CRC循环冗余校验标准多项式如下：
CRC(16位) = X16+X15+X2+1
CRC(CCITT) = X16+X12 +X5+1
CRC(32位) = X32+X26+X23+X16+X12+X11+X10+ X8+X7+X5+X4+X2+X+1
以CRC(16位)多项式为例，其对应校验二进制位列为1 1000 0000 0000 0101。
注意：这儿列出的标准校验多项式都含有(X+1)的多项式因子；各多项式的系数均为二进制数，所涉及的四则运算仍遵循对二取模的运算规则。
(注：对二取模的四则运算指参与运算的两个二进制数各位之间凡涉及加减运算时均进行XOR异或运算，即：1 XOR 1=0，0 XOR 0=0，1 XOR 0=1)

❷ 请问:CRC是什么意思

CRC意思是循环冗余码校验。

校验原理：（M-R）/G=Q+0/G

说明：以接收到的校验码除以约定的除数，若余数为0，则可认为接收到的数据是正确的。

例：有效信息1101，生成多项式样1011

循环校验码解：

有效信息1101（k=4），即M（x）=x3+x2+x0，生成多项式1011（r+1=4，即r=3）；

即G（x）=x3+x1+x0，M（x）·x3=x6+x5+x3，即1101000（对1101左移三位）；

M（x）·x3/G（x）=1101000/1011=1111+001/1011即1010的CRC是：1101001。

(2)crc算法原理及实现扩展阅读：

CRC码集选择的原则：

若设码字长度为N，信息字段为K位，校验字段为R位（N=K+R），则对于CRC码集中的任一码字，存在且仅存在一个R次多项式g（x），使得

V（x）=A（x）g（x）=xRm（x）+r（x）；

其中：m（x）为K次信息多项式，r（x）为R-1次校验多项式，

g（x）称为生成多项式：

g（x）=g0+g1x+g2x2+。。。+g（R-1）x（R-1）+gRxR

发送方通过指定的g（x）产生CRC码字，接收方则通过该g（x）来验证收到的CRC码字。

❸ 关于计算机网络的crc计算

我们知道，一台主机向另外一台主机发送报文的时候，需要一层层经过自己的协议栈进行数据封装，到达最后一层（四层协议的网络接口层）时需要在帧尾部添加FCS校验码（通过CRC算法得出）。当对端主机收到时，在接收端同样通过CRC算法进行验证，确认传输过程中是否出现错误。它只能确认一个帧是否存在比特差错，但没有提供解决措施。

循环冗余校验的原理

• 在发送端，先把数据划分为组（即：一帧）。假定每组 k 个比特。

• 在每组后面，添加供差错检测用的 n 位冗余码一起发送。即：实际发送长度为：k+n 比特。

• 发送前双方协商n+1位的除数P，方便接收方收到后校验。

• 给K比特的数据添加除数减一个0（P-1）作为被除数，与第三步确定的除数做“模2除法”。得出的余数即FCS校验序列，它的位数也必须是（P-1）。

• 将FCS校验序列添加至K个比特位的后面发送出去。

• 接收方对接收到的每一帧进行校验，若得出的余数 R = 0，则判定这个帧没有差错，就接受(accept)。若余数 R ≠ 0，则判定这个帧有差错，就丢弃。

对“模2除法”进行说明：

“模2除法”与“算术除法”类似，但它既不向上位借位，也不比较除数和被除数的相同位数值的大小，只要以相同位数进行相除即可。模2加法运算为：1+1=0，0+1=1，0+0=0，无进位，也无借位；模2减法运算为：1-1=0，0-1=1，1-0=1，0-0=0，也无进位，无借位。相当于二进制中的逻辑异或运算。

计算示例


那么接收方拿到的就是：101001001。再以它为被除数，1101为除数进行“模2除法”。

❹ 循环冗余检验 (CRC) 算法原理

x只是一个标记，无任何意义。主要是看数字1,5,7,8,9,12,14。分别代表第二进制码的第0位，第5位，第7位，第8位。。。为1，其余则为0。

❺ CRC校验的算法

在代数编码理论中，将一个码组表示为一个多项式，码组中各码元当作多项式的系数。例如 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 G(x)= x3+x+1 即 R(x)=x。注意到G(x)最高幂次r=3，得出CRC为010。
如果用竖式除法(计算机的模二，计算过程为
1110 ------- 1011 /1100000 (1100左移3位) 1011 ---- 1110 1011 ----- 1010 1011 ----- 0010 0000 ---- 010 因此，T(x)=(x6+x5)+(x)=x6+x5+x, 即 1100000+010=1100010
如果传输无误，
T(x)= （x6+x5+x）/G(x) = , G(x)= 无余式。回头看一下上面的竖式除法，如果被除数是1100010，显然在商第三个1时，就能除尽。
上述推算过程，有助于我们理解CRC的概念。但直接编程来实现上面的算法，不仅繁琐，效率也不高。实际上在工程中不会直接这样去计算和验证CRC。
下表中列出了一些见于标准的CRC资料：
名称 生成多项式 简记式* 应用举例
CRC-4 x4+x+1 3 ITU G.704
CRC-8 x8+x5+x4+1 31 DS18B20
CRC-12 x12+x11+x3+x2+x+1 80F
CRC-16 x16+x15+x2+1 8005 IBM SDLC
CRC-ITU** x16+x12+x5+1 1021 ISO HDLC, ITU X.25, V.34/V.41/V.42, PPP-FCS,ZigBee
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。
备注：
（1）生成多项式是标准规定的
（2）CRC校验码是基于将位串看作是系数为0或1的多项式，一个k位的数据流可以看作是关于x的从k-1阶到0阶的k-1次多项式的系数序列。采用此编码，发送方和接收方必须事先商定一个生成多项式G(x)，其高位和低位必须是1。要计算m位的帧M(x)的校验和，基本思想是将校验和加在帧的末尾，使这个带校验和的帧的多项式能被G(x)除尽。当接收方收到加有校验和的帧时，用G(x)去除它，如果有余数，则CRC校验错误，只有没有余数的校验才是正确的。

❻ 关于CRC效验

为保证传输过程的正确性，需要对通信过程进行差错控制。差错控制最常用的方法是自动请求重发方式（ARQ）、向前纠错方式（FEC）和混合纠错（HEC）。在传输过程误码率比较低时，用FEC方式比较理想。在传输过程误码率较高时，采用FEC容易出现“乱纠”现象。HEC方式则是ARQ和FEC的结合。在许多数字通信中，广泛采用ARQ方式，此时的差错控制只需要检错功能。实现检错功能的差错控制方法很多，传统的有：奇偶校验、校验和检测、重复码校验、恒比码校验、行列冗余码校验等，这些方法都是增加数据的冗余量，将校验码和数据一起发送到接受端。接受端对接受到的数据进行相同校验，再将得到的校验码和接受到的校验码比较，如果二者一致则认为传输正确。但这些方法都有各自的缺点，误判的概率比较高。
循环冗余校验CRC（Cyclic Rendancy Check）是由分组线性码的分支而来，其主要应用是二元码组。编码简单且误判概率很低，在通信系统中得到了广泛的应用。下面重点介绍了CRC校验的原理及其算法实现。

CRC校验可以100％地检测出所有奇数个随机错误和长度小于等于k（k为g（x）的阶数）的突发错误。所以CRC的生成多项式的阶数越高，那么误判的概率就越小。

CRC代码的一些基本概念和运算：

CRC多项式：

例：

代码：1010111 对应的多项式为：X6+X4+X2+X+1

多项式X5+X3+X2+X1+1对应的代码为101111

CRC生成多项式:

首位和最后一位必须是1。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

CRC的运算本质是异或运算（模2除法）

例：原信息码为1011001

生成码为11001

校验码计算过程

① 将信息码左移4位（生成码长-1）；得到10110010000

② 异或运算

10110010000

11001

01111010000（前面的数进行异或运算，后面的直接抄下来）

11001

0011110000（和生成码异或运算的必须从1开始）

11001

00111000

11001

001010

这样得到的结果为1010，即为所需要的校验码，添加到信息码后，得到发送的代码为:

10110011010

我把上面的手算过程用c#写了一段程序，如下：

using System;

namespace mainClass
{
public class mainProgress
{
public static void Main()
{
byte[] msg={1,0,1,1,0,0,1};//信息码
byte[] gmsg=new byte[msg.Length+4];
crc c = new crc();
gmsg=c.code(msg);
Console.Write("编码后字符串为：");
for (int i = 0; i < gmsg.Length; i++)
{
Console.Write("{0}", gmsg[i].ToString());
}
Console.Write("\n");
byte[] gmsg1={ 1, 0, 1, 1, 0, 1, 1 };//接收到的代码
bool r = c.det(gmsg1);
if (r)
{
Console.WriteLine("传输正确");
}
else
{ Console.WriteLine("传输错误"); }
}
}

public class crc//CRC编码类
{
private byte[] g = { 1,1,0,0,1};//生成码
public byte[] code(byte[] msg)//编码
{
byte[] gmsg=new byte[g.Length+msg.Length-1];
msg.CopyTo(gmsg, 0);//
for (int i = 0; i < msg.Length; i++)//完成异或运算，即模2除法
{
if (gmsg[i] == 1)
{
for (int j = 0; j < g.Length; j++)
{
if (gmsg[i + j] == g[j])
gmsg[i + j] = 0;
else
gmsg[i + j] = 1;
}
}
}
msg.CopyTo(gmsg, 0);
return gmsg;
}
private bool f=true;

//接收端检测
public bool det(byte[] gmsg)
{
for (int i = 0; i < gmsg.Length - g.Length+1; i++)
{
if(gmsg[i]==0)
continue;
for (int j = 0; j < g.Length; j++)
{
if (gmsg[i + j] == g[j])
gmsg[i + j] = 0;
else
gmsg[i + j] = 1;
}
}
for (int i = 0; i < gmsg.Length; i++)
{
if (gmsg[i] == 1)
f = false;
}
return f;
}

}
}

❼ CRC校验的工作原理

循环冗余校验码（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)*2R），这样C(x)的右边就会空出R位，这就是校验码的位置。用 C(x)*2R 除以生成多项式G(x)得到的余数就是校验码。
任意一个由二进制位串组成的代码都可以和一个系数仅为‘0’和‘1’取值的多项式一一对应。例如：代码1010111对应的多项式为x6+x4+x2+x+1，而多项式为x5+x3+x2+x+1对应的代码101111。

❽ crc32算法原理

一、循环冗余码校验英文名称为Cyclical Rendancy Check,简称CRC.
它是利用除法及余数的原理来作错误侦测（Error Detecting）的.实际应用时,发送装置计算出CRC值并随数据一同发送给接收装置,接收装置对收到的数据重新计算CRC并与收到的CRC相比较,若两个CRC值不同,则说明数据通讯出现错误.
根据应用环境与习惯的不同,CRC又可分为以下几种标准：
①CRC-12码；
②CRC-16码；
③CRC-CCITT码；
④CRC-32码.
CRC-12码通常用来传送6-bit字符串.
CRC-16及CRC-CCITT码则用是来传送8-bit字符,其中CRC-16为美国采用,而CRC-CCITT为欧洲国家所采用.
CRC-32码大都被采用在一种称为Point-to-Point的同步传输中.
下面以最常用的CRC-16为例来说明其生成过程.
CRC-16码由两个字节构成,在开始时CRC寄存器的每一位都预置为1,然后把CRC寄存器与8-bit的数据进行异或(异或：二进制运算 相同为0,不同为1；0^0=0;0^1=1;1^0=1;1^1=0),
之后对CRC寄存器从高到低进行移位,在最高位（MSB）的位置补零,而最低位（LSB,移位后已经被移出CRC寄存器）如果为1,则把寄存器与预定义的多项式码进行异或,否则如果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值.
常用的CRC循环冗余校验标准多项式如下：
CRC(16位) = X16+X15+X2+1
CRC(CCITT) = X16+X12 +X5+1
CRC(32位) = X32+X26+X23+X16+X12+X11+X10+ X8+X7+X5+X4+X2+X+1
以CRC(16位)多项式为例,其对应校验二进制位列为1 1000 0000 0000 0101.
注意：这儿列出的标准校验多项式都含有(X+1)的多项式因子；各多项式的系数均为二进制数,所涉及的四则运算仍遵循对二取模的运算规则.
(注：对二取模的四则运算指参与运算的两个二进制数各位之间凡涉及加减运算时均进行XOR异或运算,即：1 XOR 1=0,0 XOR 0=0,1 XOR 0=1,0 XOR 1=1,即相同为0,不同为1)

❾ crc电路原理

CRC(Cyclic Rendancy Check)被广泛用于数据通信过程中的差错检测，具有很强的
检错能力。本文详细介绍了CRC的基本原理，并且按照解释通行的查表算法的由来的思路介绍
了各种具体的实现方法。
1.差错检测
数据通信中，接收端需要检测在传输过程中是否发生差错，常用的技术有奇偶校验(Parity
Check)，校验和(Checksum)和CRC(Cyclic Rendancy 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
即：
x^7 + x^5 + x^2 + x + 1
(x^n表示x的n次幂)
GF(2)多项式中的加减用模2算术执行对应项上系数的加减，模2就是加减时不考虑进位和借位，
即：
0 + 0 = 0 0 - 0 = 0
0 + 1 = 1 0 - 1 = 1
1 + 0 = 1 1 - 0 = 1
1 + 1 = 0 1 - 1 = 0
显然，加和减是一样的效果(故在GF(2)多项式中一般不出现"-"号)，都等同于异或运算。例
如P1 = x^3 + x^2 + 1，P2 = x^3 + x^1 + 1，P1 + P2为：
x^3 + x^2 + 1
+x^3 + x + 1
------------------------------
x^2 + x
GF(2)多项式乘法和一般多项式乘法基本一样，只是在各项相加的时候按模2算术进行，例如
P1 * P2为：
(x^3 + x^2 + 1)(x^3 + x^1 + 1)
= (x^6 + x^4 + x^3
+ x^5 + x^3 + x^2
+ x^3 + x + 1)
= x^6 + x^5 + x^4 + x^3 + x^2 + x + 1
GF(2)多项式除法也和一般多项式除法基本一样，只是在各项相减的时候按模2算术进行，例
如P3 = x^7 + x^6 + x^5 + x^2 + x，P3 / P2为：
x^4 + x^3 + 1
--------------------------------------------------------------
x^3 + x + 1 )x^7 + x^6 + x^5 + x^2 + x
x^7 + x^5 + x^4
-----------------------------------

❿ 请教查表法计算CRC的原理

1）将上次计算出的CRC校验码右移一个字节；
（2）将移出的这个字节与新的要校验的字节进行XOR 运算；
（3）用运算出的值在预先生成码表中进行索引，获取对应的值（称为余式）；
（4）用获取的值与第（1）步右移后的值进行XOR 运算；
（5）如果要校验的数据已经处理完，则第（4）步的结果就是最终的CRC校验码。如果还有数据 要进行处理，则再转到第（1）步运行。
CRC32=CRC_32_Tbl[(CRC32^((unsigned__int8*)p)[i])&0xff]^(CRC32>>8);
怎么样？简单吧。