Reed–Solomon 码

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

在有限域上实际恢复 ​

在 ${\mathbb{F}}_7$ 中取 $n=5,k=3$，评价点为 $0,1,2,3,4$。消息系数 $(1,2,1)$ 对应 $f(x)=1+2x+x^2$，求值并模 $7$ 化简得到码字 $(1,4,2,2,4)$。

若位置 $1,3$ 的符号擦除（这里位置用评价点标记），留下 $f(0)=1,f(2)=2,f(4)=4$。写 $f(x)=a+bx+c{x}^2$，则 $a=1$，另外两式为

第一式乘 $2$ 后为 $4b+c=2$；从第二式减去它得 $c=1$，再得 $2b=4$，即 $b=2$。因此恢复原消息，并补回两个擦除值。所有除法都取域中的逆元，例如 $2^{-1}=4$；这里没有实数拟合或数值舍入。

这个码的距离为 $3$，所以能恢复两处已知擦除，或纠正一处未知错误。若把最后的 $4$ 改成 $0$，接收词 $(1,4,2,2,0)$ 与原码字仅差一处；任何另一 RS 码字不可能也与它只差一处，否则两码字距离至多为 $2$。

一般地，知道任意 $k$ 个无错符号即可插值恢复 $f$；经典唯一译码可纠正至多 $\lfloor (n-k)/2\rfloor$ 个未知位置符号错误，或至多 $n-k$ 个已知位置擦除。混合出现 $e$ 处未知错误与 $s$ 处擦除时，保证条件为 $2e+s\le n-k$：删去擦除位置后，剩余码的距离至少为 $n-k+1-s$，只要该距离大于 $2e$，就不可能有两个码字同时落在接收词的 $e$ 错误范围内。

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

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

存储实现还要保证用于恢复的符号属于一致版本。RAID校验更新与写洞理路RAID校验更新与写洞RAID parity write hole · RAID 5 parity update · 校验阵列写洞通过四盘异或校验计算擦除重建和更新I/O，枚举数据与校验的持久组合，展示部分写入如何破坏未改块，并界定日志与部分校验保护的能力。以更简单的单异或校验阵列展示：只更新一个数据块而校验未同步持久，随后重建竟会把未修改的A5算成96。这里并未推翻编码的擦除恢复界，而是输入已不满足同一合法码字和正确幸存符号的前提；RS阵列同样需要单独设计更新与持久化协议。

改用线性化消息时，互异条件也必须升级 ​

Gabidulin码理路Gabidulin码与Moore求值Gabidulin code · Gabidulin evaluation code在底域独立的求值点上评价低q次数线性化消息，构造达到秩Singleton界的线性码，并证明最小距离与任意k个坐标的擦除恢复。把普通低次消息换成 $\sum _j{f}_j{X}^{q^j}$，并在 ${\mathbb{F}}_q$ 上独立的扩域元素处求值。非零消息的根空间维数受 $q$ 次数控制，由此得到输出秩下界；仅仅互异的点可能底域相关，不能照搬本页的点条件。

未知秩错误由线性化插值译码理路Gabidulin码的插值译码Gabidulin interpolation decoder · Linearized interpolation decoding用首一错误湮灭多项式建立扩域线性插值系统，经左因子形式复合除法与残差秩复核，返回唯一半径内码字或完整的无半径内码字结论。恢复，其最终检查为 $N=\mathrm{\Lambda }\circ f$ 的形式复合除法。复合通常不交换，扩域逐坐标缩放也未必保持秩；本页普通乘法和Hamming等距的操作不能不经证明地迁移。