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

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

定理

q進数の符号 $C$ が長さ $n$ で最小ハミング距離 $d$ であるとき、その可能な最大サイズ（符号語の総数）を $A_{q} (n, d)$ とする。なお、q進数の符号は、 $q$ 個の要素の体 $𝔽_{q}^{n}$ 上の線型符号である。

すると、次が成り立つ。

\begin{matrix} A_{q} (n, d) \geq \frac{q^{n}}{\sum_{j = 0}^{d - 1} (\binom{n}{j}) (q - 1)^{j}} \end{matrix}

q が素数冪の場合、この限界を次の式が成り立つ最大の整数 k を使って $A_{q} (n, d) \geq q^{k}$ と簡略化できる。

A_{q} (n, d) \geq \frac{q^{n}}{\sum_{j = 0}^{d - 2} (\binom{n - 1}{j}) (q - 1)^{j}}

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

| C | = A_{q} (n, d)

とする。すると、全ての $x \in 𝔽_{q}^{n}$ について少なくとも1つの符号語 $c_{x} \in C$ が存在し、 $x$ と $c_{x}$ の間のハミング距離 $d (x, c_{x})$ に対して次が成り立つ。

d (x, c_{x}) \leq d - 1

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

それゆえ、 $𝔽_{q}^{n}$ 全体は $c \in C$ を中心とする半径 $d - 1$ の全ての球の和集合に含まれる。

𝔽_{q}^{n} = \cup_{c \in C} B (c, d - 1)

ここで、各球の大きさは

\begin{matrix} \sum_{j = 0}^{d - 1} (\binom{n}{j}) (q - 1)^{j} \end{matrix}

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

\begin{matrix} | 𝔽_{q}^{n} | & = & | \cup_{c \in C} B (c, d - 1) | \\ \leq & \cup_{c \in C} | B (c, d - 1) | \\ = & | C | \sum_{j = 0}^{d - 1} (\binom{n}{j}) (q - 1)^{j} \end{matrix}

すなわち:

\begin{matrix} A_{q} (n, d) & \geq & \frac{q^{n}}{\sum_{j = 0}^{d - 1} (\binom{n}{j}) (q - 1)^{j}} \end{matrix}

となる（ $| 𝔽_{q}^{n} | = q^{n}$ であるため）。