ギルバート＝バルシャモフ限界
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2015/04/29 05:04 UTC 版)
ギルバート＝バルシャモフ限界（英: Gilbert-Varshamov bound）とは、符号（線型符号とは限らない）のパラメータの限界を指す。「ギルバート＝シャノン＝バルシャモフ限界」（GSV限界）とも。
定理
q進数の符号 
が長さ 
で最小ハミング距離 
であるとき、その可能な最大サイズ（符号語の総数）を 
とする。なお、q進数の符号は、
個の要素の体 
上の線型符号である。
すると、次が成り立つ。
q が素数冪の場合、この限界を次の式が成り立つ最大の整数 k を使って 
と簡略化できる。
証明
符号 
の符号語の長さを 、最小ハミング距離を 、最大符号語数を
とする。すると、全ての 
について少なくとも1つの符号語 
が存在し、
と 
の間のハミング距離 
に対して次が成り立つ。
さもなくば、 を符号語として追加しても、その符号の最小ハミング距離 は変化しない（
が最大であるという前提に矛盾する）。
それゆえ、 全体は 
を中心とする半径 
の全ての球の和集合に含まれる。
ここで、各球の大きさは
となる。これは、n桁の符号語のうち最大 d-1 桁を（球の中心である符号語の対応する桁の値から)変化させ、
種類の異なる値とすることができる（符号はq進数で、 種類の値を取りうる）。したがって、次のような推論が成り立つ。
すなわち:
となる（
であるため）。
関連項目
ギルバート＝バルシャモフ限界と同じ種類の言葉
- ギルバート＝バルシャモフ限界のページへのリンク
