跳转到内容

辛格尔顿界

维基百科,自由的百科全书

编码理论 中, 以 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