跳转到内容
Jason's Study

Reed-Solomon 编码

是什么

Reed-Solomon（RS）是 1960 年 MIT Lincoln 实验室两位数学家发明的多项式编码。日常类比：

你写下一条算式 y = ax + b，让三个朋友各取一个 x 算出 y。后来你只要听任意两个朋友报数，就能反推出 a 和 b——丢一个人也无所谓。

把”算式”换成更高阶的多项式，把”朋友”换成存储位置或传输信道，你就有了 RS 编码：把数据当多项式系数，编码就是这条多项式在更多点上的取值。

只要丢失或损坏的”取值点”不太多，原来的多项式（也就是原数据）就能从剩下的点反推出来。这是 CD、二维码、卫星通信、RAID 6 共用的同一招。

为什么重要

不理解 RS，下面这些事都没法解释：

  • 为什么 CD 划了一道印还能播——RS 在背后默默修
  • 为什么二维码遮住一角扫码还成功——QR 强制带 RS，最高级（H）允许 30% 区域损毁
  • 为什么 Voyager 探测器从 60 亿公里传图回地球还能解出来——靠 RS(255, 223) 抗深空噪声
  • 为什么现代分布式存储（HDFS / Ceph / S3）能把”三副本”换成”省一半空间的纠删码”

它比 hamming-1950 强在两点：① 一次能纠多个错（Hamming 只纠 1 比特） ② 抗突发错误（Wi-Fi 信号、闪存坏块、印刷污渍都是连续错一片）。

核心要点

RS 编码可以拆成 三步：

  1. 数据当系数：k 个数据当成 k-1 阶多项式 P(x) 的系数。比如数据 (1, 2, 3) → P(x) = 1 + 2x + 3x²。

  2. 多点取值：在 n 个不同的点 x₁, x₂, …, xₙ 处算出 P(x)，得到 n 个码字。n > k，所以是”加冗余”。

  3. 任意 k 个能恢复：只要拿到 n 个码字里任意 k 个未损坏的，就能用插值反推出 P(x)，进而拿回原数据。

错误纠正能力 t = ⌊(n - k) / 2⌋ 个符号错。“符号”是关键词：一个符号可能是 8 比特，所以一个符号坏 = 1-8 比特坏都算 1 个。这就是为什么 RS 抗连续错——一片连续坏算几个符号坏，不像 Hamming 那样比特对比特。

实践案例

案例 1：toy RS(7, 4) 直观看一遍

设有 4 个数据 (m₀, m₁, m₂, m₃)，构造多项式：

P(x) = m₀ + m₁ x + m₂ x² + m₃ x³

在 7 个不同的 x 上取值，得 7 位码字：

码字 = (P(x₁), P(x₂), P(x₃), P(x₄), P(x₅), P(x₆), P(x₇))

故意把第 2、5、7 位丢掉，只剩 (P(x₁), P(x₃), P(x₄), P(x₆)) 这 4 个。4 个点 + 3 阶多项式 → 拉格朗日插值唯一确定 P(x) → 恢复 (m₀, m₁, m₂, m₃)。

意义：丢了 3/7 还能完整恢复，这是单条多项式”过定方程”的红利。

案例 2：QR 码的纠错等级 L/M/Q/H

QR 码强制带 RS 冗余。四个等级对应不同的冗余比例：

等级冗余占比能修多少损坏
L~7%印刷小污渍
M~15%普通遮挡
Q~25%部分被涂掉
H~30%30% 区域损毁

为什么 QR 是天然 RS 友好？因为污渍、遮挡都是连续区域——这正好是 RS 最擅长的”突发错误”模式。一片黑方块连损 8 个，对 RS 而言只是 8 个符号错，远没到上限。

案例 3：分布式存储的 RS(10, 6) 纠删码

传统三副本：一份数据存 3 份，3 倍空间开销。

现代纠删码：把数据切 6 块 + 4 个 RS 冗余 = 10 块，分散到 10 台机器。

  • 任意 4 台机器宕机仍能恢复数据
  • 空间开销只有 1.67 倍（10/6）
  • 对比三副本省一半空间

这就是 HDFS Erasure Coding、Ceph EC pool、AWS S3 IA 后端的核心招。代价是写入要算冗余、读取宕机时要重算——CPU 换空间的经典权衡。

