翻转的位
伴随式
接收结果
每发送一位的数据位

更多关于纠错码

纠错码模拟器

每条经由导线、空气或划伤的光盘传输的消息都会沾上错误:位从 0 变成 1,又从 1 变回 0。纠错码会添加几个精心选择的额外位,让接收方无需再次请求就能找到并修复损坏。输入四个数据位,看理查德·汉明的码如何把它们变成七位,随意翻转任何一位,再看三个相互重叠的圆如何直接指向错误。然后把整条消息送过噪声信道,比较使用和不使用纠错码时收到的内容。 输入四个数据位,例如 1011,应用会加上三个校验位,组成一个 7 位的汉明码字。点击任意一位(在圆中或在行中均可),像噪声那样把它翻转;再点一次即可翻回。每个圆中 1 的个数都必须是偶数:不通过校验的圆指向出错的那一位,解码器再把它翻回来。打开额外校验位,就能看到两个错误被检测出来,而不是被错误地纠正。在下方,可以把一段文字分别在使用和不使用纠错码的情况下送过噪声信道。

它是如何运作的

  1. 输入四个数据位,查看带有三个校验位的七位码字,它同时以圆和一行位的形式显示。
  2. 点击位来翻转它们,观察哪些圆校验不通过、伴随式指向哪里,以及解码器是否修复了这个字。
  3. 打开额外校验位,然后把一条消息送过噪声信道,比较使用和不使用纠错码时的结果。

汉明码如何找到错误

七个位编号为 1 到 7。第 1、2、4 位是校验位,四个数据位位于第 3、5、6、7 位。校验位 1 使第 1、3、5、7 位中 1 的个数为偶数,这些位置的二进制编号都以 1 结尾;第 2 位对第 2、3、6、7 位做同样的事,第 4 位则对第 4、5、6、7 位。画成三个相互重叠的圆时,每一位恰好位于检查它的那些圆中。当某一位翻转时,包含它的圆就变成奇数。把不通过的校验读作一个二进制数,即伴随式,就得到出错位的位置。

多一位能换来什么

如果翻转了两位,伴随式会指向第三个无辜的位,解码器反而让情况更糟。再加上第八位,使整个字中 1 的个数为偶数,就能解决这个问题:一个错误会改变整体奇偶性,两个错误则使整体保持偶数,同时有些圆校验不通过。这种扩展码称为 SECDED,即单错纠正、双错检测,它能纠正一个错误并可靠地检测出两个错误,于是接收方可以要求重发那个块。服务器的 ECC 内存使用的正是这种码。在噪声信道上,只要两次翻转很少落在同一个块里,这种码就能把大量零散的错误减少到寥寥几个。

常见问题

为什么校验位位于第 1、2、4 位?

因为它们是 2 的幂,二进制中都只有一个 1。校验位 2ᵏ 检查所有二进制编号在第 k 位上为 1 的位置。第 6 位(二进制 110)翻转时,会破坏第 2 位和第 4 位的校验,而第 1 位不受影响;不通过的校验拼出 110,也就是这个位置本身。

这种保护要付出多大代价?

(7,4) 码每 4 个数据位要发送 7 位,码率为 4/7:多出 75%。扩展码每 4 位发送 8 位,翻了一倍。更长的汉明码更划算:15 位承载 11 个数据位,31 位承载 26 个。用于 Wi-Fi 和 5G 的 LDPC 码、极化码等现代编码,已经非常接近克劳德·香农在 1948 年证明可以达到的最佳码率。

出现三个错误时会怎样?

普通汉明码可能被完全骗过:任意两个码字至少有三位不同,所以三次翻转可以把一个有效码字变成另一个,根本不会有校验不通过。应用会把这种情况报告为错误未被发现。实际系统会选择足以应对噪声水平的强码,让这种情况保持罕见。

纠错码用在哪里?

几乎所有传输或存储数字数据的地方:ECC 计算机内存、硬盘和 SSD、CD、DVD 和蓝光光盘、撕掉一部分仍可读取的二维码、手机和 Wi-Fi、数字电视,以及来自旅行者号等太空探测器的信息,它们至今仍从太阳系之外发回数据。

我的消息会被发送到别处吗?

不会。噪声信道是在你的浏览器中模拟的,你的消息和设置都保存在此浏览器的本地存储中。

准备好尝试了吗?

在浏览器中打开 PictorX — 无需安装,无需信用卡即可启动。

前往编辑器