Gilbert–Varshamov限界

同義語:Gilbert–Varshamov boundGilbert–Varshamovの限界GV限界Varshamov–Gilbert限界

概要

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$ で上回る。

$$\newcommand{C}[0]{\mathbb{C}} \newcommand{div}[0]{\mathbin{÷}} \newcommand{N}[0]{\mathbb{N}} \newcommand{Q}[0]{\mathbb{Q}} \newcommand{R}[0]{\mathbb{R}} \newcommand{Z}[0]{\mathbb{Z}} $$

前提知識: 誤り訂正符号, 線形符号, 二項係数

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)$ と書く。

Hamming 球と $q$ 元エントロピー関数

語 $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$ を 相対距離 という。

Gilbert の限界

Gilbert の限界

$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$ 以上なら選ぶ、という 貪欲な構成 がいつも限界以上の符号を返すことを示している。どの順に語を見ても結果は極大な符号になる。

長さ 7、最小距離 3 の 2 元符号

$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. $0\le p\le1-1/q$ なら $V_q(n,\lfloor pn\rfloor)\le q^{H_q(p)n}$ である。
  2. $0\le m\le n$ なら $\displaystyle\binom nm(q-1)^m\ge\frac{q^{H_q(m/n)n}}{n+1}$ である。

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$

Gilbert–Varshamov 限界(漸近形)

$0\le\delta\le1-1/q$、$\varepsilon>0$ とし、$d_n=\max(1,\lceil\delta n\rceil)$ とおく。

  1. すべての $n\ge1$ について $A_q(n,d_n)\ge q^{(1-H_q(\delta))n}$ である。
  2. $q$ が素数冪のとき、$1\le k\le(1-H_q(\delta)-\varepsilon)n$ をみたす $k$ について、$\mathbb F_q$ の成分の $k\times n$ 行列 $G$ を一様に無作為に選ぶと、$G$ の行が張る符号が次元 $k$、最小距離 $d_n$ 以上の線形符号になる確率は $1-q^{-\varepsilon n}$ より大きい。

$\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)。

上からの限界との比較

3 つの上界

$1\le d\le n$ とし、$t=\lfloor(d-1)/2\rfloor$ とおく。

  1. (Singleton)$A_q(n,d)\le q^{n-d+1}$。
  2. (Hamming)$A_q(n,d)\le q^n/V_q(n,t)$。
  3. (Plotkin)$qd>(q-1)n$ なら $A_q(n,d)\le qd/(qd-(q-1)n)$。

$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 の値はどの上界よりも小さい。

GV 限界を越えて

  • 大きな $q$。 $q\ge49$ が素数冪の平方のとき、代数曲線から作る $\mathbb F_q$ 上の代数幾何符号で、情報率 $R\ge1-\delta-1/(\sqrt q-1)$ をみたす線形符号の族があり、ある範囲の $\delta$ で GV 限界を上回る(Tsfasman–Vlăduţ–Zink TVZ82。GRS25 §4.6, p. 92 とその脚注 2 の紹介による。この記事では証明しない)。$q=49$ では直線 $1-\delta-1/6$ が $1-H_{49}(\delta)$ を上回るのはおよそ $0.365< \delta< 0.625$ の範囲で、平方数 $q=4,9,16,25$ では上回る $\delta$ はない。
  • 2 元符号。 2 元符号では GV 限界が知られている最良の下界であり(GRS25 p. 82)、最良の情報率と相対距離の関係は未解決である。GV 限界の上に乗る 2 元符号の族を明示的に構成することも未解決である(GRS25 Open Questions 8.3.1・8.3.2, p. 168)。上界の側は McEliece–Rodemich–Rumsey–Welch の限界まで改良されているが、$\delta$ が $1/2$ に近いところでも GV 限界との間に対数の因子の隙間が残っている(同 p. 167)。

反例:条件を外すと成り立たないこと

外す条件反例成り立たなくなること
$\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$ の球は符号語のまわりで重なりうる。

歴史と広がり

  • 名前の由来。 一般の符号の存在は Gilbert(Gil52)、線形符号の場合は Varshamov(Var57)による(GRS25 §4.6, p. 92)。線形符号 の記事の定理「Gilbert–Varshamov の限界」は、検査行列の列を 1 本ずつ選ぶ Varshamov 型の構成で、thm-gv-gilbert より少し強い $V_q(n-1,d-2)< q^{n-k}$ という条件を与える。
  • 誤り訂正との関係。 最小距離 $d$ の符号は $\lfloor(d-1)/2\rfloor$ 個の誤りを訂正できる(誤り訂正符号)。GV 限界は、相対距離 $\delta$ を保ったまま情報率が正の符号の族(漸近的に良い符号)が $q$ によらず存在することを保証する。
  • 確率的方法。 thm-gv-asymptotic の 2 は 確率的方法 の典型的な使い方で、存在だけでなく「ほとんどすべて」を示す。ただし無作為な符号は記述にも復号にも手間がかかる。
  • 完全符号。 prop-gv-upper の 2 の等号が成り立つ符号が 完全符号 で、ex-gv-n7 の Hamming 符号がその例である。

関連項目

参考文献

Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する