汉明码
汉明码（Hamming Codes）是一种能够纠正单比特错误的线性分组码，由 Richard Hamming于 1950年在贝尔实验室提出。Hamming在早期计算机 MARK I的运行中发现，程序因单比特错误而崩溃后需要人工干预才能恢复，这促使他设计了第一种实用的纠错码。对于任意正整数 ，存在一个 的汉明码，其中 n为码长，k为信息位长度，r为校验位长度。最经典的汉明码是 (7, 4)码，即码长 7位中包含 4位信息和 3位校验位。
汉明码的校验矩阵 H 的列由所有非零的 r 维二元向量构成，共有 2^r - 1 列，各列互不相同且都不为零。对于 (7, 4) 汉明码，校验矩阵 H 为 3 x 7 矩阵，其列向量为 1 到 7 的二进制表示：
汉明码的最小汉明距离为 3。这一结论可由校验矩阵的结构严格证明：由于 H 的各列互不相同且非零，任意两列之和不可能为零向量（否则两列相等），因此任何非零码字至少包含 3 个非零分量。理由如下——重量为 1 的向量不可能是码字，因为 H 乘以该向量得到的等于 H 的某一列，非零；重量为 2 的向量也不可能是码字，因为 H 乘以该向量等于两列之和，非零；因此最小重量至少为 3，即 d_min = 3。根据纠错能力公式，最小距离为 3 的码可以纠正所有单比特错误，这正是汉明码的设计目标。
汉明码的译码过程非常高效。接收端计算伴随式 s = H y^T，若 s = 0 则直接输出接收向量作为译码结果；若 s != 0，则 s 恰好是 H 中错误位置对应的列向量，将该位取反即可完成纠错。这种译码方式在硬件实现中极为简单，仅需异或门和查找表即可实现。扩展汉明码通过在 (n, k) 汉明码的基础上增加一个全局校验位（对所有位进行偶校验），将码长扩展为 (2^r, 2^r - 1 - r)，最小距离提升至 4，从而能够同时检测双比特错误并纠正单比特错误。汉明码广泛应用于计算机内存纠错（如 ECC 内存）和通信系统中的前向纠错，是编码理论中最基本且最实用的码之一。
链接到
- 上一个知识点：8.4 伴随式
- 下一个知识点：无（本章最后一个知识点）