シングルトン限界

シングルトン限界（英: Singleton bound）とは、符号のパラメータの比較的大雑把な限界値を指す。符号 "C" のパラメータとは、符号語の長さ formula_1、シンボル数（アルファベット）formula_2、最小ハミング距離 formula_3 である。
定理.
formula_4個の要素の体上の符号において、符号語の長さが formula_1 であり符号の最小ハミング距離が formula_3 であるとする。すなわち、任意の2つの符号語 formula_7 と formula_8 について formula_9 が成り立つとする。
このような符号の符号語数の最大値を formula_10 とする。このとき
が成り立つ。
証明.
q進数の符号で、符号語の長さが "n" なら、符号語数 "r" の最大は "qn" となる（符号語の各桁は他の桁とは独立に "q" 種類の値をとりうるため）。
"C" がq進数の符号であるとする。その全符号語 formula_12 はそれぞれ異なる。各符号語の先頭から formula_13 桁を除去したとき、全符号語の最小ハミング距離は formula_3 なので、残った符号語もそれぞれ異なる値でなければならない。したがって、符号語数 formula_2 は変化しない。
この新たな符号の長さは
となり、可能な最大符号語数は
となる。したがって、元の符号も符号語数について同じ限界を持つ。