Reed–Solomon 码

Reed–Solomon 码把消息看成低次数多项式，在有限域的多个不同点求值。低次多项式由足够多取值唯一确定，噪声只破坏部分取值时，剩余冗余仍可恢复原多项式。任意两个不同的次数小于 $k$ 的多项式至多在 $k-1$ 个点相同，所以长度 $n$ 的码最小距离为 $n-k+1$，恰好达到一般上界。它按“符号”纠错，每个符号可含多个 bit，特别适合把 burst 打包成少量符号错误的场景。

次数小于 3 的任意两个不同多项式之差次数至多为 2，最多在 2 个评价点为零，所以码字距离至少为 $n-2$。字段大小限制意味着长二元码不能直接用普通 RS 构造，常在扩域符号上工作。

在域 ${\mathbb{F}}_q$ 上取次数小于 $k$ 的 $f(x)$，码字为 $(f({\alpha }_1),\dots ,f({\alpha }_n))$。知道任意 $k$ 个无错符号即可插值恢复 $f$；经典唯一译码一般可纠正 $t=\lfloor (n-k)/2\rfloor$ 个未知位置符号错误，或至多 $n-k$ 个已知位置擦除。

求值点必须互异且 $n\le q$（扩展版本另论）。bit 错误如何映为符号错误取决于封装；若每个 bit 错落在不同符号，纠错能力与 burst 场景不同。超出唯一译码半径可采用列表译码公理库列表译码List decoding允许每个接收词对应一个受控候选列表，从而在组合意义上越过唯一译码半径。；Guruswami–Sudan 的插值—因式分解路线利用 RS 代数结构输出完整候选列表，但列表大小、可达半径与唯一译码保证不能混写。

RS 码是在 有限域公理库有限域Finite field · Galois field底层集合有限的域。 上按多项式取值构造的 线性码公理库线性码Linear code有限域向量空间中的线性子空间作为码字集合的信道码。，距离由 Hamming 距离公理库Hamming 距离Hamming distance两个等长字在对应位置不同的坐标数。衡量，唯一译码可用综合、Euclid/Berlekamp–Massey 等算法，列表译码则有不同输出接口与半径。光盘、二维码、存储阵列与分布式存储、卫星通信和秘密共享都利用其 MDS 性质。