Singleton 界 | Codeboy's Blog

形式陈述

设 $\Sigma$ 是大小为整数 $q\ge2$ 的字母表， $n\ge1$ 为整数，码 $C\subseteq\Sigma^n$ 有 $M=|C|\ge2$ 个码字，最小Hamming 距离为 $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, \qquad\text{或}\qquad d\le n-k+1.

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

\pi:C\longrightarrow\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\le1-\delta+\frac1n,

例如固定字母表大小 $q$ ，对块长 $n\to\infty$ 的码族，若 $R_n=(1/n)\log_q M_n\to R$ 且 $d_n/n\to\delta$ ，取极限便得 $R\le1-\delta$ 。不假定这两个极限存在时，同一有限长度界给出 $\limsup_n R_n\le1-\liminf_n(d_n/n)$ 。

直觉

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

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

例子与边界

$q$ 元重复码

C=\{(a,a,\ldots,a):a\in\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 界把信道码的冗余与最坏情形擦除能力联系起来。最小距离为 $d$ 的码可保证恢复 $d-1$ 个已知位置擦除；界说明要承受这么多擦除，至少需要相应数量的冗余坐标。MDS 码在这一意义下把每个冗余符号都用到极致。

它也为编码参数图提供一条简单外边界，并解释Reed–Solomon 码为何被称为最大距离可分。与 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。

形式陈述 ​

反向链接

形式陈述