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

Singleton 界的描述

编辑

长度为   的分组码   的最小距离定义为:

 

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

Singleton 界断言

 

证明

编辑

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

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

新码的码字具有长度

 

所以至多有

 

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

 

最大距离可分码(MDS codes)

编辑

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

对于二元码,所有 MDS 码都是平凡的。[1]

非平凡的 MDS 码包括 里德-所罗门码 和其扩展版本.[2]

扩展阅读

编辑

注释

编辑
  1. ^ see e.g. Vermani (1996), Proposition 9.2.
  2. ^ see e.g. MacWilliams and Sloane, Ch. 11.

参考文献

编辑

Further reading