案例库 · 工程与运营 · 技术决策 · 1960
里德-所罗门码让划伤的CD仍能播放
1960年，里德和所罗门将数据编码为多项式，使少量损坏的值能被精确重建。
MIT林肯实验室
那一手
数字信息只是0和1，任何不完美的设备偶尔会翻转一个位，所以划伤的CD或微弱的无线电链路会损坏数据。简单的修复是冗余：把每个内容发送三次，取多数票，但这样要三倍数据才能对付一个错误。
里德和所罗门在1960年的论文中，将消息编码为多项式的系数，并在多个点上求值，于是整个消息变成一长串值。一个k-1次多项式由k个点唯一确定，接收方只需要部分值就能插值出原始消息。
这意味着少量额外点能修复许多错误，与重复相比，每个字节的开销远小。它使旅行者二号能从外行星发回清晰照片，也让有划痕的光盘仍能播放，因为损坏被视为缺失的样本，需要重建，而不是要读取的数据。
为什么管用
- 低次多项式由少量点唯一确定，所以额外的求值点是廉价的冗余。
- 插值能恢复系数，即使某些值错误或缺失，所以损坏是可修复的。
- 开销只是少量额外点，远小于重复所需的翻倍数据。
值了多少将数据编码为多项式，从部分损坏中恢复神来之笔
可以搬走什么
把冗余花在少量巧妙的校验值上，可以求解回来，而不是重复拷贝，这样每个字节能修复更多损坏，并且对干净数据几乎不增加开销。
后来呢
里德-所罗门码成为光盘、数字录音带、硬盘驱动器、DSL和QR码等二维条码内的标准纠错方案，让受损媒体仍能正确读取；这篇1960年五页纸的论文如今成为数字通信领域最具影响力的论文之一。
资料来源
发现哪里写错了？告诉我们。