Singleton 界

形式陈述 ​

设 $\mathrm{\Sigma }$ 是大小为 $q$ 的字母表，码 $C\subseteq {\mathrm{\Sigma }}^n$ 有 $M=|C|$ 个码字，最小Hamming 距离公理库Hamming 距离Hamming distance两个等长字在对应位置不同的坐标数。为 $d$。Singleton 界断言

$$M\le q^{n-d+1}.$$

等价地，若定义一般码的 $q$ 元信息量 $k_C={\log }_{q}M$，则 $k_C\le n-d+1$；$k_C$ 对非线性码不一定是整数，也不应直接称为向量空间维数。对有限域上的线性 $[n,k,d{]}_q$ 码，$M=q^k$，所以界化为

$$k\le n-d+1,\text{或}d\le n-k+1.$$

证明只需 puncturing。任意选定 $d-1$ 个坐标并从每个码字中删除，得到映射

$$\pi :C⟶{\mathrm{\Sigma }}^{n-d+1}.$$

该映射必须是单射：若两个不同码字删除后相同，它们只能在被删的 $d-1$ 个位置有差别，原距离至多为 $d-1$，与最小距离 $d$ 矛盾。像空间至多有 $q^{n-d+1}$ 个词，于是 $|C|$ 不超过这个数。删除恰好 $d-1$ 个坐标是证明的临界步；删除 $d$ 个坐标后，两个距离正好为 $d$ 的码字可能合并。

达到等号 $M=q^{n-d+1}$ 的码称为 maximum distance separable code，简称 MDS 码。线性情形中，MDS 条件等价于 $d=n-k+1$。把 $R=(1/n){\log }_{q}M$ 与相对距离 $\delta =d/n$ 代入，可得有限长度形式

$$R\le 1-\delta +\frac{1}{n},$$

因此任意码族的渐近率与相对距离满足 $R\le 1-\delta$。

直觉 ​

最小距离 $d$ 表示任意两份合法数据至少在 $d$ 个坐标上有差别。即使抹掉其中 $d-1$ 个坐标，仍应剩下至少一个差别，所以短化后的词仍能唯一标识原码字。剩余 $n-d+1$ 个 $q$ 元坐标最多容纳 $q^{n-d+1}$ 种标签，这便直接限制了消息数量。

与 Hamming 球打包不同，Singleton 证明不计算噪声球体积，也不围绕最近邻译码。它只问“删掉多少坐标仍不丢失码字身份”，所以对擦除恢复和 MDS 结构格外透明，但对很多一般码的数值限制可能较粗。

例子与边界 ​

$q$ 元重复码

$$C=\{(a,a,\dots ,a):a\in \mathrm{\Sigma }\}$$

有长度 $n$、码字数 $q$ 和最小距离 $n$。Singleton 界给 $q\le q^{n-n+1}=q$，恰好取等；任意保留一个坐标都能识别 $a$，删掉全部 $n$ 个坐标则不能。这一结构同时展示了等号与 puncturing 临界点，却以很低码率换取最大距离。

Reed–Solomon 码提供高维 MDS 实例。在 ${\mathbb{F}}_q$ 的 $n$ 个互异点上评价次数小于 $k$ 的多项式，得到 $[n,k,n-k+1{]}_q$ 码，正好达到线性 Singleton 界。其紧性来自任意 $k$ 个无错评价值都能插值恢复多项式；这也是“任意删除 $n-k$ 个坐标仍单射”的代数版本。

Singleton 是上界，不是存在定理。参数满足 $d\le n-k+1$ 只说明未被该界排除，不能保证给定 $q,n,k,d$ 的码存在；尤其 MDS 码的长度受字母表和代数结构限制，不能宣称所有等号参数都有构造。非线性码中 ${\log }_q|C|$ 不是维数，取整和可实现码字数也需单独处理。

这个界还不直接给译码算法或错误概率。达到 MDS 只说明距离最优；高效编码、唯一译码、列表译码以及特定信道上的软判决性能，仍是独立的算法与模型问题。

推论与应用 ​

Singleton 界把信道码公理库信道码Channel code把消息映为信道输入码字并从带噪输出恢复消息的编码—译码对。的冗余与最坏情形擦除能力联系起来。最小距离为 $d$ 的码可保证恢复 $d-1$ 个已知位置擦除；界说明要承受这么多擦除，至少需要相应数量的冗余坐标。MDS 码在这一意义下把每个冗余符号都用到极致。

它也为编码参数图提供一条简单外边界，并解释Reed–Solomon 码公理库Reed–Solomon 码Reed–Solomon code以低次数多项式在互异域元素处的取值向量形成的最大距离可分码。为何被称为最大距离可分。与 Hamming 界的球打包上界、Gilbert–Varshamov 的存在下界并列阅读，可以区分“所有码必须满足什么”“某些码能够达到什么”以及“达到参数后能否高效译码”三类结论。

参考资料

• Richard C. Singleton, “Maximum Distance q-nary Codes,” IEEE Transactions on Information Theory 10(2), 1964。
• F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes, North-Holland, 1977，Ch. 1。
• W. Cary Huffman and Vera Pless, Fundamentals of Error-Correcting Codes, Cambridge University Press, 2003，MDS codes and classical bounds。