← 实验室
ASTERXOR / 实验室

能修好一个错误位的消息

三枚精心安排的校验位,能定位七位块中的一个错误;超出假设时,同一解码器也可能自信地改错。

七个蓝金色位标记中,一个位置被白圈突出。
数值九的编码,圈出一个可能翻转的位置。
实验室ASTERXOR / LEON LEUNG

把这个小编码消息任意翻转一位,原来的四位数值都能回来。

实验使用Hamming(7,4),把四个载荷位变成七位。额外部分不是整条消息的副本,而是建立重叠奇偶校验,用失败组合定位一个受损位置。我们测试所有四位消息与全部单比特翻转,再故意引入两位错误,观察承诺的边界。

冗余怎样安排,决定它能告诉你什么出了错。
SEVEN POSITIONS

校验位置与地址有关

把位置编号为1至7,校验位放在1、2、4,载荷放在3、5、6、7。每个校验看二进制地址含对应位的位置:校验1看奇数位,校验2看2、3、6、7,校验4看4、5、6、7。

编码器设置校验位,使每组中的1为偶数,这叫偶校验。重叠分组是关键:每个位置属于不同校验组合。因此,单个位改变会留下独特指纹,而不只是宣布“有错”。

三行重叠校验使七个位置各有不同成员组合。
FIG 01金色格表示每条校验规则检查的位。
READ THE DISAGREEMENT

失败组合就是地址

载荷九的本地编码为0011001,从左至右是位置1到7。翻转第5位,校验1和4失败,校验2仍通过,把失败标签相加得到5。解码器再翻转该位置,恢复码字并取出原载荷。

这种组合叫校验子。零表示当前三条奇偶方程都成立。在零或一个错误的假设下,非零值准确指明要修复哪里。校验位本身出错也能修复,保护覆盖七位,不只四个载荷位。

三行分别显示干净、受损与修正后的码字。
FIG 02编码九、翻转第5位,再由单错解码器恢复七位原码字。
TRY EVERY SMALL CASE

小范围承诺可以穷尽检查

四位消息共有16种,脚本先解码全部干净码字,再对每条消息分别翻转七个位置,得到112个单错案例,全部恢复正确载荷。这覆盖了这个小错误模型,不只是几个幸运随机样例。

报告把它们合为两项检查:全部干净情况、全部单错情况,没有把每个翻转包装成独立科学结论来膨胀计数。它们证明指定有限范围中的实现行为,不测量物理信道错误频率或真实存储设备表现。

TWO WRONG BITS

同样的自信,也可能修错地方

再次从载荷九出发,同时翻转位置1和2,合成校验子为3。单错解码器以为第3位损坏,翻转了原本正确的载荷位,输出变成八。三条校验无法把这件事与“只错第3位”区分开。

非零校验子能揭示奇偶关系失败,却不能证明只错一位。Hamming(7,4)有效码字的最小距离为3,支持唯一单错修复,但这里的纠错程序可能把两位损坏修错。边界应与成功数字并列,而不是藏在“消息能自愈”的小字里。

THE PRICE OF REPAIR

额外位买到特定保护

每四个载荷位增加三位,让有效码字彼此拉开距离。在假设成立时,附近受损字能重新归回原邻居。不同编码和信道模型,对块长度、检错、纠错和解码工作量有不同取舍。

这里只实现图中的小型二进制方案,没有测试二维码、无线链路、内存硬件或生产纠错库。可亲手检查的启发是:增加韧性不只靠整段重复。重叠约束安排得当,有限的一类错误就能暴露自己的位置。

留一个想法带走

修复承诺有多强,要看旁边写着怎样的错误模型。