纠错编码
概述
纠错编码（Error Correcting Code, ECC）是通过在数据中添加冗余比特，使得接收方能够检测并自动纠正传输或存储中的比特错误的编码技术。
关键内容
从存在性到构造性
- Shannon (1948)：信道编码定理证明了纠错编码的可能性——存在编码方案能在有噪声信道上实现可靠通信。但这是纯粹的存在性证明，没有给出具体构造。
- Hamming (1950)：给出了第一个系统的、可构造的、有精确纠错保证的编码方案。
发展轨迹
| 年份 | 编码方案 | 特点 |
|---|---|---|
| 1950 | Hamming 码 | 单纠错，代数构造 |
| 1949 | Golay 码 | 另一个完美码 (23,12) |
| 1954 | Reed-Muller 码 | 推广 Hamming 码构造 |
| 1960 | BCH 码 | 多纠错，有限域代数 |
| 1960 | Reed-Solomon 码 | 基于有限域多项式，广泛用于 CD/DVD/QR |
| 1967 | 卷积码 + Viterbi | 状态机编码 + 动态规划解码 |
| 1993 | Turbo 码 | 迭代解码，接近 Shannon 极限 |
| 1996 | LDPC 码（复兴） | 稀疏图码，置信传播解码 |
| 2009 | Polar 码 | 第一个可证明达到容量的显式构造 |
基本概念
- 码字（codeword）：合法的编码序列
- 码率 R = k/n：n 位传输中有多少比例是"有用信息"
- 最小距离：编码方案的核心参数，决定纠错能力
- 完美码：达到 Hamming 界的编码
现代应用
- ECC 内存、闪存/SSD、通信协议、CD/DVD、QR 码、深空通信、量子纠错
来源
- raw/books/信息论/04_hamming_1950_error_correcting_codes.md — Hamming (1950) 深度解析