Singleton 界

维基百科,自由的百科全书
跳转至: 导航搜索

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

Singleton 界的描述[编辑]

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

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

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

Singleton 界断言

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

证明[编辑]

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

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

新码的码字具有长度

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

所以至多有

q^{n-d+1}

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

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

最大距离可分码(MDS codes)[编辑]

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

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

非平凡的 MDS 码包括 里德-所罗门码 and their extended versions.[2]

扩展阅读[编辑]

Notes[编辑]

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

参考文献[编辑]

Further reading