ギルバート=バルシャモフ限界(英: Gilbert-Varshamov bound)とは、符号(線型符号とは限らない)のパラメータの限界を指す。「ギルバート=シャノン=バルシャモフ限界」(GSV限界)とも。
符号 の符号語の長さを 、最小ハミング距離を 、最大符号語数を
-
とする。すると、全ての について少なくとも1つの符号語 が存在し、 と の間のハミング距離 に対して次が成り立つ。
-
さもなくば、 を符号語として追加しても、その符号の最小ハミング距離 は変化しない( が最大であるという前提に矛盾する)。
それゆえ、 全体は を中心とする半径 の全ての球の和集合に含まれる。
-
ここで、各球の大きさは
-
となる。これは、n桁の符号語のうち最大 d-1 桁を(球の中心である符号語の対応する桁の値から)変化させ、 種類の異なる値とすることができる(符号はq進数で、 種類の値を取りうる)。したがって、次のような推論が成り立つ。
-
すなわち:
-
となる( であるため)。