踩过的坑

  1. 理论 1960 → 工业 1990s 滞后 30 年：1960 论文没给完整解码算法，要等 Berlekamp（1968）+ Massey（1969）把解码降到 O(n²)，再等 1980s 集成电路成熟，CD（1986）才用上。理论先行 → 算法补丁 → 硬件成熟 的三步台阶。

  2. RS 偏爱”突发错”，不偏爱”均匀比特错”：每 8 比特错 1 个 → 看起来都是 1 符号错，但每个都吃 1 个 t 名额，效率低。所以 5G 移动信道（白噪声）改用 LDPC，QR 码（区域污损）继续用 RS。

  3. RS 不直接处理比特，处理”符号”：底层是有限域 GF(2^m) 上的运算（加法 = XOR，乘法 = 查表）。新人想直接套整数运算，会发现”加完出现了不存在的数”——必须先理解有限域。

适用 vs 不适用场景

适用：

  • 突发错误信道（CD 划痕、闪存坏块、二维码污渍）
  • 已知”哪些位置坏了”的场景（分布式存储——磁盘宕机有 SMART 信号）→ erasure 模式纠错能力翻倍到 n - k
  • 短 / 中 block（n ≤ 255）+ 硬件资源受限（嵌入式、QR 扫描芯片）
  • 需要”确定性”解码（不像 LDPC 那种概率收敛可能 stall）

不适用：

  • 长 block（n > 10000）+ 接近 shannon-1948 极限要求 → LDPC（5G、Wi-Fi 6）
  • 5G 控制信道 → Polar Codes
  • 流式无固定 block 长度的场景 → Fountain Codes（LT、Raptor）
  • 单纯纠 1 比特 + 极简硬件 → Hamming 码（成本更低）

历史小故事（可跳过）

  • 1948：Shannon 的信道编码定理证明”足够好的纠错码存在”，但没构造。
  • 1950：Hamming 给出第一个能用的纠错码——只能纠 1 比特。
  • 1960：MIT Lincoln 实验室的 Reed 和 Solomon 在 J. SIAM 发了 4 页论文，给出参数任选的多项式构造。当时没人能高效解码。
  • 1968-1969：Berlekamp / Massey 把解码降到 O(n²)，可硬件化。
  • 1977：NASA 用 RS(255, 223) 装到 Voyager 1/2 上，至今仍在传数据。
  • 1982：飞利浦 / Sony 用双层 RS（CIRC）把 CD 标准化。
  • 1994：ISO 把 QR 码标准化，RS 当核心。
  • 2010s：Hadoop HDFS、Ceph、AWS S3 把 RS 当纠删码用，分布式存储省一半空间。

理论提出 → 算法成熟 → 工业落地，三步隔了 30 年。这种”超前论文沉睡几十年”在数学和算法领域很常见。

学到什么

  1. 冗余 ≠ 副本——RS 的冗余是”多项式上的额外取值”，不是简单复制。同样空间下，纠错能力远超副本。
  2. 符号 vs 比特 是 RS 抗突发错的关键——一片连续坏算几个符号错，不是几十个比特错。
  3. 解码比编码难——编码是”代入求值”，解码要”找出哪里坏了 + 修回来”，需要 syndrome / 错误定位多项式 / Chien 搜索 / Forney 公式四步配合。
  4. 理论存在性 → 构造算法 → 硬件可用 是工业落地的三步台阶；跨过任何一步都要等 10-20 年。

延伸阅读

关联

  • hamming-1950 —— 1 比特纠错的简化前身；RS 把它推广到任意符号尺寸 + 多个错 + 突发错
  • shannon-1948 —— 证明”好的纠错码存在”，RS 是其中一个达到 Singleton bound 的构造
  • aes —— 同样建立在有限域 GF(2^8) 上的算法，密码学版本
  • bitcoin —— 区块链地址（如 Bitcoin Cash CashAddr）用 RS 校验输入错字符

反向链接

  • bitcoin —— Bitcoin 白皮书
  • f4-2014 —— f4 — Facebook 把 90 天前的旧图片搬到一个省 40% 存储的仓库
  • hamming-1950 —— Hamming 纠错码
  • shannon-1948 —— Shannon 1948 — 信息论的诞生
  • sia —— Sia / Renterd — 主机持续打卡才能拿钱的去中心化云存储