十四个开关 · 第 02 份 · Shannon 1948 → Hamming 1950 → Reed–Solomon 1960

纠错码开关

CD 刮花了还能放、二维码破一角还能扫、旅行者号从 240 亿公里外发回的照片——靠的都是同一件事:多带上一点冗余,让接收端能把错的字节算回来。下面三栏用同一份信道噪声,差别只有带了多少冗余。这是真的 GF(256) 上的 Reed–Solomon,编码和译码(Berlekamp–Massey + Chien + Forney)都在你浏览器里跑。

总闸

同一份噪声,三种冗余

在图上拖动可以手动砸坏一片字节
裸传 · 0% 冗余 RS(255,239) · 6.3% 冗余,纠 8 个 RS(255,223) · 12.5% 冗余,纠 16 个

那道悬崖

正在逐档实测…

关掉的是什么

关掉的是那 32 个校验字节。三栏走的是同一条信道、同一串随机数、同一批错误位置,唯一的差别是每 255 个字节里留了几个给冗余:0 个 / 16 个 / 32 个

代价小得惊人:RS(255,223) 只多带 12.5% 的数据,换来的是每 255 个字节里任意 16 个坏掉都能算回来——不是「大概能」,是可证的。

边界是刀切的

右边那张表是实测:给一个码字精确注入 e 个错误,e ≤ 16 时成功率 100.0%,e = 17 时成功率 0.0%。中间没有过渡带。

这是 Reed–Solomon 和「大概能修」的本质区别:它的能力是一个整数,不是一个概率。而超过那个整数之后它不是「修得差一点」——是彻底失效,而且可能还悄悄给出一个错误的「已修复」结果

⚠ 我预期错了:崩点不在 6.3%

动手前我算「一个码字 255 字节、能纠 16 个 ⇒ 崩点在 255q = 16,也就是 6.3%」。实测整幅图的崩点在 3~4%

因为 6.3%单个码字的 50% 分界;而一幅图要 74 个码字全部成功。要每个的失败率低于 1/74,得让 255q + 2.2√(255q) < 16,解出 q ≈ 3.6%——和实测对上了。

⇒ ★ 可靠性按最弱的那一环算,不按平均。这条规矩在任何「N 个部件都得好」的系统里都成立。

⚠ 而译码器我第一版写错了两处

Chien 搜索里我用数组下标 k 当错误位置,而该用的是次数 N−1−k;同时 Forney 公式漏了 X_j 那个因子(生成多项式的根从 α⁰ 起时要乘)。

两处一起改才对:只改对一处,成功率仍然是 0%。而这个 bug 的表现是「所有测试全部失败」——比只错一点点好查得多。⚠ 真正危险的是另一种:改对了一处,测试从 0% 变成 60%,那才会让人以为方向对了。