シングルトン限界

シングルトン限界（英: Singleton bound）とは、符号のパラメータの比較的大雑把な限界値を指す。符号 C のパラメータとは、符号語の長さ ${\displaystyle n}$、シンボル数（アルファベット）${\displaystyle r}$、最小ハミング距離 ${\displaystyle d}$ である。

${\displaystyle q}$個の要素の体上の符号において、符号語の長さが ${\displaystyle n}$ であり符号の最小ハミング距離が ${\displaystyle d}$ であるとする。すなわち、任意の2つの符号語 ${\displaystyle w}$ と ${\displaystyle w'}$ について ${\displaystyle {\textrm {D}}_{H}(w,w')\geq d}$ が成り立つとする。

このような符号の符号語数の最大値を ${\displaystyle A_{q}(n,d)}$ とする。このとき

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

が成り立つ。

q進数の符号で、符号語の長さが n なら、符号語数 r の最大は qⁿ となる（符号語の各桁は他の桁とは独立に q 種類の値をとりうるため）。

C がq進数の符号であるとする。その全符号語 ${\displaystyle c\in C}$ はそれぞれ異なる。各符号語の先頭から ${\displaystyle d-1}$ 桁を除去したとき、全符号語の最小ハミング距離は ${\displaystyle d}$ なので、残った符号語もそれぞれ異なる値でなければならない。したがって、符号語数 ${\displaystyle r}$ は変化しない。

この新たな符号の長さは

${\displaystyle n-(d-1)=n-d+1}$

となり、可能な最大符号語数は

${\displaystyle q^{n-d+1}}$

となる。したがって、元の符号も符号語数について同じ限界を持つ。

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

• ギルバート＝バルシャモフ限界
• プロトキン限界
• ハミング限界
• ジョンソン限界