Singleton 界

在 编码理论 中, 以 Singleton 命名的 Singleton 界 是一个关于分组码容量的粗略估计。下面约定分组码 $C$ 的码长为 $n$, 容量为 $r$, 码的最小距离为 $d$。

Singleton 界的描述

长度为 $n$ 的分组码 $C$ 的最小距离定义为：

$d = \min_{x,y \in C, x \neq y} d(x,y)$

其中 $d(x,y)$ 是 $x$ 和 $y$ 之间的汉明距离。表达式 $A_{q}(n,d)$ 表示长度为 $n$，极小距离为 $d$ 的 $q$ 元分组码所能容纳的码字个数的的最大值。

Singleton 界断言

$A_q(n,d) \leq q^{n-d+1}.$

证明

首先，长度为 $n$ 的 $q$ 元码字最多有 $q^n$ 个，因为每个位置上的字母有 $q$ 个独立可选的值。

若 $C$ 为任意一个最小距离为 $d$ 的 $q$ 元分组码。显然，所有的码字是两两不同的。如果我们删除掉这些码字的前 $d-1$ 个字符，则新的码字仍然两两不同，因为 $C$ 中原有码字间的汉明距离至少为 $d$。因此新码的码字个数与旧码是相同的。

新码的码字具有长度

$n-(d-1)=n-d+1$，

所以至多有

$q^{n-d+1}$

个不同码字. 由于旧码的码字个数 $|C|$ 与新码相同，所以：

$|C| \le A_q(n,d) \leq q^{n-d+1}.$

最大距离可分码(MDS codes)

能达到 Singleton 界的分组码称为MDS (最大距离可分) codes。 这种码的例子包括只有一个码字的码，由$(F_q)^n$ 中全体向量构成的码(最小距离为 1),包含一个奇偶校验位的码 (最小距离为 2) 以及它们的 对偶码. 这些常被称为 平凡 的 MDS 码.

对于二元码，所有 MDS 码都是平凡的。

非平凡的 MDS 码包括 里德-所罗门码 and their extended versions.

扩展阅读

• Gilbert-Varshamov bound
• Plotkin bound
• Hamming bound
• Johnson bound
• Griesmer bound

参考文献

• R.C. Singleton. Maximum distance q-nary codes. IEEE Trans. Inf. Theory. 1964, 10: 116–118. doi:10.1109/TIT.1964.1053661. 

Further reading

• J.H. van Lint. Introduction to Coding Theory. GTM 86 2nd. Springer-Verlag. 1992. 61. ISBN 3-540-54894-7. 
• F.J. MacWilliams; N.J.A. Sloane. The Theory of Error-Correcting Codes. North-Holland. 1977: 33,37. ISBN 0-444-85193-3. 
• L. R. Vermani: Elements of algebraic coding theory, Chapman & Hall, 1996.