辛格爾頓界

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