奇偶校验（Parity Check）

基本原理

在原始数据后面附加1 位校验位，使得整个码字中"1"的个数满足约定的奇偶性。

• 偶校验：加上校验位后，"1"的总数为偶数
• 奇校验：加上校验位后，"1"的总数为奇数

示例

原始数据1011001，其中"1"的个数为 4（偶数）。

• 偶校验：校验位 =0，码字 =10110010（1 的个数仍为 4）
• 奇校验：校验位 =1，码字 =10110011（1 的个数变为 5）

检错能力

• 能检测1 位错误
• 不能纠错
• 偶数个比特同时出错时无法检测（例如 2 位翻转，奇偶性不变）

优缺点

典型应用

ASCII 字符传输、简单的串口通信、内存的早期检错。

循环冗余校验码（CRC，Cyclic Redundancy Check）

基本原理

将待发送的数据看作一个多项式，用一个预定义的生成多项式 G(x)做模 2 除法，得到的余数就是校验码（FCS，帧检验序列），附加在数据后面发送。

计算步骤

1. 将数据位表示为多项式 M(x)
2. 在 M(x) 后面补 r 个 0（r = 生成多项式的阶数），阶数就是最高次幂
3. 用生成多项式 G(x) 对补零后的数据做模 2 除法
4. 得到的 r 位余数即为 CRC 校验码
5. 将余数附加到原始数据后发送

示例（简化）

• 数据：110101
• 生成多项式 G(x) = x³ + x + 1，对应二进制1011（阶数 r = 3）
• 数据补 3 个 0：110101000
• 模 2 除法求余数，得到 3 位校验码，附加后发送

模 2 除法的特点：减法等同于异或（XOR），没有进位和借位。

检错能力

CRC 的检错能力取决于生成多项式的选择：

• 能检测所有奇数个比特错误（若 G(x) 含有因子 x+1）
• 能检测所有突发长度 ≤ r的错误（r 为校验位长度）
• 对突发长度 > r 的错误，漏检概率极低（约为 2⁻ʳ）
• 不能纠错（标准 CRC 只用于检错）

常见标准

优缺点

典型应用

以太网帧校验（FCS）、磁盘存储、ZIP/RAR 文件校验、通信协议（HDLC、PPP）。

海明码（Hamming Code）

基本原理

海明码是一种既能检错又能纠错的线性分组码。通过在数据位中插入多个校验位，使得每个校验位覆盖不同的数据位组合，从而在接收端定位并纠正错误。

核心思想

• 校验位放在码字中2 的幂次位置（第 1、2、4、8、16… 位）
• 每个校验位负责校验一组特定的位（由其位置的二进制表示决定）
• 接收端计算校正子（Syndrome），其值直接指向出错位的位置

编码步骤（以海明(7,4)码为例）

原始数据 4 位：D₃D₂D₁D₀，需插入 3 个校验位 P₁P₂P₃，组成 7 位码字。

位位置安排：

校验关系（偶校验）：

• P₁ 覆盖位置 1,3,5,7（二进制末位为 1 的位置）
• P₂ 覆盖位置 2,3,6,7（二进制倒数第二位为 1 的位置）
• P₃ 覆盖位置 4,5,6,7（二进制倒数第三位为 1 的位置）

纠错过程

接收端重新计算各校验组的奇偶性，得到校正子 S = S₃S₂S₁：

• S = 000 → 无错
• S ≠ 000 → S 的值就是出错位的位号，翻转该位即可纠正

检错与纠错能力

• 标准海明码：纠正 1 位错误，检测 2 位错误（但不能同时纠正 1 位又检测 2 位）
• 扩展海明码（加一位总校验位）：纠正 1 位错误 + 检测 2 位错误（SECDED）

码率与效率

海明码需满足关系：

2ʳ ≥ m + r + 1

其中 m 为数据位数，r 为校验位数。

优缺点

典型应用

计算机内存 ECC（SECDED 就是扩展海明码）、深空通信、RAID 存储系统。

三者对比总结

简单来说：奇偶校验最简单但最弱；CRC检错能力最强但只检不纠；海明码是唯一能自动纠错的方案，代价是校验位开销更大。