crc校验码计算方法是什么

1、循环校验码（CRC码）：是数据通信领域中最常用的一种差错校验码，其特征是信息字段和校验字段的长度可以任意选定。

2、生成CRC码的基本原理：任意一个由二进制位串组成的代码都可以和一个系数仅为‘0’和‘1’取值的多项式一一对应。

例如：代码1010111对应的多项式为x6+x4+x2+x+1，而多项式为x5+x3+x2+x+1对应的代码101111。

扩展资料：

注意事项

是接受方和发送方的一个约定，也就是一个二进制数，在整个传输过程中，这个数始终保持不变。

在发送方，利用生成多项式对信息多项式做模2除生成校验码。在接收方利用生成多项式对收到的编码多项式做模2除检测和确定错误位置。

应满足以下条件：

1、生成多项式的最高位和最低位必须为1。

2、当被传送信息（CRC码）任何一位发生错误时，被生成多项式做除后应该使余数不为0。

3、不同位发生错误时，应该使余数不同。

4、对余数继续做除，应使余数循环。

就是相加后取被二除的余数。通常用于计算机和电子领域。如果两个加数是二进制数（通常都是），且不计进位，相当于按位取异或。

规则：

1+1=0+0=0

1+0=0+1=1

分析：问题特殊化

1、只有一堆时，即状况为（a , 0 , 0）,此时先抓者必胜

2、只有两堆时，即状况为（a , b , 0）

（1）若b = a , 即状况为（a , a , 0）,此时后抓者必胜。因为

对方先抓后，结果或剩一堆，成为（a , 0 , 0）的状况，

一把可抓完；或剩两堆，你抓后，又成为新的（d , d , 0）

的状况，且d < a , 继续由对方抓。

（2）若b ≠ a ,不妨设b > a ,即状况为（a , b , 0）, 此时先抓

者必胜。因为先抓者可以把第二堆抓掉b – a个，使状况

转化为（a , a , 0）, 成为新的“状况（1）”。

3、三堆都有，且其中两堆相等，即状况为

（a , a , c）,此时先抓者必胜。因为先抓者可以把

第三堆全抓完，使状况转化为（a , a , 0）,成为新

的“状况 2)（1）”。

4、三堆都有，且其中任意两堆都不相等，即状况为（a , b , c）, 且不妨设a < b < c ,此时情况比较复杂。

为了下面表述得清楚，我们把前面的一个结论用“反面说法”，总结为

“把两堆相等的状况留给对方，自己可以取胜。”

然后再讨论 a、b、c 的不同情况。以其中最小的a为“主要线索”分情况讨论。

（1）a ＝ 1 时，即状况为（1 , b , c）。

下面再对 b 分情况讨论。

（2）a ＝ 2 时，即状况为（2 , b , c）。

下面再对 b 分情况讨论。

（3）a ＝ 3 时，即状况为（3 , b , c）。

下面再对 b 分情况讨论。

（4）a ＝ 4 时，即状况为（4 , b , c）。

下面再对 b 分情况讨论。

然后再讨论 a、b、c 的不同情况。以其中最小的a为“主要线索”分情况讨论。

（1）a ＝ 1 时，即状况为（1 , b , c）。

下面再对 b 分情况讨论。

（2）a ＝ 2 时，即状况为（2 , b , c）。

下面再对 b 分情况讨论。

（3）a ＝ 3 时，即状况为（3 , b , c）。

下面再对 b 分情况讨论。

（4）a ＝ 4 时，即状况为（4 , b , c）。

下面再对 b 分情况讨论。

（1）a ＝ 1 时，即状况为（1 , b , c）。下面再对 b 分情况。

由于a < b < c ,即 a、b、c “前小后大”，因此 b最小为2，于是起始情况是（1 , 2 , 3）。经用“穷举法”分析，该情况下后抓者胜；或用“反面说法”说成，“把（1 , 2 , 3）的状况留给对方，自己可以取胜”。

