Gilbert–Varshamov 限界(Gilbert–Varshamov bound)とは、長さ $n$、最小距離 $d$ の $q$ 元符号で符号語が $q^n/V_q(n,d-1)$ 個以上のものが存在するという下からの限界で、$V_q(n,r)$ は半径 $r$ の Hamming 球の大きさである。極大な符号が半径 $d-1$ の球で全体を覆うことから従い、線形符号でも成り立つ。球の大きさを $q$ 元エントロピー関数 $H_q$ で評価すると、$0\le\delta\le1-1/q$ で情報率 $1-H_q(\delta)$ 以上、相対距離 $\delta$ 以上の符号の族があり、無作為な線形符号がほとんど確実にこれをみたす。2 元符号で GV 限界を改良できるかは未解決だが、$q\ge49$ が素数冪の平方のときは代数幾何符号が一部の $\delta$ で上回る。
Gilbert–Varshamov 限界(Gilbert–Varshamov bound)とは、長さ $n$、最小距離 $d$ の $q$ 元符号で、符号語が
$$
\frac{q^n}{V_q(n,d-1)},\qquad V_q(n,r)=\sum_{i=0}^{r}\binom ni(q-1)^i
$$
個以上のものが存在する、という下からの限界である。$V_q(n,r)$ は半径 $r$ の Hamming 球に入る語の個数で、限界は「距離 $d$ 未満に近い語を除きながら符号語を選んでいけば、球が全体を覆うまでは選び続けられる」という数え上げから出る。長さ $n\to\infty$ で情報率 $R$ と相対距離 $\delta=d/n$ の言葉に直すと $R\ge1-H_q(\delta)$ となり($H_q$ は $q$ 元エントロピー関数)、さらに無作為に選んだ線形符号がほとんど確実にこの限界をみたす。
上からの限界(Singleton、Hamming、Plotkin)との間には一般に隙間があり、2 元符号ではこの下界を漸近的に改良できるかどうかがわかっていない。
| 問い | 答え |
|---|---|
| 何の限界か | 最小距離 $d$ の符号の大きさ $A_q(n,d)$ の下界 |
| 主張 | $A_q(n,d)\ge q^n/V_q(n,d-1)$(Gilbert)、線形符号でも成り立つ(Varshamov) |
| 漸近形 | $0\le\delta\le1-1/q$ で $R\ge1-H_q(\delta)$ をみたす符号の族がある |
| 証明の道具 | 極大な符号による球の被覆、無作為な生成行列と和の上界 |
| 上回る例 | $q\ge49$ が素数冪の平方のとき、代数幾何符号が一部の $\delta$ で上回る |
$q\ge2$ とし、$q$ 個の文字からなる集合 $Q$ を固定する。$Q^n$ の元を長さ $n$ の 語 といい、語 $x,y$ の Hamming 距離 $d(x,y)$ を $x_i\ne y_i$ となる座標 $i$ の個数とする。$d$ は $Q^n$ の上の距離である(線形符号 の記事の補題「Hamming 距離の性質」と同じ議論)。
$Q^n$ の部分集合 $C$ を長さ $n$ の $q$ 元符号、その元を 符号語 という。$\lvert C\rvert\ge2$ のとき、相異なる符号語の距離の最小値を 最小距離 という。$1\le d\le n$ について、どの相異なる 2 つの符号語の距離も $d$ 以上である符号 $C$ の大きさの最大値を $A_q(n,d)$ と書く。
語 $x$ と整数 $0\le r\le n$ について、$B(x,r)=\{y\in Q^n\mid d(x,y)\le r\}$ を半径 $r$ の Hamming 球 という。$x$ と $i$ 個の座標で異なる語は、座標の選び方 $\binom ni$ と文字の選び方 $(q-1)^i$ で数えられるので
$$
\lvert B(x,r)\rvert=V_q(n,r)=\sum_{i=0}^{r}\binom ni(q-1)^i
$$
であり、中心によらない。$0\le x\le1$ について
$$
H_q(x)=x\log_q(q-1)-x\log_qx-(1-x)\log_q(1-x)
$$
($0\log_q0=0$)を $q$ 元エントロピー関数 という。
$H_q$ は $[0,1-1/q]$ で $0$ から $1$ まで単調に増え、$[1-1/q,1]$ で $1$ から $\log_q(q-1)$ まで減る。$q=2$ のときは $H_2(x)=-x\log_2x-(1-x)\log_2(1-x)$ で、Shannonエントロピー の 2 点分布の値である。$\lvert C\rvert=q^k$ の符号は $k$ 文字の情報を $n$ 文字で送るので、$R=\log_q\lvert C\rvert/n$ を 情報率、$\delta=d/n$ を 相対距離 という。
$1\le d\le n$ とする。どの相異なる 2 つの符号語の距離も $d$ 以上である符号 $C$ で、そのような符号の中で包含について極大なものは
$$
\lvert C\rvert\ge\frac{q^n}{V_q(n,d-1)}
$$
をみたす。とくに $A_q(n,d)\ge q^n/V_q(n,d-1)$ である。
$C$ は極大なので、どの語 $y\in Q^n\setminus C$ についても $C\cup\{y\}$ は条件をみたさず、$d(y,c)\le d-1$ となる $c\in C$ がある。$y\in C$ なら $y\in B(y,d-1)$ である。よって
$$
Q^n=\bigcup_{c\in C}B(c,d-1)
$$
であり、両辺の元の個数を比べて $q^n\le\lvert C\rvert\,V_q(n,d-1)$ となる。$Q^n$ は有限なので、条件をみたす符号(たとえば 1 語だけの符号)を含む極大なものがある。$\square$
証明は、語を 1 つずつ見て、それまでに選んだ符号語のどれとも距離 $d$ 以上なら選ぶ、という 貪欲な構成 がいつも限界以上の符号を返すことを示している。どの順に語を見ても結果は極大な符号になる。
$V_2(7,2)=1+7+21=29$ なので、Gilbert の限界は $A_2(7,3)\ge128/29\approx4.41$、すなわち $5$ 語以上を保証する。一方、符号語のまわりの半径 $1$ の球は互いに交わらないので $A_2(7,3)\le128/V_2(7,1)=16$ であり、Hamming符号 $[7,4,3]_2$ がこの上界に達する。
語を辞書式の順に見る貪欲な構成は、ちょうど $16$ 語の符号を返す。見る順を変えると結果は変わり、$16$ 語より少ない極大な符号も現れるが、thm-gv-gilbert によりどれも $5$ 語以上である。線形符号については、線形符号 の記事の定理「Gilbert–Varshamov の限界」が、$V_2(6,1)=7< 2^{7-4}$ から $[7,4,\ge3]_2$ 符号の存在を与え、この場合は最良の大きさ $16$ に届く。
漸近形に直すには、球の体積を $H_q$ で挟む。
$n\ge1$ とする。
1:$p=0$ なら両辺とも $1$ である。$0< p\le1-1/q$ とし、$r=\lfloor pn\rfloor$、$\lambda=p/((q-1)(1-p))$ とおく。$p\le1-1/q$ は $\lambda\le1$ と同値である。二項定理 から
$$
1=\sum_{i=0}^{n}\binom nip^i(1-p)^{n-i}\ge\sum_{i=0}^{r}\binom ni(q-1)^i(1-p)^n\lambda^i\ge V_q(n,r)\,(1-p)^n\lambda^{pn}
$$
である。最後の不等号は $i\le r\le pn$ と $\lambda\le1$ による。右辺の $(1-p)^n\lambda^{pn}=\bigl(p/(q-1)\bigr)^{pn}(1-p)^{(1-p)n}$ は $q^{-H_q(p)n}$ に等しい。
2:$p=m/n$ とし、$t_k=\binom nkp^k(1-p)^{n-k}$($0\le k\le n$)とおく。$p=0,1$ なら $t_m=1$ で主張は明らかなので、$0< m< n$ とする。$t_{k+1}/t_k=(n-k)m/((k+1)(n-m))$ であり、$k< m$ なら $(n-k)m>(n-m)m\ge(n-m)(k+1)$、$k\ge m$ なら $(n-k)m\le(n-m)m\le(n-m)(k+1)$ である。よって $t_k$ は $k=m$ で最大で、$n+1$ 個の和が $1$ なので $t_m\ge1/(n+1)$ である。$t_m=\binom nm(q-1)^m\cdot\bigl(p/(q-1)\bigr)^m(1-p)^{n-m}=\binom nm(q-1)^m\,q^{-H_q(p)n}$ から主張が従う。$\square$
$0\le\delta\le1-1/q$、$\varepsilon>0$ とし、$d_n=\max(1,\lceil\delta n\rceil)$ とおく。
$\delta< 1$ なので $d_n\le n$ であり、$d_n-1\le\lfloor\delta n\rfloor$ である。$V_q(n,r)$ は $r$ について増加するので、lem-gv-volume の 1 から
$$
V_q(n,d_n-1)\le V_q(n,\lfloor\delta n\rfloor)\le q^{H_q(\delta)n}.
$$
1:thm-gv-gilbert から $A_q(n,d_n)\ge q^n/V_q(n,d_n-1)\ge q^{(1-H_q(\delta))n}$ である。
2:$m\in\mathbb F_q^k\setminus\{0\}$ を固定する。$m_j\ne0$ となる $j$ をとると、$G$ の第 $j$ 行以外を固定して第 $j$ 行だけを動かせば $mG$ は $\mathbb F_q^n$ のすべての元を同じ回数ずつとる。よって $mG$ は $\mathbb F_q^n$ の上で一様に分布し、
$$
\Pr\bigl[\operatorname{wt}(mG)\le d_n-1\bigr]=\frac{V_q(n,d_n-1)}{q^n}\le q^{(H_q(\delta)-1)n}
$$
である($\operatorname{wt}$ は $0$ でない座標の個数)。$0$ でない $m$ は $q^k-1$ 個なので、和の上界から
$$
\Pr\bigl[\text{ある}\ m\ne0\ \text{で}\ \operatorname{wt}(mG)\le d_n-1\bigr]< q^{k}\,q^{(H_q(\delta)-1)n}\le q^{-\varepsilon n}.
$$
この事象が起こらなければ、$m\ne0$ について $mG\ne0$ なので $G$ の階数は $k$ であり、符号の $0$ でない元の重みはすべて $d_n$ 以上である。線形符号の最小距離は $0$ でない符号語の重みの最小値に等しい(線形符号 の記事の命題「最小距離と最小の重み」)ので、最小距離は $d_n$ 以上である。$\square$
2 は、線形符号が Gilbert の限界と漸近的に同じ情報率を達成するだけでなく、無作為に選んだ線形符号のほとんどすべてがそうであることを述べている。GRS25 は Theorem 4.2.1(p. 75)でこの形を述べ、§4.2(pp. 75–78)で貪欲な構成と無作為な生成行列による証明を与えている。一般の符号の場合は Gilbert、線形符号の場合は Varshamov による(同 §4.6, p. 92)。
$1\le d\le n$ とし、$t=\lfloor(d-1)/2\rfloor$ とおく。
$C$ を、相異なる符号語の距離がすべて $d$ 以上の符号とし、$M=\lvert C\rvert$ とおく。
1:符号語の最初の $n-d+1$ 個の座標が一致する 2 つの符号語は、残りの $d-1$ 座標でしか異ならないので距離が $d-1$ 以下になる。よって最初の $n-d+1$ 座標への写像は $C$ の上で単射で、$M\le q^{n-d+1}$ である。
2:$c\ne c'$ について $B(c,t)\cap B(c',t)\ni y$ なら $d(c,c')\le2t\le d-1$ となるので、球 $B(c,t)$($c\in C$)は互いに交わらない。元の個数を比べて $M\,V_q(n,t)\le q^n$ である。
3:$S=\sum_{c\ne c'}d(c,c')$(順序対の和)を 2 通りに評価する。どの対も $d$ 以上なので $S\ge M(M-1)d$ である。座標 $i$ ごとに、文字 $a$ を $i$ 番目にもつ符号語の個数を $m_{i,a}$ とすると、座標 $i$ で異なる順序対の個数は $M^2-\sum_am_{i,a}^2\le M^2-M^2/q$ である(Cauchy–Schwarz の不等式 $\sum_am_{i,a}^2\ge(\sum_am_{i,a})^2/q$)。よって $S\le n(1-1/q)M^2$ であり、$M(M-1)d\le n(1-1/q)M^2$、すなわち $M\bigl(qd-(q-1)n\bigr)\le qd$ となる。$\square$
lem-gv-volume の 2 を $m=t$ に当てると $V_q(n,t)\ge q^{H_q(t/n)n}/(n+1)$ なので、2 から $\frac1n\log_qA_q(n,d)\le1-H_q(t/n)+\frac{\log_q(n+1)}{n}$ である。$d=\lceil\delta n\rceil$ で $n\to\infty$ とすると $t/n\to\delta/2$ なので、情報率は漸近的に $1-H_q(\delta/2)$ 以下になる(漸近 Hamming 限界)。同様に 1 から $1-\delta$ 以下(漸近 Singleton 限界)である。3 を長さを縮めた符号に当てると、$\delta\le1-1/q$ でも情報率が漸近的に $1-q\delta/(q-1)$ 以下になること(漸近 Plotkin 限界)が導かれる(GRS25 Corollary 4.4.2, p. 81。この記事では証明しない)。2 元符号の場合のこの漸近形と、漸近形でない Plotkin 限界の等号を与える Hadamard 行列の符号は Plotkin限界 で証明している。
| $\delta$ | GV $1-H_2(\delta)$ | Hamming $1-H_2(\delta/2)$ | Plotkin $1-2\delta$ | Singleton $1-\delta$ |
|---|---|---|---|---|
| $0.05$ | $0.714$ | $0.831$ | $0.9$ | $0.95$ |
| $0.1$ | $0.531$ | $0.714$ | $0.8$ | $0.9$ |
| $0.2$ | $0.278$ | $0.531$ | $0.6$ | $0.8$ |
| $0.3$ | $0.119$ | $0.390$ | $0.4$ | $0.7$ |
| $0.4$ | $0.029$ | $0.278$ | $0.2$ | $0.6$ |
表は 2 元符号の場合で、GV の列は存在が保証される情報率、残りの列は超えられない情報率である。$0< \delta< 1/2$ では、$H_2$ が増加なので $H_2(\delta)>H_2(\delta/2)$、狭義の凹関数で $H_2(0)=0$、$H_2(1/2)=1$ なので $H_2(\delta)>2\delta>\delta$ であり、GV の値はどの上界よりも小さい。
| 外す条件 | 反例 | 成り立たなくなること |
|---|---|---|
| $\delta\le1-1/q$(thm-gv-asymptotic) | $q=2$、$\delta=0.6$ | $1-H_2(0.6)\approx0.029>0$ だが、$A_2(n,\lceil0.6n\rceil)\le6$ で情報率は $0$ に近づく |
| 符号が極大であること(thm-gv-gilbert) | $n=7$、$d=3$ の 1 語だけの符号 | $\lvert C\rvert\ge2^7/V_2(7,2)\approx4.41$ |
| $k\le(1-H_q(\delta)-\varepsilon)n$(thm-gv-asymptotic の 2) | $q=2$、$n=7$、$k=5$、$d=3$ | 最小距離 $3$ 以上の線形符号になる確率が正 |
| 球の半径 $t=\lfloor(d-1)/2\rfloor$(prop-gv-upper の 2) | 半径を $d-1$ に広げる。$n=7$、$d=3$ | $A_2(7,3)\le2^7/V_2(7,2)$ |
要点:各行で左の条件だけが外れていることを確かめる。
1 行目:$d=\lceil0.6n\rceil$ なら $2d-n\ge0.2n>0$ なので、prop-gv-upper の 3 から $A_2(n,d)\le2d/(2d-n)=1+n/(2d-n)\le6$ であり、大きさは有界である。$\delta=0.6>1/2$ なので lem-gv-volume の 1 が使えず、$1-H_2(\delta)$ は情報率の下界にならない。
2 行目:1 語の符号は条件をみたすが極大でない。極大なら $5$ 語以上ある(ex-gv-n7)。
3 行目:prop-gv-upper の 2 から $A_2(7,3)\le16< 2^5$ なので、$[7,5,\ge3]_2$ 符号はなく、確率は $0$ である。$(2^5-1)V_2(7,2)/2^7=31\cdot29/128>1$ で、和の上界も働かない。
4 行目:Hamming符号 は $16$ 語で、$2^7/V_2(7,2)\approx4.41$ を超える。半径 $d-1$ の球は符号語のまわりで重なりうる。
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する