辛格尔顿界

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

Singleton 界的描述

长度为 ${\displaystyle n}$ 的分组码 ${\displaystyle C}$ 的最小距离定义为：

${\displaystyle d=\min _{x,y\in C,x\neq y}d(x,y)}$

其中 ${\displaystyle d(x,y)}$ 是 ${\displaystyle x}$ 和 ${\displaystyle y}$ 之间的汉明距离。表达式 ${\displaystyle A_{q}(n,d)}$ 表示长度为 ${\displaystyle n}$，极小距离为 ${\displaystyle d}$ 的 ${\displaystyle q}$ 元分组码所能容纳的码字个数的的最大值。

Singleton 界断言

${\displaystyle A_{q}(n,d)\leq q^{n-d+1}.}$

证明

首先，长度为 ${\displaystyle n}$ 的 ${\displaystyle q}$ 元码字最多有 ${\displaystyle q^{n}}$ 个，因为每个位置上的字母有 ${\displaystyle q}$ 个独立可选的值。

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

新码的码字具有长度

${\displaystyle n-(d-1)=n-d+1}$，

所以至多有

${\displaystyle q^{n-d+1}}$

个不同码字. 由于旧码的码字个数 ${\displaystyle |C|}$ 与新码相同，所以：

${\displaystyle |C|\leq A_{q}(n,d)\leq q^{n-d+1}.}$

最大距离可分码(MDS codes)

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

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

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

扩展阅读

• Gilbert-Varshamov bound
• Plotkin bound
• Hamming bound
• Johnson bound
• Griesmer bound