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

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

定理編集

q進数の符号 $\ C$ が長さ $n$ で最小ハミング距離 $d$ であるとき、その可能な最大サイズ（符号語の総数）を $\ A_{q}(n,d)$ とする。なお、q進数の符号は、 $q$ 個の要素の体 $\mathbb {F} _{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 \mathbb {F} _{q}^{n}$ について少なくとも1つの符号語 $c_{x}\in C$ が存在し、 $x$ と $c_{x}$ の間のハミング距離 $d(x,c_{x})$ に対して次が成り立つ。

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

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

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

\mathbb {F} _{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進数で、 $\mathbb {F} _{q}^{n}$ 種類の値を取りうる）。したがって、次のような推論が成り立つ。

{\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}}

すなわち:

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

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