纠错码详解
没有完美的信道。宇宙射线会翻转内存中的位,划痕会抹去光盘的一部分,无线电信号会衰减。数字系统不是听天由命,而是以巧妙的方式加入冗余,使接收方即使在部分内容出错时也能推断出发送的是什么。这些编码背后的数学始于 20 世纪 40 年代末,默默保护着我们存储或发送的几乎每一个位。
用奇偶校验检测错误
最简单的保护是单个奇偶校验位:加上一个 1 或 0,使 1 的总数为偶数。如果途中有一位翻转,计数就变成奇数,接收方便知道出了问题。奇偶校验无法指出是哪一位出错,两次翻转还会相互抵消而不被察觉,但它成本低廉,几十年来一直用于内存和串行链路。不过,检测出错误只完成了一半工作:接着还必须重新发送数据。
用重复来纠错
要在不重新请求的情况下纠正错误,接收方需要足够的冗余来以多数压倒错误。把每一位发送三次,即 000 或 111,接收方就可以按多数取值:三位一组中的一次翻转会被纠正。代价很高:每一位数据要用三位,而且同一组中的两次翻转仍然会占上风。开创编码理论的问题是:能否做得更好?
汉明的码
1947 年,理查德·汉明在贝尔实验室使用一台从穿孔卡片读取程序的继电器计算机。它在周末发现错误时只会停机,汉明星期一回来面对的是白白浪费的作业。他问道:既然机器能检测出错误,为什么不能定位并纠正它?他的答案于 1950 年发表,把 4 个数据位作为 7 位发送。三个校验位位于第 1、2、4 位,各自检查一组不同的、相互重叠的位置,这些分组经过挑选,使每个单个错误都会破坏一种独特的校验组合。
伴随式
接收方重新计算这三个校验。如果全部通过,就接受这个字。如果有些不通过,把不通过的校验写成二进制数字,以校验 4 为最高位,就得到一个 1 到 7 之间的数:伴随式,它恰好就是被翻转的位的位置。把它翻回来就恢复了码字。这个技巧之所以有效,是因为位置的编号方式让每个位置的二进制展开正好列出它所属的校验,这也是为什么这种码画成三个相互重叠的圆时显得如此整齐。
汉明距离
两个字之间的汉明距离是它们不同的位置数。在 (7,4) 码中,任意两个码字至少相距 3。一个有一处错误的字与发送的码字仍相距 1,与其他每个码字至少相距 2,所以译码为最近的码字就能纠正它。一般来说,码字之间至少相距 d 的码能检测 d − 1 个错误,并纠正 (d − 1)/2 个错误(向下取整)。加上一个整体奇偶校验位,距离就提高到 4,得到能纠正一个错误并检测两个错误的扩展码。
香农极限
1948 年,比汉明的论文早两年,克劳德·香农证明了一个惊人的定理。每个噪声信道都有一个容量,只要使用足够长的码,就能以低于这个容量的任何速率发送数据,并使错误少到任意程度;高于这个容量,错误就无法避免。香农证明了这样的码存在,却没有说明如何构造它们。找到接近他的极限的实用编码花了半个世纪,从 1960 年的里德-所罗门码,到 1993 年的 Turbo 码,再到低密度奇偶校验码的重新发现。
身边无处不在的编码
里德-所罗门码让 CD 带着划痕也能播放,让二维码在图案损坏多达 30% 时仍能扫描。服务器内存使用扩展汉明码来修复宇宙射线造成的单个位翻转。旅行者号拍摄的外行星照片先后由戈莱码和里德-所罗门码保护,而 5G 和 Wi-Fi 的 LDPC 码和极化码几乎榨取了信道允许的每一个位。就连书上的条形码和银行账号的最后一位,也是简单的检错码。
动手探索
打开纠错码模拟器,用汉明 (7,4) 码对任意四个数据位编码,在圆中或行中点击位来翻转它们,观察不通过的圆和伴随式如何指向错误,然后解码器将其修复。打开额外校验位可以看到双错误被检测出来,把一条消息送过噪声信道,则可以比较使用和不使用纠错码时收到的内容。
常见问题
错误检测和错误纠正有什么区别?
检测只告诉接收方出了问题,所以它必须要求重新发送数据;奇偶校验位或校验和就是这样做的。纠正让接收方无需请求就能重建原始数据,这需要更多冗余。无法重新请求的系统,例如远在数百万公里之外的太空探测器或 DVD,依靠的是纠正。
为什么不干脆把所有内容发送两次?
两份副本能表明发生了错误,却不能说明哪一份是对的,而且成本翻倍。三份副本可以进行多数表决,但成本变为三倍。汉明码用不到两倍的位数就能纠正每七位一组中的单个错误,而更长的码效果要好得多。
理查德·汉明是谁?
美国数学家(1915–1998),曾参与曼哈顿计划,之后在贝尔实验室工作了三十年。除了他的编码,他还以信号处理中的汉明窗、汉明距离以及他的演讲《你和你的研究》(You and Your Research)而闻名。他于 1968 年获得图灵奖。
一种码能纠正任意多个错误吗?
只有在冗余足够时才行。一种码每块最多能纠正 (d − 1)/2 个错误,其中 d 是码字之间的最小距离,而校验位更多的更长的码可以达到更大的 d。香农定理设定了终极极限:没有任何码能超越信道的容量。
准备好尝试了吗?
在浏览器中打开 PictorX — 无需安装,无需信用卡即可启动。
打开纠错码模拟器