Hamming 界

Hamming 界用球打包计数限制码字数量：若要纠正 $t$ 个错误，每个码字必须拥有一块不会与其他码字混淆的接收空间，即周围半径 $t$ 的 Hamming 球必须互不相交，否则同一接收词会落入两个码字的保证解码区。所有球占用的空间不能超过整个字母串空间，因此得到码率、块长与距离之间的上界。它是必要条件，不保证满足不等式的参数一定有相应码。

二元 $[7,4,3]$ Hamming 码有 16 个码字，半径 1 球大小 $1+7=8$，乘积为 128，恰好填满 $2^7$，故是完美码。界是必要条件，不保证满足参数的码一定存在；列表译码理路列表译码List decoding允许每个接收词对应一个受控候选列表，从而在组合意义上越过唯一译码半径。允许一个较大球包含至多 $L$ 个候选，已不再使用唯一译码的球不交模型。

二元长度 $n$、码字数 $M$、纠正 $t$ 错的码满足

例如 $n=3,t=1$ 时每个球大小为 $1+3=4$，故 $M\le 2$；重复码 $\{000,111\}$ 恰达到等号，是完美码。

球半径应取可保证纠正的 $t=\lfloor (d-1)/2\rfloor$，不是直接取最小距离 $d$。非二元码需把球体积改为 $\sum _i(\genfrac{}{}{0ex}{}{n}{i})(q-1{)}^i$；非对称信道或软判决也未必适用这种 Hamming 几何与球不交模型。

Hamming 界用于排除不可能码参数、定义完美码并比较编码构造效率。Hamming 距离理路Hamming 距离Hamming distance等长字中不同坐标的数量；由逐位比较、三角不等式和 Hamming 球解释检错与唯一纠错半径。定义球，信道码理路信道码Channel code把消息映为信道输入码字并从带噪输出恢复消息的编码—译码对。提供码字集合；本页与Singleton 上界理路Singleton 界Singleton bound通过删去最小距离减一个坐标，给出码字数、块长与距离之间的普适上界。方向相同但证明几何不同，Gilbert–Varshamov 界理路Gilbert–Varshamov 界Gilbert–Varshamov bound · GV bound由极大码的覆盖性质证明具有给定最小距离的大码存在，并导出渐近可达率下界。则是码大小的存在下界。线性码理路线性码Linear code有限域向量空间中的线性子空间作为码字集合的信道码。达到 Hamming 界等号时对应具有整齐综合结构的完美码。