シングルトン限界

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

 定理 
個の要素の体上の符号において、符号語の長さが  であり符号の最小ハミング距離が  であるとする。すなわち、任意の2つの符号語  と  について  が成り立つとする。

このような符号の符号語数の最大値を  とする。このとき

が成り立つ。

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

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

この新たな符号の長さは



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



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

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

Category:符号理論
Category:不等式
Category:数学に関する記事