打印
[应用相关]

CRC 循环校验码的原理方法

[复制链接]
421|0
手机看帖
扫描二维码
随时随地手机跟帖
跳转到指定楼层
楼主
jf101|  楼主 | 2024-5-24 14:09 | 只看该作者 |只看大图 回帖奖励 |倒序浏览 |阅读模式
CRC算法是以GF(2)(模 2 除法求余数)多项式算术为数学基础的。

我们先看多项式是怎么来的!

假设我们有一段数据需要传输,数据是二进制的 10100111,那么我们以 x 为变量,定义如下的一个多项式:
1x^7 + 0x^6 + 1x^5 + 0x^4 + 0x^3 + 1x^2 +1x^1 + 1x^0
可以看出,数据就是多项式的系数,每个 bit 对应到的是 x 的对应指数项的系数,这个系数非 0 即 1,因此多项式可以简化为:
x^7 + x^5 + x^2+ x + 1
这样是不是就很像我们平时看到的 CRC 校验的多项式了。上面这个是 8bit 的多项式,最高次幂为 7,对应的 16bit 的多项式中,最高次幂就为 15 了。
什么是模 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
总结一下规律可以得出,这种加减法的运算正好等同于我们计算机中的异或运算,数学理论是基础,我们这里可以记住异或运算就好了。
多项式乘法和一般多项式乘法也是一样的,只是在各项相加的时候按模2算术相加进行,例如:
(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

换成除法,我们也可以通过列一下二进制的除法算式来求余数,我们把包含 n 次幂的项省略掉。



上面的除法就是我们用在 CRC 中做运算用的,我们看看 CRC 的逻辑
假如我们需要传输一个长度为 k 位的数据块,它对应的多项式我们称为 M,按照上面图片中的除法运算,我们需要传输的 8bit 数据为:11100110。假设我们传输 MSB,则它对应多项式为 x^7 + x^6 + x^5 + x^2 + x。最后没有常数项 1,因为最后一个 bit 为 0。
这时候,发送信息的一端和接收信息的一端就要约定一个多项式 G。假设按照上图除法中的数据,我们这里使用的就是 CRC-3(一般没有,是为了适合上图的除式),取多项式为x^3 + x + 1,最高次幂为r = 3。
这时候,发送端先在 M 后面添加 r = 3 个 0,标记为 Mx,然后我们使用 Mx 除以 G 将得到一个次数等于或者小于 r - 1 的余数多项式,我们标记为 R 多项式,这个 R 对应的 bit 串就是校验码。
发送端会将原始数据和校验码一起发送出去,接收端则按照同样的方式进行计算余数 R,然后判断和接收到的是否相同来检验传输是否有错误。


细心的你会发现,这里的原理和校验和其实是一样的,差别在于校验和是累加,这里是对一个多项式 G 做除法。
而这个多项式 G 是可以任意定义的,不同的多项式的检验错误的能力是不同的,校验过程中的运算是不同的。
基于此,很多行业形成固定的多项式,一般我们开发时遵循他们就可以了:





使用特权

评论回复
发新帖 我要提问
您需要登录后才可以回帖 登录 | 注册

本版积分规则

190

主题

1334

帖子

2

粉丝