形式陈述

取有限域 $\mathbb F_q$${\mathbb{F}}_q$ 中 $n\le q$$n\le q$ 个互异点 $\alpha_1,\ldots,\alpha_n$${\alpha }_1,\dots ,{\alpha }_n$，Reed–Solomon 码把次数小于 $k$$k$ 的多项式 $f$$f$ 映为 $(f(\alpha_1),\ldots,f(\alpha_n))$$(f({\alpha }_1),\dots ,f({\alpha }_n))$。它是 $[n,k,n-k+1]_q$$[n,k,n-k+1{]}_q$ 线性码，达到 Singleton 界，因而是 MDS 码。不同评价点和乘子产生广义 RS 码。

直觉

低次多项式由足够多取值唯一确定；噪声只破坏部分取值，剩余冗余可恢复原多项式。

例子与边界

次数小于 3 的多项式任意两个不同多项式之差次数至多 2，最多在 2 个评价点为零，所以码字距离至少 $n-2$$n-2$。经典唯一译码可纠正 $\lfloor(n-k)/2\rfloor$$\lfloor (n-k)/2\rfloor$ 个符号错误。字段大小限制意味着长二元码不能直接用普通 RS 构造，常在扩域符号上工作。

推论与应用

RS 码用于光盘、二维码、存储阵列、卫星通信和分布式存储。

参考资料

• Irving S. Reed and Gustave Solomon, Polynomial Codes over Certain Finite Fields, Journal of the Society for Industrial and Applied Mathematics 8(2), 1960，pp. 300–304。
• F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes, North-Holland, 1977，Chs. 1–10。