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

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

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

すると、次が成り立つ。

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

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

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

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

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

ここで、各球の大きさは



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

すなわち:

となる（ であるため）。

 関連項目 
シングルトン限界
ハミング限界
ジョンソン限界
プロトキン限界

Category:符号理論
Category:数学に関する記事