Hamming 距离

比较的是位置，不是数值大小 ​

把两个同样长的字符串逐位对齐，数一数有多少个位置不同，得到的就是 Hamming 距离。例如：

因此 $d_H(x,y)=3$。一个位置从 0 换成 1 算一次，从字符 A 换成 Z 也只算一次；符号之间没有预先规定的数值距离。

这个度量适合描述替换错误。插入一个字符会使后面的对齐关系整体移动；编辑距离的网格动态规划理路编辑距离的网格动态规划Levenshtein distance dynamic programming · Wagner–Fischer algorithm把插入、删除与替换写成前缀网格的三类边，求出最小改写费用并重建逐条可执行的脚本。让插入、删除与替换共同决定对齐路径，因而可以比较不同长度的字，不能用原位置的不同字符数代替。

Hamming 球为什么是这个大小 ​

设 $|\mathrm{\Sigma }|=q$，以 $x$ 为中心、半径为整数 $0\le t\le n$ 的球是

恰好改动 $i$ 位，要先用组合数理路组合Combination · k-subset从有限集合中无序选取固定数量元素所得的子集。从 $n$ 个位置中选出 $i$ 个，再为每个位置选一个不同于原符号的新符号。因此

二元长度 $7$、半径 $1$ 的球包含原词和七种单比特翻转，共 $8$ 个字。若一个码保证纠正一位错误，这些以码字为中心的球必须互不相交。把它们装进全部 $q^n$ 个字中，就得到Hamming 界理路Hamming 界Hamming bound · Sphere-packing bound由互不相交纠错球的体积给出码大小、长度与最小距离的上界。所使用的计数关系。

为什么擦除比未知翻转容易处理 ​

擦除会标出出错位置。若两个码字在未擦除位置上都与接收词一致，它们只能在被擦除的 $s$ 个位置上不同，因此距离至多 $s$。只要 $s<d_{min}$，就只能有一个候选；所以最小距离 $d_{min}$ 可保证恢复至多 $d_{min}-1$ 个擦除，比纠正未知翻转的半径更大。

例如重复码收到 1??，唯一可能的码字是 111；收到 100 则无法知道第一位错了还是后两位错了。若同时有 $e$ 个未知替换和 $s$ 个已知擦除，两个可能原词在未擦除位置至多相差 $2e$ 位，在擦除位置至多相差 $s$ 位，故 $2e+s<d_{min}$ 是唯一恢复的保证条件。这个计数解释了错误位置提示的价值，而不是增加了码字之间的距离。

归一化距离与使用范围 ​

对 $n>0$，相对距离 $d_H(x,y)/n$ 衡量不同位置所占比例，便于比较不同规模的实例。在性质测试理路性质测试模型Property testing model · Property testing明确 oracle、距离和承诺间隔，用测试算法与下界区分局部违规、全局距离、容忍性和查询成本。中，再取一个输入到所有合法对象的最小相对距离，便得到“需要改动多大比例才能修好”的概念。

距离描述的是输入之间的几何关系，不直接给出计算成本。两个完整数组的朴素比较要查看各坐标；压缩位串、抽样测试或分布式持有输入时，算法成本还取决于表示与计算模型。同样，最近邻距离并不自动等于信道中的最大似然代价：各位置错误概率不同或提供软可靠度时，译码往往需要加权信息。

距离怎样变成纠错能力 ​

设码 $C\subseteq {\mathrm{\Sigma }}^n$ 至少有两个码字，其最小距离为

若发送 $c$ 后至多有 $d_{min}-1$ 个位置被改动，接收词不可能变成另一个码字。否则两个码字的距离就小于 $d_{min}$。因此，检查接收词是否仍为码字，能够保证检测这一区间内的非零错误。

纠错需要更大的间隔。假设接收词 $r$ 同时距两个不同码字至多 $t$，则

只要 $2t<d_{min}$，这种混淆便不可能发生。因此最近邻译码能够保证纠正

个任意替换错误。这是对所有码字、所有相应错误位置的保证，不是平均成功率，也不是说超过这个数就必定失败。[1][2]

二元重复码 $C=\{000,111\}$ 的最小距离为 $3$。发送 000，若第一位翻转得到 100，它距 000 为 $1$、距 111 为 $2$，最近邻能恢复原词。若前两位翻转得到 110，它反而距 111 更近，会被误纠到另一个码字。这个例子也说明：“发现了错误”与“知道原来是什么”需要不同强度的冗余。

对至少含两个码字的线性码理路线性码Linear code有限域向量空间中的线性子空间作为码字集合的信道码。，任意两码字之差仍是码字，故

于是两两比较码字的问题，化成了寻找最轻的非零码字。综合译码理路综合译码Syndrome decoding利用校验矩阵消去码字成分，以综合定位错误陪集并选择首领；区分合法输出、正确恢复与一般译码困难性。正是在这一线性结构中定位错误。

多处错误也可能只含一个独立方向 ​

若每个符号来自扩域 $L/{\mathbb{F}}_q$，秩度量理路秩度量码Rank-metric code · 秩距离码以错误矩阵的秩或扩域符号张成的底域维数衡量噪声，证明矩形Singleton界、秩一球计数及唯一纠错半径。可以改按错误值张成的底域维数收费。四个相同非零错误值有Hamming重量四，却只有秩一；两个底域独立的错误值则有秩二。固定底域后总有 ${\mathrm{wt}}_R\le {\mathrm{wt}}_H$，但相同半径对应不同错误集合，必须重新核对码距及译码合同。

Gabidulin码理路Gabidulin码与Moore求值Gabidulin code · Gabidulin evaluation code在底域独立的求值点上评价低q次数线性化消息，构造达到秩Singleton界的线性码，并证明最小距离与任意k个坐标的擦除恢复。提供这种距离下的最优构造。它允许在一个秩方向传播到许多位置的情况下恢复消息，不表示任意四个无关替换也同样可纠。