シングルトン限界

ウィキペディア

シングルトン限界

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2010/06/12 02:07 UTC 版)

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

定義

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

すると

が成り立つ。

証明

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

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

この新たな符号の長さは

n − (d − 1) = n − d + 1

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

q^{n − d + 1}

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

関連項目

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