Hamming 距离

Hamming 距离只计算等长词在多少个对应坐标上不同，不关心符号之间的数值差，是离散立方体上的度量。对码而言，两个码字距离越大，噪声必须改动更多坐标才能把一个混淆成另一个，因此最小距离直接控制检测与纠错能力。它适合替换错误，却不处理插入或删除。

10110 与 10001 在三个位置不同，距离为 3；另取 10110 与 11100，它们在第 $2$、$4$ 位不同，距离为 $2$。半径 $t$ 的 Hamming 球大小为 $\sum _{i=0}^t(\genfrac{}{}{0ex}{}{n}{i})(q-1{)}^i$。

最小距离 $d=5$ 的码可检测至多 $4$ 个任意错误，并保证纠正至多 $2$ 个错误，因为半径 $2$ 的球互不相交。

不同长度字符串的 Hamming 距离通常未定义或需先对齐；编辑距离才处理插入删除。接收词离两个码字同距时，最近邻解码会出现 tie，超过保证半径后不能声称唯一正确。

Hamming 距离衡量码字可分性，是 度量空间公理库度量空间Metric space用满足正定性、对称性与三角不等式的实值距离刻画点间远近的空间。 的有限离散实例。它也是 Hamming 界公理库Hamming 界Hamming bound · Sphere-packing bound由互不相交纠错球的体积给出码大小、长度与最小距离的上界。 和 线性码公理库线性码Linear code有限域向量空间中的线性子空间作为码字集合的信道码。 距离的基础。容错存储、组合设计、局部敏感哈希和二进制特征比较都使用它；码的重量是与零词的 Hamming 距离。

在性质测试中，常把 $d_H(x,y)/n$ 作为相对距离，并用到性质的距离公理库到性质的距离Distance to property · Distance from a property取对象到性质中最近合法对象的归一化距离，并据此精确定义 close、far 与测试 promise。取对所有合法对象的最小值；测试器公理库性质测试模型Property testing model · Property testing通过少量 oracle 查询区分完全满足性质的对象与到该性质至少相距 ε 的对象，并允许 gap 内行为任意。只需以少量坐标查询区分距离为零与至少 $\epsilon$。若两个字分别由 Alice 与 Bob 持有，计算它们是否相等或距离是否超过阈值则是通信问题，成本按交换 bit 而非不同坐标数计算。Hamming 距离给出输入几何，却不会自动等于查询复杂度或Equality公理库Equality 通信问题Equality communication problem · EQ communication problem比较双方 n-bit 私有串是否完全相同，展示确定性完整传输与公共随机指纹之间的指数差异。 的通信复杂度。