辛格尔顿界

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

Singleton 界的描述

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

d = \min_{x, y \in C, x \neq y} d (x, y)

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

Singleton 界断言

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

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

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

新码的码字具有长度

n - (d - 1) = n - d + 1

，

所以至多有

q^{n - d + 1}

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

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

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

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

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

Further reading