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

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

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

すると、次が成り立つ。

${\displaystyle {\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 を使って ${\displaystyle A_{q}(n,d)\geq q^{k}}$ と簡略化できる。

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

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

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

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

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

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

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

${\displaystyle \mathbb {F} _{q}^{n}=\cup _{c\in C}B(c,d-1)}$

ここで、各球の大きさは

${\displaystyle {\begin{matrix}\sum _{j=0}^{d-1}{\binom {n}{j}}(q-1)^{j}\\\end{matrix}}}$

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

${\displaystyle {\begin{matrix}|\mathbb {F} _{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}}}$

すなわち:

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

となる（${\displaystyle |\mathbb {F} _{q}^{n}|=q^{n}}$ であるため）。

• シングルトン限界
• ハミング限界
• ジョンソン限界
• プロトキン限界