シングルトン限界のソースを表示

'''シングルトン限界'''（[[英語|英]]: '''Singleton bound'''）とは、[[符号]]のパラメータの比較的大雑把な限界値を指す。符号 ''C'' のパラメータとは、符号語の長さ <math>n</math>、シンボル数（[[アルファベット (計算機科学)|アルファベット]]）<math>r</math>、最小[[ハミング距離]] <math>d</math> である。

== 定理 ==
<math>q</math>個の要素の[[可換体|体]]上の符号において、符号語の長さが <math>n</math> であり符号の最小ハミング距離が <math>d</math> であるとする。すなわち、任意の2つの符号語 <math>w</math> と <math>w'</math> について <math>\textrm D_H(w,w')\ge d</math> が成り立つとする。

このような符号の符号語数の最大値を <math>A_q(n,d)</math> とする。このとき

:<math>A_q(n,d) \leq q^{n-d+1}</math>

が成り立つ。

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

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

この新たな符号の長さは

:<math>n-(d-1)=n-d+1</math> 

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

:<math>q^{n-d+1}</math> 

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

:<math>A_q(n,d) \leq q^{n-d+1}</math>

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

{{DEFAULTSORT:しんくるとんけんかい}}

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