CRC基本原理和计算方式

循环冗余校验码(CRC) 是在数字数据的生成、传输、处理或存储过程中用于错误检测的最广泛使用的代码之一。简单来说，CRC 码在传输、处理和数据静止期间保持数据的完整性。为了使用 CRC 进行错误检测，输入流除以标准多项式，称为特定 CRC 标准的“生成多项式”。此除法过程中的余数称为输入数据的 CRC 码。在传输或存储数据之前，该剩余部分与原始数据相连。在接收器处，传输的数据（原始数据及其 CRC）再次除以相同的生成多项式。如果在传输或存储期间没有引入错误，则该除法的余数应为零。循环冗余码最常用于检测突发错误。CRC 经常使用，因为它们易于设计并且能够检测大量错误。特定 CRC 代码能够检测到的错误类型取决于其生成多项式 。可以使用循环冗余校验码检测以下类型的错误：所有单位或两位错误。所有奇数位错误。所有突发错误，其中突发大小小于或等于生成多项式的次数。

CRC 数学原理

宏观的角度看一下校验过程，如下图所示，带有CRC校验的数据格式为数据+添加项，我们把发送的总数据位记作N，消息位（Message bits）记作k，添加项位数（Appended bits）记作n，即N-k=n，也就是常说的二进制 (N, k) CRC 码。

若用多项式表示，如下：

根据上面描述的CRC code bits 的计算方式，消息位（Message bits）也就是你要发的实际数据位是已知的，所需要计算的就是添加项（即多项式R（x）），这就需要n阶生成多项式g（x）（用二进制表示是n+1位）

将除以 g(X)（模 2 除法）得到余数，即 R(X)，注意R（x）是n-1阶，用二进制表示是n位数据。之所以要把m（x）乘以X的n阶，是为了把要发的数据向左移n位，给计算的添加项“挪位置”。因为本身的n位二进制添加项是要加到消息（Message）后面的。

计算R（X）举例：

那么，，添加项为0110（n=4），即发送的数据为：111001100110

校验正确举例：

接收码字的多项式 T(X) 除以生成多项式 g(X)

设 接收端接收到的带CRC的据111001100110

即T（X）除以g（x）余项为0，所以校验正确

校验错误举例

传输的带有CRC校验的数据：111001100110

接收的带有CRC校验的数据：110011100110

可得余项为x，即添加项为0010不为0000，校验出错，证明接收的数据有误。

CRC (7, 4) 的向量形式示例1

注：Divisor是n阶g（x）的二进制表示，二进制位数为n+1位，remainder是n-1阶R（x），二进制为n位，在接收到带有CRC校验的数据时，计算出的syndrome不为0，即出现错误。下面的例子有按照多项式的计算也有二进制的计算。

CRC (7, 4) 的向量形式示例2

CRC (7, 4) 的向量形式示例3

CRC (7, 4) 的向量形式示例4

常见CRC

总结：本文主要使用简单的CRC来讲解基础的原理，各种生成项的行列式校验能力是不一样的，用的场合也不同，根据需求选择。

参考文献：ELEC 7073 Digital Communications III, Dept. of E.E.E., HKU