辛格尔顿界

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

Singleton 界的描述
长度为  的分组码  的最小距离定义为：

其中  是  和  之间的汉明距离。表达式
 表示长度为 ，极小距离为  的  元分组码所能容纳的码字个数的的最大值。

Singleton 界断言

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

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

新码的码字具有长度

，

所以至多有



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

最大距离可分码(MDS codes)

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

对于二元码，所有 MDS 码都是平凡的。see e.g. Vermani (1996), Proposition 9.2.

非平凡的 MDS 码包括 里德-所罗门码 和其扩展版本. see e.g. MacWilliams and Sloane, Ch. 11.

扩展阅读

Gilbert-Varshamov bound
Plotkin bound
Hamming bound
Johnson bound
Griesmer bound
注释

参考文献

Further reading


 L. R. Vermani: Elements of algebraic coding theory, Chapman & Hall, 1996.

Category:Coding theory
Category:Inequalities
Category:Articles containing proofs