8.3 汉明距离

汉明距离

汉明距离（Hamming Distance）是编码理论中最基本的概念之一，用于衡量两个等长码字之间的差异程度。对于两个长度均为 n 的码字 x = (x_1, x_2, …, x_n) 和 y = (y_1, y_2, …, y_n)，汉明距离定义为它们对应位置上不同符号的个数，记作 d(x, y)。数学表达式为：

$$d(x,y)=\sum _{i=1}^n{1}_{x_i\ne y_i}$$

其中 1为指示函数，当 $x_i!=y_i$时取 1，否则取 0。汉明距离满足距离度量的三条基本公理：非负性（$d(x,y)\ge 0$，当且仅当 $x=y$时取等）、对称性（$d(x,y)=d(y,x)$）和三角不等式（$d(x,z)\le d(x,y)+d(y,z)$）。此外，两个码字的汉明距离等于它们模 2和的汉明重量（Hamming Weight），即 $d(x,y)=w(x+y)$，其中汉明重量 $w(x)$定义为向量 x中非零分量的个数。

在线性分组码中，汉明距离具有特殊的结构意义。由于线性码是向量空间中的子空间，任意两个码字的和仍然是码字，因此码的最小汉明距离 d_min 等于非零码字的最小汉明重量。这一性质使得线性码的最小距离分析简化为对码字重量的分析，无需逐一计算所有码字对之间的距离。最小汉明距离直接决定了码的检错和纠错能力：

$$\text{可检测错误位数}\le d_{\min }-1,\text{可纠正错误位数}\le \lfloor \frac{d_{\min }-1}{2}\rfloor$$

对于给定的码参数 (n, k)，最小汉明距离的上界由各种界约束，如汉明界（Hamming Bound，又称球包界）和普洛特金界（Plotkin Bound）。汉明界指出，若要纠正 t 位错误，必须以码字为中心、半径为 t 的球互不相交，从而有：

$$2^k\cdot \sum _{i=0}^t\left(\genfrac{}{}{0ex}{}{n}{i}\right)\le 2^n$$

等号成立时称为完美码（Perfect Code），汉明码即为完美码的一个经典例子——当 t = 1 时，(2^r - 1, 2^r - 1 - r) 汉明码恰好填满整个空间，每个码字周围的半径为 1 的球互不相交且覆盖所有可能的接收向量。

链接到

• 上一个知识点：8.2 GF2域零空间
• 下一个知识点：8.4 伴随式