ギルバート=バルシャモフ限界

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動先: 案内検索

ギルバート=バルシャモフ限界: Gilbert-Varshamov bound)とは、符号線型符号とは限らない)のパラメータの限界を指す。「ギルバート=シャノン=バルシャモフ限界」(GSV限界)とも。

定理[編集]

q進数の符号 が長さ で最小ハミング距離 であるとき、その可能な最大サイズ(符号語の総数)を とする。なお、q進数の符号は、 個の要素の 上の線型符号である。

すると、次が成り立つ。

q が素数冪の場合、この限界を次の式が成り立つ最大の整数 k を使って と簡略化できる。

証明[編集]

符号 の符号語の長さを 、最小ハミング距離、最大符号語数を

とする。すると、全ての について少なくとも1つの符号語 が存在し、 の間のハミング距離 に対して次が成り立つ。

さもなくば、 を符号語として追加しても、その符号の最小ハミング距離 は変化しない( が最大であるという前提に矛盾する)。

それゆえ、 全体は を中心とする半径 の全ての和集合に含まれる。

ここで、各球の大きさは

となる。これは、n桁の符号語のうち最大 d-1 桁を(の中心である符号語の対応する桁の値から)変化させ、種類の異なる値とすることができる(符号はq進数で、 種類の値を取りうる)。したがって、次のような推論が成り立つ。

すなわち:

となる( であるため)。

関連項目[編集]