辛格爾頓界

在 編碼理論 中, 以 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}.$

最大距離可分碼(MDS codes)

能達到 Singleton 界的分組碼稱為MDS (最大距離可分) codes。 這種碼的例子包括只有一個碼字的碼，由$(F_{q})^{n}$ 中全體向量構成的碼(最小距離為 1),包含一個奇偶校驗位的碼 (最小距離為 2) 以及它們的 對偶碼. 這些常被稱為 平凡 的 MDS 碼.

對於二元碼，所有 MDS 碼都是平凡的。

非平凡的 MDS 碼包括 里德-所羅門碼 和其擴展版本.

擴展閱讀

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

參考文獻

• R.C. Singleton. Maximum distance q-nary codes. IEEE Trans. Inf. Theory. 1964, 10: 116–118. doi:10.1109/TIT.1964.1053661. 

Further reading

• J.H. van Lint. Introduction to Coding Theory. GTM 86 2nd. Springer-Verlag. 1992: 61. ISBN 3-540-54894-7. 
• F.J. MacWilliams; N.J.A. Sloane. The Theory of Error-Correcting Codes. North-Holland. 1977: 33,37. ISBN 0-444-85193-3. 
• L. R. Vermani: Elements of algebraic coding theory, Chapman & Hall, 1996.