纠错编码

最常见的纠错编码是海明码。这一节有两样东西要带走：码距决定检错和纠错能力的那条公式，以及海明码校验位数的不等式 。完整的编码过程在计网里考得不多，但它是理解”为什么能纠错”的唯一途径，而且计组也要用。

机制

海明码的思路：让每一位参加几个检验组

海明码的实现原理是：在有效信息位中加入几个检验位形成海明码，并把海明码的每个二进制位分配到几个奇偶检验组中。某一位出错后，就会引起有关的几个检验位的值发生变化——这不但可以发现错位，而且能指出错位的位置，为自动纠错提供依据。

对比奇偶检验码：它只有一个检验组，所有位都在里面，所以只能知道”组里有奇数个错”，不知道是哪一位。海明码让不同位参加不同组合的检验组，于是”哪几个组出了问题”就唯一对应”哪一位错了”。

码距：检错与纠错能力从哪里来

任何一种编码的检错能力和纠错能力都与该编码的最小距离有关。码距（也称海明距离）是指两个码字对应位取值不同的比特数。计算码距的一种方法是对两个位串进行异或运算，结果中 1 的个数即为码距。例如，异或结果中有两个 1，所以 0110 和 0011 的码距为 2。

在一个编码集中，任意两个码字的码距的最小值称为该编码集的码距。 例如编码集 {10011, 01011, 11110, 00001}，尽管 11110 和 00001 的码距为 5，但 10011 和 01011 的码距为 2，取最小值，所以该编码集的码距为 2。

根据纠错理论，编码方案的检错能力和纠错能力与码距的关系为：其中是能检错的位数，是能纠错的位数。码距越大，能检错的位数越大，能纠错的位数也越大，且纠错能力恒小于或等于检错能力（能纠错必然能检错）。例如码距时，这种编码最多能检错 2 位，或能纠错 1 位。

考虑和两种边界情况，得到两条常用结论：

为了检测位错误，需要码距为的编码方案。 一个有效码字发生位错误时，不可能变成另一个有效码字。可见，码距为 1 的编码方案无法检测任何错误。
为了纠正位错误，需要码距为的编码方案。 一个有效码字发生位错误时，它仍然离原来的码字最近，从而能确定原来的码字，达到纠错的目的。

第二条的直观理解：把每个有效码字想成一个点，出错就是从点出发走了几步。要检出错，只要走步到不了别的有效码字（间距）；要纠正错，还得保证走步之后离自己仍比离别人近，两边各让出步再留一步余量，间距就要。

海明码的编码过程

海明码具有 1 位纠错能力。以数据 1010 为例：

（1）确定海明码的位数。 设信息位有位，检验位有位。位检验位能表示种状态；信息位和检验位共有种”1 位出错”的状态，此外还需要一种表示”正确”的状态，因此和应满足时，成立，所以。信息位，检验位，海明码为。

（2）确定检验位的分布。 规定检验位在海明位号为的位置上，其余各位为信息位，按原来顺序放入：

（3）分组，形成检验关系。 每个数据位用多个检验位进行检验，条件是：被检验数据位的海明位号，等于检验该数据位的各检验位海明位号之和。检验位不需要再被检验。

数据位	所在位置	位号分解	由谁检验
			、
			、
			、
			、、

于是第 1 组（负责）是；第 2 组（）是；第 3 组（）是。

（4）检验位取值。 的值为第组所有数据位求异或：

所以 1010 对应的海明码为，即 1010010（下画线为检验位）。

（5）检验原理。 每个检验组用检验位和参与形成该检验位的信息位进行奇偶检查，构成个检验方程：

若，说明无错；否则说明出错，且这个二进制数就是错误位的位号。例如说明出错，直接将该位取反即达到纠错的目的。

计算模板：海明码

求检验位数：找最小的使。
放检验位：放在第位（1、2、4、8…），数据位按顺序填满其余位置。
分组：把每个数据位的位号写成 2 的幂之和，出现哪个幂，就归哪个检验位管。
算检验位： = 它所管的数据位的异或。
纠错：收到后算，非零时的值就是出错位号。

信息位	1	2～4	5～11	12～26	27～57
检验位	2	3	4	5	6

例（王道 3.3.3 第 4 题）：10 位数据采用海明码需要增加几位冗余信息？时，时，所以。

例（纠错）：收到 1110010。按上面的分组，；。

，（即）出错，取反得 1010010，与上面编出的码一致。

边界

码距为 3 时是”检 2 位或纠 1 位”，不是”检 2 位同时纠 1 位”。 公式要求：时只有或两种用法。想同时纠 1 位、检 2 位，需要。

海明码只能纠 1 位错。 两位同时出错时，仍会给出一个非零位号，按它取反反而会把正确的位改错。

检验位的位置是，不是连续放在一端。 这是分组能用”位号分解”来算的前提；换了位置，” 的值就是出错位号”这条结论也就不成立了。

里的”+1”是”无错”那种状态。 忘了它会把算成（不成立，但也不成立……实际上多数人会漏在、这种临界值上）。

计网与计组用的是同一套海明码。 计组第 2 章讲校验码时有更完整的推导，两边的位号约定一致。

对照速查

需求	最小码距
检测位错
纠正位错
纠正位且检测位（）

说法	对错
码距为 1 的编码不能检测任何错误	✅
码距为 3 的编码能检 2 位错且同时纠 1 位错	❌（二者只能取其一）
纠错能力可以大于检错能力	❌
海明码能纠正 1 位差错	✅
4 位数据需要 3 位海明检验位	✅

考点

码距 = 异或结果中 1 的个数；编码集码距取最小值
；检位需，纠位需
海明码校验位数：
在第位；数据位位号 = 检验它的各检验位位号之和
检验结果即出错位号，取反纠错

考研笔记