循环冗余校验码（Cyclic Redundancy Check，CRC）是一种广泛应用于数据通信和存储领域的错误检测编码方法。它利用多项式除法的原理，通过对发送的数据进行特定的数学运算，生成一个固定长度的校验码。接收方可以使用相同的算法对收到的数据进行校验，以检测在传输过程中是否发生了错误。

---

一、CRC的基本概念

1. 数据的多项式表示

在CRC中，数据被视为二进制多项式。例如，一个8位的数据字节 $D=d_7{d}_6{d}_5{d}_4{d}_3{d}_2{d}_1{d}_0$​可以表示为多项式：
$$D(x)=d_7{x}^7+d_6{x}^6+d_5{x}^5+d_4{x}^4+d_3{x}^3+d_2{x}^2+d_{1}x+d_0$$
其中，$d_i$ 是二进制位（0或1），$x$是形式变量。

2. 生成多项式（$G(x)$）

CRC算法使用一个预先定义的生成多项式 $G(x)$，这是一个固定的多项式，用于确定校验码的计算方式。生成多项式的最高次项和最低次项系数均为1。例如，常用的生成多项式有：

• CRC-8：$G(x)=x^8+x^2+x+1$
• CRC-16：$G(x)=x^{16}+x^{15}+x^2+1$
• CRC-32：$G(x)=x^{32}+x^{26}+x^{23}+\dots +x+1$

---

二、CRC的编码过程

CRC编码的核心是对数据多项式进行模 $G(x)$ 的除法，求得余数作为校验码。

步骤1：数据多项式的扩展

将原始数据多项式 $D(x)$ 乘以 $x^n$，其中 $n$ 是生成多项式 $G(x)$ 的阶数（最高次项的指数）。这相当于在数据后面附加 $n$​个零位。
$$D^{\prime }(x)=D(x)\times x^n$$

步骤2：计算余数多项式

对扩展后的数据多项式 $D^{\prime }(x)$ 进行模 $G(x)$ 的除法，得到余数多项式 $R(x)$​：
$$R(x)=D^{\prime }(x)\mathrm{mod}G(x)$$

步骤3：生成码字

将余数 $R(x)$ 添加到扩展后的数据多项式 $D^{\prime }(x)$中，形成最终的CRC码字 $T(x)$：
$$T(x)=D^{\prime }(x)+R(x)$$
在二进制域上，加法等同于异或操作。因此，$T(x)$实际上是在原始数据后附加了校验码 $R(x)$。

---

三、CRC的解码和错误检测

接收方在收到码字 $T^{\prime }(x)$ 后，需要验证数据的完整性。

步骤1：校验

对接收到的码字 $T^{\prime }(x)$ 进行模 $G(x)$的除法，计算得到余数 $R^{\prime }(x)$：

$R^{\prime }(x)=T^{\prime }(x)\mathrm{mod}G(x)$

步骤2：判断

• 如果 $R^{\prime }(x)=0$，则认为数据未发生错误。
• 如果 $R^{\prime }(x)\ne 0$，则检测到错误。

CRC只能检测错误，不能纠正错误。

---

四、CRC的错误检测能力

CRC的错误检测能力取决于生成多项式 $G(x)$的选择。一般来说，CRC可以检测：

• 所有单比特错误。
• 所有双比特错误，前提是 $G(x)$ 的最小因子包含至少三个不同的因子。
• 所有奇数位错误，如果 $G(x)$ 包含$(x+1)$因子。
• 长度小于等于 $n$ 的突发错误，其中 $n$ 是 $G(x)$ 的阶数。

---

五、生成多项式的选择

选择合适的生成多项式对于CRC的性能至关重要。以下是常用的生成多项式及其特性：

1. CRC-8

• 多项式：$G(x)=x^8+x^2+x+1$
• 应用：ATM头部错误控制、标准字节校验。

2. CRC-16

