查看“辛格尔顿界”的源代码

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

==Singleton 界的描述==
长度为 <math>n</math> 的分组码 <math>C</math> 的最小距离定义为：
:<math>d = \min_{x,y \in C, x \neq y} d(x,y)</math> 
其中 <math>d(x,y)</math> 是 <math>x</math> 和 <math>y</math> 之间的[[汉明距离]]。表达式
<math>A_{q}(n,d)</math> 表示长度为 <math>n</math>，极小距离为 <math>d</math> 的 <math>q</math> 元分组码所能容纳的码字个数的的最大值。

Singleton 界断言
:<math>A_q(n,d) \leq q^{n-d+1}.</math>

==证明==
首先，长度为 <math>n</math> 的 <math>q</math> 元码字最多有 <math>q^n</math> 个，因为每个位置上的字母有 <math>q</math> 个独立可选的值。

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

新码的码字具有长度

:<math>n-(d-1)=n-d+1</math>，

所以至多有

:<math>q^{n-d+1}</math> 

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

:<math>|C| \le A_q(n,d) \leq q^{n-d+1}.</math>

==最大距离可分码(MDS codes)==

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

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

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

==扩展阅读==

*[[Gilbert-Varshamov bound]]
*[[Plotkin bound]]
*[[Hamming bound]]
*[[Johnson bound]]
*[[Griesmer bound]]
==注释==
<references/>

==参考文献==
* {{cite journal | author=R.C. Singleton | title=Maximum distance q-nary codes | journal=IEEE Trans. Inf. Theory | volume=10 | pages=116–118 | year=1964 | doi=10.1109/TIT.1964.1053661 }} 
'''Further reading'''
* {{cite book | author=J.H. van Lint | authorlink=Jack van Lint | title=Introduction to Coding Theory | edition=2nd | publisher=Springer-Verlag | series=[[Graduate Texts in Mathematics|GTM]] | volume=86 | date=1992 | isbn=3-540-54894-7 | page=61 }}
* {{cite book | author=F.J. MacWilliams | authorlink=Jessie MacWilliams | coauthors=[[Neil Sloane|N.J.A. Sloane]] | title=The Theory of Error-Correcting Codes | publisher=North-Holland | date=1977 | isbn=0-444-85193-3 | pages=33,37 }}
* L. R. Vermani: Elements of algebraic coding theory, Chapman & Hall, 1996.

{{DEFAULTSORT:Singleton Bound}}
[[Category:Coding theory]]
[[Category:Inequalities]]
[[Category:Articles containing proofs]]