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

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動: 案内検索

ギルバート=バルシャモフ限界: 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)\ge 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 が存在し、xc_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 であるため)。

関連項目[編集]