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

ギルバート＝バルシャモフ限界（英: Gilbert-Varshamov bound）とは、符号（線型符号とは限らない）のパラメータの限界を指す。「ギルバート＝シャノン＝バルシャモフ限界」（GSV限界）とも。
定理.
q進数の符号 formula_1 が長さ formula_2 で最小ハミング距離 formula_3 であるとき、その可能な最大サイズ（符号語の総数）を formula_4 とする。なお、q進数の符号は、formula_5 個の要素の体 formula_6 上の線型符号である。
すると、次が成り立つ。
q が素数冪の場合、この限界を次の式が成り立つ最大の整数 k を使って formula_8 と簡略化できる。
証明.
符号 formula_10 の符号語の長さを formula_2、最小ハミング距離を formula_3、最大符号語数を
とする。すると、全ての formula_14 について少なくとも1つの符号語 formula_15 が存在し、formula_16 と formula_17 の間のハミング距離 formula_18 に対して次が成り立つ。
さもなくば、formula_16 を符号語として追加しても、その符号の最小ハミング距離 formula_3 は変化しない（formula_22 が最大であるという前提に矛盾する）。
それゆえ、formula_6 全体は formula_24 を中心とする半径 formula_25 の全ての球の和集合に含まれる。
ここで、各球の大きさは
となる。これは、"n"桁の符号語のうち最大 "d"-1 桁を（球の中心である符号語の対応する桁の値から)変化させ、formula_28種類の異なる値とすることができる（符号はq進数で、formula_6 種類の値を取りうる）。したがって、次のような推論が成り立つ。
すなわち:
となる（formula_32 であるため）。