辛格尔顿界
在 编码理论 中, 以 Singleton 命名的 Singleton 界 是一个关于分组码容量的粗略估计。下面约定分组码 的码长为 , 容量为 , 码的最小距离为 。
Singleton 界的描述
编辑长度为 的分组码 的最小距离定义为:
其中 是 和 之间的汉明距离。表达式 表示长度为 ,极小距离为 的 元分组码所能容纳的码字个数的的最大值。
Singleton 界断言
证明
编辑首先,长度为 的 元码字最多有 个,因为每个位置上的字母有 个独立可选的值。
若 为任意一个最小距离为 的 元分组码。显然,所有的码字是两两不同的。如果我们删除掉这些码字的前 个字符,则新的码字仍然两两不同,因为 中原有码字间的汉明距离至少为 。因此新码的码字个数与旧码是相同的。
新码的码字具有长度
- ,
所以至多有
个不同码字. 由于旧码的码字个数 与新码相同,所以:
最大距离可分码(MDS codes)
编辑能达到 Singleton 界的分组码称为MDS (最大距离可分) codes。 这种码的例子包括只有一个码字的码,由 中全体向量构成的码(最小距离为 1),包含一个奇偶校验位的码 (最小距离为 2) 以及它们的 对偶码. 这些常被称为 平凡 的 MDS 码.
对于二元码,所有 MDS 码都是平凡的。[1]
扩展阅读
编辑注释
编辑参考文献
编辑- 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.