• 多项式：$G(x)=x^{16}+x^{15}+x^2+1$
• 应用：USB、XMODEM协议、IBM SDLC。

3. CRC-32

• 多项式：$G(x)=x^{32}+x^{26}+x^{23}+\dots +x+1$
• 应用：以太网、ZIP压缩、PNG图像格式。

生成多项式的选择应考虑到所需的错误检测能力和实现复杂度。

---

六、CRC的示例

以CRC-4为例，生成多项式 $G(x)=x^4+x+1$。

编码过程：

1. 原始数据：$D=1101$
2. 扩展数据：$D^{\prime }=11010000$（在数据后添加4个零）
3. 计算余数：对 $D^{\prime }$ 进行模 $G(x)$ 的二进制除法，得到余数 $R=0011$。
4. 生成码字：$T=D+R=11010011$

解码过程：

1. 接收码字：$T^{\prime }=11010011$
2. 校验：对 $T^{\prime }$ 进行模 $G(x)$的二进制除法，若余数为0，则数据正确。

---

七、CRC的优点和局限性

优点：

• 高效的错误检测能力：对突发错误特别敏感。
• 实现简单：可用硬件和软件高效实现。
• 开销低：附加的校验码长度相对较短。

局限性：

• 不能纠正错误：只能检测错误，无法定位或纠正。
• 检测能力有限：对于某些特定的错误模式，可能无法检测。

---

八、应用领域

• 数据通信：网络协议（如以太网、CAN总线）、无线通信。
• 存储设备：硬盘、光盘的数据完整性校验。
• 文件传输：FTP、ZIP压缩文件的完整性验证。

---

九、总结

CRC是一种基于多项式运算的高效错误检测编码方法。通过选择合适的生成多项式，CRC能够以较低的计算和传输开销，实现对数据的有效错误检测。理解CRC的技术原理有助于在实际应用中正确地实现和使用CRC算法，确保数据通信和存储的可靠性。

附录：模 2 运算（Modulo-2 Arithmetic）

模 2 运算（Modulo-2 Arithmetic） 是一种特殊的二进制运算规则，主要用于二进制数的计算中，比如 CRC 校验、编码理论和通信系统中常见的误差检测。

模 2 运算的特点是：

1. 加法与减法等价：在模 2 运算中，加法和减法是等价的，都是使用异或运算（XOR）。这是因为二进制的加法和减法在模 2 下遵循相同的规则：

   • $0\oplus 0=0$
   • $1\oplus 1=0$
   • $0\oplus 1=1$
   • $1\oplus 0=1$

   这种运算特性使得模 2 下的加法不需要进位，也没有负数的概念。

2. 模 2 运算的乘法：模 2 下的乘法就是常规的二进制乘法，但结果只会是 0 或 1，没有进位问题：

   • $0\times 0=0$
   • $1\times 0=0$
   • $0\times 1=0$
   • $1\times 1=1$

模 2 运算的应用

在很多应用中，例如 CRC 校验，模 2 运算用于二进制除法。不同于我们通常理解的除法，这里主要使用 异或 运算替代常规的减法操作。

模 2 运算的例子

假设我们有两个二进制数 $A=1101$ 和$B=1011$，我们进行模 2 运算：

• $A\oplus B=1101\oplus 1011=0110$

这里的每一位都是进行模 2 下的异或运算，因此：

• 第一位：$1\oplus 1=0$
• 第二位：$1\oplus 0=1$
• 第三位：$0\oplus 1=1$
• 第四位：$1\oplus 1=0$

最终结果是 0110。

总结

• 模 2 运算 是二进制中的一种运算规则，主要使用异或（XOR）操作代替加法和减法，且没有进位。
• 模 2 乘法 是普通的二进制乘法，没有进位或更高的数位。

模 2 运算特别适合应用于数字通信中的错误检测、编码理论等领域，因为它能有效简化二进制数据的处理。