ギルバート・ヴァルシャモフ境界

符号理論において、ギルバート・ヴァルシャモフ境界（エドガー・ギルバート^[1]および独立にロム・ヴァルシャモフ^{[2]による）は、（必ずしも}線形ではない）符号のサイズの境界である。ギルバート・シャノン・ヴァルシャモフ境界（またはGSV境界）と呼ばれることもあるが、「ギルバート・ヴァルシャモフ境界」という名前が圧倒的に一般的である。ヴァルシャモフは、線形符号の確率的方法を使用してこの境界を証明した。その証明の詳細については、線形符号のギルバート・ヴァルシャモフ境界を参照。

コード内の任意の2つの要素が少なくとも一定の距離離れている場合、コードには最小距離があることを思い出してください。 ${\displaystyle d}$${\displaystyle d}$

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

長さnと最小ハミング距離dを持つq元コードの最大可能サイズを表します( q元コードはq個の要素を持つ体上のコードです)。 ${\displaystyle C}$ ${\displaystyle \mathbb {F} _{q}}$

それから：

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

長さが でハミング距離が最小でサイズが最大であるコードがあるとします。 ${\displaystyle C}$${\displaystyle n}$ ${\displaystyle d}$

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

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

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

そうしないと、コードの最小ハミング距離を維持しながらx をコードに追加できるため、の最大性と矛盾します。 ${\displaystyle d}$${\displaystyle |C|}$

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

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

それぞれのボールの大きさは

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

なぜなら、コードワードの要素の最大 が（ボールの中心の対応する要素の値から）他の可能な値のいずれかに逸脱することを許容（またはを選択）できるからである（思い出してください：コードはq元であり、 内の値を取ります）。したがって、 ${\displaystyle d-1}$${\displaystyle n}$${\displaystyle (q-1)}$${\displaystyle \mathbb {F} _{q}^{n}}$

${\displaystyle q^{n}=\left|\mathbb {F} _{q}^{n}\right|=\left|\bigcup _{c\in C}B(c,d-1)\right|\leqslant \sum _{c\in C}|B(c,d-1)|=|C|\sum _{j=0}^{d-1}{\binom {n}{j}}(q-1)^{j}}$

つまり、

${\displaystyle A_{q}(n,d)=|C|\geqslant {\frac {q^{n}}{\sum _{j=0}^{d-1}{\binom {n}{j}}(q-1)^{j}}}.}$

qが素数累乗の場合、境界を次のように改善することができる。ここでkは最大の整数である。 ${\displaystyle A_{q}(n,d)\geq q^{k}}$

${\displaystyle q^{k}<{\frac {q^{n}}{\sum _{j=0}^{d-2}{\binom {n-1}{j}}(q-1 )^{j}}}.}$

• エリアス・バッサリゴ行き
• 線形符号に対するギルバート・ヴァルシャモフ境界
• グリースマー行き
• ハミング境界
• ジョンソン行き
• プロトキン縛り
• シングルトンバウンド