Reed–Solomon 码

Reed–Solomon 码（RS 码）由 Irving Reed 与 Gustave Solomon 在 1960 年提出，是最大距离可分（MDS）码的典范：把低次多项式在多个点上赋值，最小距离恰好撞上 Singleton 上界 d=n−k+1，距离—码率之间没有任何浪费。它在 GF(2^m) 上的符号级纠错能力转化为对突发比特错误的强力免疫，使其成为深空通信、CD/DVD、QR 码与光缆系统的工业支柱；GF(2^8) 上的 [255,223,33] 是 CCSDS 深空标准。量子码一侧的量子 MDS 构造沿袭其赋值思想。

多项式赋值构造

取 ${\mathbb{F}}_q$ 上 $n\le q$ 个互异点 ${\alpha }_1,\dots ,{\alpha }_n$ 与次数 $<k$ 的多项式集合，码字为赋值向量：

$\mathcal{C}=\left\{\right(f({\alpha }_1),f({\alpha }_2),\dots ,f({\alpha }_n)):f\in {\mathbb{F}}_q[x],\mathrm{deg}f<k\}.$

线性性显然（赋值映射线性）。维数恰为 $k$：两个次数 $<k$ 的多项式若在 $n\ge k$ 个点上赋值相同，其差是次数 $<k$ 却有至少 $k$ 个根的多项式，必为零多项式——赋值映射单射，像空间维数等于多项式空间维数 $k$Reed & Solomon 1960 (J. SIAM)。

最小距离：两行证明 d=n−k+1

上界：Singleton 界对任意码成立，$d\le n-k+1$（删除论证见classical-bounds）。

下界：非零多项式 $f$（$\mathrm{deg}f\le k-1$）在域上至多 $k-1$ 个根，故非零码字至多 $k-1$ 个分量为零：

$\mathrm{wt}(f({\alpha }_1),\dots ,f({\alpha }_n))\ge n-(k-1)=n-k+1.$

取等：取 $f(x)={\prod }_{i=1}^{k-1}(x-{\alpha }_i)$，它恰有 $k-1$ 个根，码字重量恰为 $n-k+1$。∎

于是 $d=n-k+1$ 精确成立，RS 码是 MDS 码：对每个长度 $n\le q$ 与维数 $k$，距离都坐在理论天花板（帕累托前沿）上。MDS 性的擦除版解读：任意 $k$ 个坐标的赋值由拉格朗日插值唯一重构多项式——纠 $n-k$ 个擦除。

突发错误：距离被”放大 m 倍”

在 ${\mathbb{F}}_{2^m}$ 上实现时，一个符号 = $m$ 比特。纠 $t=\lfloor (n-k)/2\rfloor$ 个符号错意味着：任何长度 $\le mt$ 比特的连续突发至多损坏 $t$ 个符号，必被纠正。例如 [255,223,33]（$t=16$，$q=2^8$）可吸收 128 比特长的任意突发——这是存储介质与衰落信道选 RS 作外码的根本原因，也是级联方案 RS+卷积 内外分工的依据（见concatenated-classical）。代价是 $n\le q$ 的长度限制：长码需要大域，二元信道上 RS 必须先做符号打包，码长以符号计。

译码：关键方程与三件套

错误向量 $\mathbf{e}$ 的非零位置集合与取值未知，译码归结为关键方程：已知位置 $j$ 满足 $e({\alpha }_j)=0$ 的信息不足以直接解出，但 $\mathrm{deg}e\le t$ 使方程组可解。经典流水线三件套Albert & Faist 2026 (arXiv)：

1. Berlekamp–Massey：迭代综合最短线性反馈移位寄存器，求错误定位多项式 $\Lambda (x)={\prod }_{j\in E}(1-x{\alpha }_j)$，复杂度 $O(t^2)$ 级；
2. Chien 搜索：穷举 ${\alpha }_j$ 检验 $\Lambda ({\alpha }_j^{-1})=0$，找出错误位置；
3. Forney 公式：由 $\Lambda (x)$ 与伴随多项式直接算出错误值 $e_j$。

整条流水线为 $O(n^2)$ 级的代数运算，硬件实现成熟。超出半径的一半时，Guruswami–Sudan 列表译码可对至多 $n-\sqrt{nk}$ 个错误输出含正确码字的候选列表——译码半径突破 $\lfloor (n-k)/2\rfloor$。

与 BCH 的关系和量子侧

RS 是 BCH 族的 $q$ 元满长特例：取 $n=q-1$、赋值点为全部非零元时，分圆陪集退化为单点，“连续根设计”与”多项式赋值”两种视角重合（见bch-codes）。量子一侧，Rains 把 MDS 概念移入量子码：量子 Singleton 界 $d\le n/2-k+2$ 的饱和码与 RS 的赋值结构密切相关Rains 1998 (IEEE Trans. Inf. Theory)，量子 MDS 码族见perfect-quantum-codes；现代 qLDPC 码（如环上的双变量自行车码）在”符号取自代数结构、约束由赋值定义”这一点上也延续着同一思想（见bivariate-bicycle）。

延伸阅读

• bch-codes
• galois-fields
• classical-bounds
• concatenated-classical
• perfect-quantum-codes