下一个情况是（1 , 2 , c）, c > 3 。此时必先抓者胜。因为先抓者只要把第三堆抓剩3个，就转化成（1 , 2 , 3）的状况，从而必胜。

下一个情况是（1 , 3 , c）, c > 3。此时必先抓者胜。因为先抓者只要把第三堆抓剩2个，就转化成（1, 3 , 2）的状况，也即（1, 2 , 3）的状况，从而必胜。

下一个情况是（1 , 4 , c）, c > 4。起始情况是（1 , 4 , 5）。经用“穷举法”分析，该情况下后抓者胜；或用“反面说法”说成，

“把（1 , 4 , 5）的状况留给对方，自己可以取胜”。

这样类似地分析下去，逐渐可以得到结论：

把（1 , 2 , 3）的状况留给对方，自己可以取胜。

把（1 , 4 , 5）的状况留给对方，自己可以取胜。

把（1 , 6 , 7）的状况留给对方，自己可以取胜。

把（1 , 8 , 9）的状况留给对方，自己可以取胜。

这样类似地分析下去，逐渐可以得到结论：

把（1 , 2 , 3）的状况留给对方，自己可以取胜。

把（1 , 4 , 5）的状况留给对方，自己可以取胜。

把（1 , 6 , 7）的状况留给对方，自己可以取胜。

把（1 , 8 , 9）的状况留给对方，自己可以取胜。

于是归纳、抽象、猜测：把（1 , 2m , 2m+1）的状况留给对方，自己可以取胜。

然后用数学归纳法可以证明，这一结论是正确的。自己证明

这样，就把 a ＝ 1 时的情况，全搞清楚了。

（2）a ＝ 2 时，即状况为（2 , b , c）。

下面再对 b 分情况。

由于a < b < c , 即a、b、c “前小后大”，因此 b最小为3，于是起始情况是（2 , 3 , c）。c > 3。

此时必先抓者胜。因为先抓者只要把第三堆抓剩1个，就转化成（2 , 3 , 1）的状况，也即（1 , 2 , 3）的状况，从而必胜。

下一个情况是（2 , 4 , c）, c > 4。起始情况是（2 , 4 , 5）。此时必先抓者胜。因为先抓者只要

把第一堆抓剩1个，就转化成（1 , 4 , 5）的状况，从而必胜。

下一个情况是（2 , 4 , 6）。经用“穷举法”分析，该情况下后抓者胜；或用“反面说法”说成，“把（2 , 4 , 6）的状况留给对方，自己可以 取胜”。

这样类似地分析下去，逐渐可以得到结论：

把（2 , 4 , 6）的状况留给对方，自己可以取胜。

把（2 , 5 , 7）的状况留给对方，自己可以取胜。

把（2 , 8 , 10）的状况留给对方，自己可以取胜。

把（2 , 9 , 11）的状况留给对方，自己可以取胜。

于是归纳、猜测：把（2 , 4m , 4m+2）或（2 , 4m+1 , 4m+3）的状况留给对方，自己可以取胜。然后用数学归纳法可以证明，这一结论是正确的。

这样，就把a = 2 时的情况，全搞清楚了。

（3）a ＝ 3 时，即状况为（3 , b , c）。

下面再对b分情况。类似地分析下去，逐渐可以得到结论：

把（3 , 4 , 7）的状况留给对方，自己可以取胜。

把（3 , 5 , 6）的状况留给对方，自己可以取胜。

把（3 , 8 , 11）的状况留给对方，自己可以取胜。

把（3 , 9 , 10）的状况留给对方，自己可以取胜。

于是归纳、猜测：

把（3 , 4m , 4m+3）或（3 , 4m+1 , 4m+2）的状况留给对方，自己可以取胜。然后用数学归纳法可以证明，这一结论是正确的。这样，就把a = 3 时的情况，全搞清楚了。

为了赢律更大，还需研究 a =4 时的情况，a = 5 时的情况

例如a ＝ 4 时的情况，经过研究可以得到结论：

