Hamming界

概述

Hamming 界（也称球填充界）是纠错码的理论上界：在 n 位空间中，码字数 2ᵏ 与纠错能力 t 满足 2ᵏ · Σ C(n,i) ≤ 2ⁿ，达到此界的编码称为"完美码"。

$$2^k \cdot \sum_{i=0}^{t} \binom{n}{i} \leq 2^n$$

其中 t = ⌊(d_min - 1)/2⌋ 是纠错能力。

每个码字"覆盖"了所有与它距离不超过 t 的 n 位字符串（共 Σ C(n,i) 个），这些"球"不能重叠。所有码字的球加起来不能超过 n 维空间的总大小 2ⁿ，因此码字数 2ᵏ 有上界。

就像在一个房间里放球——球不能重叠，球越大（纠错能力越强），能放的球就越少。

Hamming(7,4) 码恰好达到了 Hamming 界——是"完美码"（perfect code）：球填充无缝隙。其他已知的完美码包括 (23,12) Golay 码。

Shannon (1949) 在连续信道中使用球填充推导了 Shannon-Hartley 公式。Hamming (1950) 在离散空间中使用了相同的几何直觉推导了 Hamming 界。两者从不同角度揭示了信息传输的几何本质。