检查线索怎样找到一位错误?
传送一串 0 和 1 时,某一位可能被翻错。多添几位检查信息,可以让接收端发现异常。
这里安排几组互相重叠的检查,每个位置参加的组合都不同。如果最多只错一位,哪些检查失败就能指出它的位置;翻回去,原消息便恢复了。
试着让两位一起出错,再看原来的办法为什么可能判断错。纠错有适用范围,多加一次检查可以区分更多情况,却仍不是任意错误都能恢复。
亲手制造一次误纠,再看扩展码怎样拦住它
- 先只翻错一位,看看检查线索能否找到并恢复它。
- 再翻错两位,观察普通纠错为什么可能给出错误答案。
- 换成扩展码,保留同样的两处错误:它能报警,不等于找到了两处错误的位置。
校验矩阵、距离和能力边界
进一步操作与数值核对
进入自由探索,选择四位消息、编码方式,再按位翻转信道数据。按钮既显示固定编号,也显示接收值;键盘 Tab 可以逐个聚焦,空格或回车切换。无翻转、单错 6、双错 3+5 是可复现的快捷输入。重置恢复消息 1011、扩展码和单错 6。共享播放器保留播放、暂停、重播与章节跳转。
先选普通 Hamming,翻转第 3 和第 5 位。两次错误产生的综合征是 3 XOR 5 = 6。按单错规则解码,会误翻第 6 位,得到 0100101,提取数据为 0101。这是另一个合法码字,但不是发送的消息。 如果只做检测而不尝试纠正,普通 Hamming 的非零综合征可以报告所有双错;它无法同时把单错纠正和双错识别区分开来。
切换到扩展 Hamming(8,4),在第 8 位加入全字偶校验。比较时,四位消息与第 3、第 5 位这两个翻转位置相同。用 s 表示原来三项校验构成的综合征,q 表示收到的全部八个位的异或:
| 接收检查 | 在最多两位翻转的前提下 | 解码动作 |
|---|---|---|
| s=0,q=0 | 未检出错误 | 接受码字 |
| s≠0,q=1 | 前七位中的单错 | 翻回位置 s |
| s=0,q=1 | 新增总校验位单错 | 翻回第 8 位 |
| s≠0,q=0 | 双错 | 报警,不纠正,不交付数据 |
双错可以涉及数据位、普通校验位或新增的第 8 位。模型对全部位置一视同仁。双错报警不是找到那两个错误位置;此时存在多个同样合理的原始码字。
想核对技术细节?
传送一串 0 和 1 时,某一位可能被翻错。我们额外添几位“检查信息”,让几组互相重叠的检查一起找线索。如果只错一位,失败的检查组合就能指出它的位置;错得更多时,这个保证会失效。
给消息加一位总奇偶校验,可以发现一次翻转,却不能告诉我们哪一位错了。Hamming(7,4) 把四位数据放到位置 3、5、6、7,在 1、2、4 放三个校验位。这里统一用偶校验:每组中一的数量必须为偶数,等价于这组所有位的异或为零。
三组分别是 C1 = {1,3,5,7}、C2 = {2,3,6,7}、C4 = {4,5,6,7}。它们的重叠有意安排过:每个位置的参与组合都不同。数字 6 的二进制写法是 110,所以第 6 位属于 C4 和 C2,却不属于 C1。上标附近的数字是位置编号;圆内的零或一才是该位的值。
演示始终跟随消息 1011,编码得到 0110011。信道翻转第 6 位后,接收码字变成 0110001。重新检查得到 C1=0、C2=1、C4=1,按 C4、C2、C1 排成综合征 110₂ = 6。在最多一位错误的前提下,翻回第 6 位,再提取位置 3、5、6、7,就恢复 1011。接收端只使用收到的码字;界面上的原数据用于教学对照,并不参与解码。
以位置 1 到 7 为列、以数据 d1 到 d4 为输入行,模型用下面的生成矩阵计算 c = dG,运算都在二元域 GF(2) 中进行。数据列 3、5、6、7 组成单位矩阵,所以是系统码:原消息位仍能直接取出。
G = 1 1 1 0 0 0 0
1 0 0 1 1 0 0
0 1 0 1 0 1 0
1 1 0 1 0 0 1
H = 1 0 1 0 1 0 1 C1
0 1 1 0 0 1 1 C2
0 0 0 1 1 1 1 C4
HGᵀ = 0。接收列向量 r 的三个校验结果为 Hr。扩展码把前七位的异或附在位置 8;相应扩展检查矩阵在 H 的右侧补零列,再增加一行八个一。
Hamming 距离是两个等长码字中值不同的位置数量;奇偶校验是对一组位做异或。两者不是同一个量。对全部 16 个合法码字两两比较,普通码的最小距离为 3,扩展码为 4。这里采用的 SECDED 解码规则保证纠正单错并检测双错,并不保证纠正双错。
探索中可以翻转超过两位来检验边界。例如扩展码翻转 1、2、3 位,会被误判为第 8 位错误;翻转 1、2、3、8 位,会直接成为另一个合法码字而漏检。不能把“未检出错误”读成“原始消息一定正确”。这是短二元块码的完整教学模型,不是某款存储器的完整 ECC、重传协议或故障概率模型。
构造与扩展方法见 Hamming 1950 年原论文,第 3–5 节。距离与纠检能力的关系见 MIT 6.02 纠错编码讲义;双错与总校验的接收逻辑可对照 MIT 6.111 习题解答。本文中的码字数值与反例由独立模型计算。