把（4 , 8 , 12）的状况留给对方，自己可以取胜。

把（4 , 9 , 13）的状况留给对方，自己可以取胜。

把（4 , 10 , 14）的状况留给对方，自己可以取胜。

把（4 , 11 , 15）的状况留给对方，自己可以取胜。

把（4 , 16 , 20）的状况留给对方，自己可以取胜。

把（4 , 17 , 21）的状况留给对方，自己可以取胜。

把（4 , 18 , 22）的状况留给对方，自己可以取胜。

把（4 , 19 , 23）的状况留给对方，自己可以取胜。

于是归纳、猜测：

把（4 , 8m , 8m+4）或（4 , 8m+1 , 8m+5）或（4 , 8m+2 , 8m+6）或（4 , 8m+3 , 8m+7）的状况留给对方，自己可以取胜。

然后用数学归纳法可以证明，这一结论是正确的。

这样，用“数列通项公式”的方法，继续研究

下去，也能得出取胜的策略，但表达起来会很繁琐。

因为已经看到，在（a , b , c），a < b < c的

规定下，

a ＝ 1 时，有一种表达式（1 , 2m , 2m+1）的状况留给对方，自己可以取胜。

a ＝ 2 时，有二种表达式（2 , 4m , 4m+2）或（2 , 4m+1 , 4m+3）的状况留给对方，自己可以取胜。

a = 3 时，有二种表达式（3 , 4m 4m+3）或（3 , 4m+1 , 4m+2）的状况留给对方，自己可以取胜。

a = 4 时，有四种表达式（4 , 8m , 8m+4）或（4 , 8m+1 , 8m+5）或（4 , 8m+2 , 8m+6）或

（4 , 8m+3 , 8m+7）的状况留给对方，自己可以 取胜。

可以猜测，a ＝ 4、5、6、7这四种情况时，都分别有四种通项表达式的状况留给对方，自己可以取胜。

a ＝8、9、10、11、12、13、14、15这八种情况时，都分别有八种通项表达式的状况留给对方，自己可以取胜。

…………

a ＝ 2k ，2k+1，2k +2，…，2k+1-1 ，这 2k种情况时，都分别有 2k种通项表达式的状况留给对方，自己可以取胜。

“抓三堆”的二进制解法

用二进制表示这三堆谷粒数，写成三行，并上下对齐，各列相加，列的加法定义为0+0=0；0+1=1；1+0=1；1+1=1

这就是模2加法。（只要是有2的倍数，就都可以作为0）

关于模2加法，可以推广；比如推广为模7加法：

例1：如果1号是星期一，问 27号是星期几？

解答：27号与1号相差26天，因为 26=73+5 ，说明过去3个7天之后，再过5 天，这样27号这天就是星期一再加上5天，即星期六。（事实上，这里只要是有7的倍数，就都可以作为0。）

例2：如果1号是星期三，问 27号是星期几？（答：星期一）

我们断言：把三堆谷粒数均表为二进制，写成三行，将位数对齐，各列“模2相加”，若各列的和全为0，则后抓者有必胜策略； 若和中出现1，则先抓者有必胜策略。

和中出现1时，先抓者的具体策略是：先抓者从最左边的1所在的列，寻找某堆的谷粒数中相应的列也有1，就从该堆中抓走适当个数，使得抓完后各列的和（模2）为0。

一、由于谷粒数越来越少，最后，先抓者可以使得后抓者始终面临各列模2之和为（0，0，…，0）状态，这意味着先抓者获胜。

二、后抓者只要抓，谷粒就将减少，因此该行中至少有一个1变为0（如果1都不变为0，只会使谷粒数增加或不变），从而该列模2之和将为1。于是先抓者就不会面临（0，0，…， 0）状态。

三、先抓者的正确抓法，应使得各列模2之和均为0。即，先抓者应总是抓成（0，0，…， 0）状态。

例1：设原始状态（2，3，4），则先抓者胜。

