ギルバート＝バルシャモフ限界のソースを表示

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

== 定理 ==
q進数の符号 <math>\ C</math> が長さ <math>n</math> で最小[[ハミング距離]] <math>d</math> であるとき、その可能な最大サイズ（符号語の総数）を <math>\ A_q(n,d)</math> とする。なお、q進数の符号は、<math>q</math> 個の要素の[[可換体|体]] <math>\mathbb{F}_q^n</math> 上の線型符号である。

すると、次が成り立つ。

:<math>
\begin{matrix}
\\
A_q(n,d) \geq \frac{q^n}{\sum_{j=0}^{d-1} \binom{n}{j}(q-1)^j} \\
\\
\end{matrix}
</math>

q が素数冪の場合、この限界を次の式が成り立つ最大の整数 k を使って <math>A_q(n,d)\ge q^k</math> と簡略化できる。

:<math>A_q(n,d) \geq \frac{q^n}{\sum_{j=0}^{d-2} \binom{n-1}{j}(q-1)^j}</math>

== 証明 ==
符号 <math>C</math> の符号語の長さを <math>n</math>、最小[[ハミング距離]]を <math>d</math>、最大符号語数を

:<math>|C|=A_q(n,d)</math>

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

:<math>d(x,c_x)\leq d-1</math>

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

それゆえ、<math>\mathbb{F}_q^n</math> 全体は <math>c \in C</math> を中心とする半径 <math>d-1</math> の全ての[[球]]の[[合併 (集合論)|和集合]]に含まれる。

:<math>\mathbb{F}_q^n =\cup_{c \in C} B(c,d-1) </math>

ここで、各球の大きさは

:<math>
\begin{matrix}
\sum_{j=0}^{d-1} \binom{n}{j}(q-1)^j \\
\end{matrix}
</math> 

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

:<math>
\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}
</math>

すなわち:

:<math>
\begin{matrix}
A_q(n,d) & \geq & \frac{q^n}{\sum_{j=0}^{d-1} \binom{n}{j}(q-1)^j} \\
\end{matrix}
</math>

となる（<math>|\mathbb{F}_q^n|=q^n</math> であるため）。

== 関連項目 ==
*[[シングルトン限界]]
*[[ハミング限界]]
*[[ジョンソン限界]]
*[[プロトキン限界]]

{{DEFAULTSORT:きるはとはるしやもふけんかい}}

[[Category:符号理論]]
[[Category:数学に関する記事]]