在 编码理论 中, 以 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| \le A_q(n,d) \leq q^{n-d+1}.
最大距离可分码(MDS codes)
能达到 Singleton 界的分组码称为MDS (最大距离可分) codes。 这种码的例子包括只有一个码字的码，由(F_q)^n 中全体向量构成的码(最小距离为 1),包含一个奇偶校验位的码 (最小距离为 2) 以及它们的 对偶码. 这些常被称为 平凡 的 MDS 码.
对于二元码，所有 MDS 码都是平凡的。
非平凡的 MDS 码包括 里德-所罗门码 和其扩展版本.
扩展阅读
*Gilbert-Varshamov bound
*Plotkin bound
*Hamming bound
*Johnson bound
*Griesmer bound
注释
参考文献
*
Further reading
*
*
- L. R. Vermani: Elements of algebraic coding theory, Chapman & Hall, 1996.
评论 (0)