シングルトン限界

出典: フリー百科事典『ウィキペディア（Wikipedia）』

移動: 案内、検索

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

定義 [編集]

q進数の符号において、符号語の長さが $n$ であるとき、可能な最大符号語数を $A_q(n,d)$ とする。なお、q進数の符号は、 $q$ 個の要素の体上の符号である。2つの符号語間の最小ハミング距離を $d$ とする。すなわち、その符号内の任意の2つの符号語 $w$ と $w'$ について $\textrm D_H(w,w')\ge d$ が成り立つ。

すると

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

が成り立つ。

証明 [編集]

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

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

この新たな符号の長さは

$n-(d-1)=n-d+1$

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

$q^{n-d+1}$

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

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

関連項目 [編集]

「http://ja.wikipedia.org/w/index.php?title=シングルトン限界&oldid=46781099」から取得