标签 算法 下的文章

循环冗余校验(CRC)算法入门

CRC 算法原理

CRC 算法的基本原理是将数据看作一个大数,与一个预定义的除数使用特殊的除法相除,所得的余数即为数据的 CRC 校验值。

生成多项式

算法的数学原理与多项式相关,用到的除法也基于多项式除法,预定义的除数也叫“生成多项式”,这里的多项式都是只有一个未知数并且各项系数只能是 0 或 1 的多项式(更多的信息可以参考维基百科:有限域算术,这里不多讲)。

我们以 CRC-4/ITU 为例,其生成多项式是 $x^4 + x + 1$,也即:

$$1x^4 + 0x^3 + 0x^2 + 1x^1 + 1x^0$$

如果我们令 $x = 2$,则多项式中每一项的系数可以看作一个二进制数的对应位,即 $(10011)_2$,是一个 5 位的二进制数,那么用它来做除数,最后可以得到 4 位的余数,也就是 CRC-4/ITU 中的 4。由此可见,生成多项式的首位必然是 1,在一般表示生成多项式的时候我们都省略最高位,再写成十六进制就是 0x03

模二多项式除法

我们先看多项式乘法:

$$ (x^4 + x^1 + x^0) \times (x^4 + x^3 + x^0) = x^8 + x^7 + x^4 + x^5 + x^4 + x^1 + x^4 + x^3 + x^0 $$

这里我们没有合并同类项,如果按照常规的方式合并同类项,即

$$ x^8 + x^7 + x^5 + 3x^4 + x^3 + x^1 + x^0 $$

那就是普通的多项式乘法;对于 CRC 算法,加减法采用模二运算,也就是最后的系数除以 2 取余数,不产生进位,所以最后的结果是:

$$ x^8 + x^7 + x^5 + x^4 + x^3 + x^1 + x^0 $$

- 阅读剩余部分 -