例2：设原始状态（5，8，13），则后抓者胜。

例3：设原始状态（5，12，13），则先抓者胜。

CRC码是由两部分组成，前部分是信息码，就是需要校验的信息，后部分是校验码，如果CRC码共长n个bit，信息码长k个bit，就称为(n,k)码。

它的编码规则是：

1、首先将原信息码(kbit)左移r位(k+r=n)

2、运用一个生成多项式g(x)（也可看成二进制数）用模2除上面的式子，得到的余数就是校验码。

非常简单，要说明的：模2除就是在除的过程中用模2加，模2加实际上就是我们熟悉的异或运算，就是加法不考虑进位，公式是：

0+0=1+1=0,1+0=0+1=1

即‘异’则真，‘非异’则假。

由此得到定理：a+b+b=a

也就是‘模2减’和‘模2加’直值表完全相同。

有了加减法就可以用来定义模2除法，于是就可以用生成多项式g(x)生成CRC校验码。

计算过程如下：

采用CRC校验方法，生成多项式为X4+X3+1，则对应的代码为11001，则冗余位为4位，则被除数为101100110000，除数为11001，进行模2除法示余式

11010100

11001

101100110000

11001

11110

11001

11111

11001

11000

11001

0100

则实际发送的二进制数据为101100110100

分类: 电脑/网络 >> 程序设计 >> 其他编程语言

问题描述:

最好有例子的

解析:

CRC（Cyclic Redundancy Check)循环冗余校验码

是常用的校验码，在早期的通信中运用广泛，因为早期的通信技术不够可靠（不可靠性的来源是通信技术决定的，比如电磁波通信时受雷电等因素的影响），不可靠的通信就会带来‘确认信息’的困惑，书上提到红军和蓝军通信联合进攻山下的敌军的例子，第一天红军发了条信息要蓝军第二天一起进攻，蓝军收到之后，发一条确认信息，但是蓝军担心的是‘确认信息’如果也不可靠而没有成功到达红军那里，那自己不是很危险？于是红军再发一条‘对确认的确认信息’，但同样的问题还是不能解决，红军仍然不敢冒然行动。

对通信的可靠性检查就需要‘校验’，校验是从数据本身进行检查，它依靠某种数学上约定的形式进行检查，校验的结果是可靠或不可靠，如果可靠就对数据进行处理，如果不可靠，就丢弃重发或者进行修复。

CRC码是由两部分组成，前部分是信息码，就是需要校验的信息，后部分是校验码，如果CRC码共长n个bit，信息码长k个bit，就称为(n,k)码。 它的编码规则是：

1、首先将原信息码(kbit)左移r位(k+r=n)

2、运用一个生成多项式g(x)（也可看成二进制数）用模2除上面的式子，得到的余数就是校验码。

非常简单，要说明的：模2除就是在除的过程中用模2加，模2加实际上就是我们熟悉的异或运算，就是加法不考虑进位，公式是：

0+0=1+1=0,1+0=0+1=1

即‘异’则真，‘非异’则假。

由此得到定理：a+b+b=a 也就是‘模2减’和‘模2加’直值表完全相同。

有了加减法就可以用来定义模2除法，于是就可以用生成多项式g(x)生成CRC校验码。

例如： g(x)=x4+x3+x2+1,(7,3)码,信息码110产生的CRC码就是：

101

11101 | 110,0000

111 01

1 0100

1 1101

1001

余数是1001，所以CRC码是110,1001

标准的CRC码是，CRC-CCITT和CRC-16，它们的生成多项式是：

CRC-CCITT=x16+x12+x5+1

CRC-16=x16+x15+x2+1

以上就是关于crc校验码计算方法是什么全部的内容，包括:crc校验码计算方法是什么、两个相同矩阵模2相加什么意思、抓三堆谷粒的数学问题,用二进制方法!求高手解答等相关内容解答，如果想了解更多相关内容，可以关注我们，你们的支持是我们更新的动力！