CRC

CRC

CyclicRedundancyCheck

常用多项式

$$
CRC4=x^4+x+1
$$

$$
CRC8=x^8+x^5+x^4+1
$$

$$
CRC12=x^{12}+x^{11}+x^{3}+x^{2}+1
$$

$$
CRC16=x^{16}+x^{15}+x^2+1
$$

$$
CRC-CCITT=x^{16}+x^{12}+x^5+1
$$

$$
CRC32=x^{32}+x^{26}+x^{23}+x^{22}+x^{16}+x^{12}+x^{11}+x^{10}+x^8+x^7+x^5+x^4+x^2+x^1+1
$$

CRC4 = 0b10011
CRC8 = 0b100110001
CRC12= 0b1100000001101
CRC16= 0b11000000000000101
CRC_CCITT= 0b10001000000100001
CRC32= 0b100000100110000010001110110110111

步骤

选择除数与阶数

选择除数G

选择阶数r

M'后附加r个0

M'是待处理数据块

假设原始数据块的长度是l位的话，附加之后的长度就变成l+r位了，我们用M来代表附加后的值。

M = M' << r

除法

G除M，直到余数Y的阶数r'小于等于r-1

Y = bindiv(M, G)

具体除法例子可以看老师PPT或者Wiki

校验

#binsub代表模2减法
M'' = binsub(M, Y)

似乎 模2加法=模2减法=异或

总结

$$
M(x)·x^n=Q(x)·K(x)-R(x)
$$

其中，M(x)就是原始信息数据，乘以x^n即在后面添加n个0

R(x)即校验码，是余数

K(x)是“钥匙”，即作为除数的多项式

所以有
$$
M(x)·x^n+R(x)=Q(x)·K(x)
$$
即在数据正确的情况下，左侧多项式能够被K(x)整除

参考

https://en.wikipedia.org/wiki/Computation_of_cyclic_redundancy_checks

CRC32查表法 - 孜求嵌道 - 博客园 (cnblogs.com)

https://zh.wikipedia.org/wiki/%E5%BE%AA%E7%92%B0%E5%86%97%E9%A4%98%E6%A0%A1%E9%A9%97

• 本文作者： Taardis
• 本文链接： https://taardisaa.github.io/2022/03/17/CRC/
• 版权声明： 本博客所有文章除特别声明外，均采用 Apache License 2.0 许可协议。转载请注明出处！