Johnson 限界(Johnson bound)とは、最小距離 $d$ 以上の長さ $n$ の符号について、半径 $e$ の Hamming 球に入る符号語の個数を抑える上界で、$e/n< 1-\sqrt{1-d/n}$ なら $nd$ 個以下、2 元符号では $e/n< \frac12(1-\sqrt{1-2d/n})$ なら $2dn$ 個以下である。どちらの半径も最小距離の半分より大きく、一意の復号の範囲を越えても候補が多項式個に収まることを保証する。証明は符号語どうしの一致や距離の総和の二重計数と Cauchy–Schwarz の不等式により、同じ議論から重みが一定の 2 元符号の大きさの上界と Elias–Bassalygo の限界が出る。次元を下げる Johnson–Lindenstrauss の補題とは別の定理である。
Johnson 限界(Johnson bound)とは、最小距離 $d$ の符号について、半径 $e$ の Hamming 球に入る符号語の個数を評価する上界である。半径が最小距離の半分未満なら球には符号語が高々 1 つしか入らないが、Johnson 限界によれば、半径をそれより大きい Johnson 半径 未満にとっても、球に入る符号語は長さ $n$ の多項式個(たとえば $nd$ 個)以下である。長さ $n$ の符号で半径の割合 $\rho=e/n$ と相対距離 $\delta=d/n$ で言えば、
$$
\rho<1-\sqrt{1-\delta}
$$
なら球の中の符号語は $nd$ 個以下であり、2 元符号ではさらに広く $\rho< \frac12\bigl(1-\sqrt{1-2\delta}\bigr)$ まで同じ型の評価が成り立つ。証明はどちらも、球の中の符号語どうしの距離(または一致)の総和を二重計数する。同じ議論は、重みが一定の 2 元符号(定重み符号)の大きさの上界にもなり、さらに Elias–Bassalygo の限界を導く。
ベクトルの次元を下げる Johnson–Lindenstrauss の補題(Johnson–Lindenstraussの補題)や、平面幾何の Johnsonの定理 とは別の定理である。
| 問い | 答え |
|---|---|
| 何を数えるか | 半径 $e$ の Hamming 球に入る、最小距離 $d$ の符号の符号語の個数 |
| 主張 | $e/n<1-\sqrt{1-d/n}$ なら $nd$ 個以下、2 元では $e/n< J_2(d/n)$ なら $2dn$ 個以下 |
| 定重み符号 | $w^2-wn+s n>0$ なら $A(n,2s,w)\le s n/(w^2-wn+s n)$ |
| 証明の道具 | 一致・距離の総和の二重計数と Cauchy–Schwarz の不等式 |
| 応用 | リスト復号の半径、Elias–Bassalygo の限界 |
$q\ge2$ とし、$q$ 個の文字の集合 $Q$ を固定する。長さ $n$ の語、Hamming 距離 $d(x,y)$、半径 $e$ の Hamming 球 $B(y,e)=\{x\in Q^n: d(x,y)\le e\}$、その大きさ $V_q(n,e)$、$q$ 元エントロピー関数 $H_q$ は Gilbert–Varshamov限界 の記事の定義のとおりとする。符号 $C\subseteq Q^n$ は、相異なるどの 2 つの符号語の距離も $d$ 以上のとき 距離 $d$ 以上の符号 という。
重み $w$ の 2 つの語 $x,y$ の距離は $d(x,y)=2w-2\lvert\operatorname{supp}x\cap\operatorname{supp}y\rvert$($\operatorname{supp}$ は $1$ である座標の集合)なので偶数であり、距離 $2s$ 以上は $\lvert\operatorname{supp}x\cap\operatorname{supp}y\rvert\le w-s$ と同じである。$w=0$ の定重み符号は $0$ だけなので $A(n,2s,0)=1$ である。
$n\ge2$、$1\le w\le n$、$s\ge1$ とする。
$C$ を重み $w$、距離 $2s$ 以上の定重み符号とし、$M=\lvert C\rvert$、座標 $i$ が $1$ である符号語の個数を $m_i$ とする。符号語と、その $1$ である座標の組を数えて $\sum_im_i=Mw$ である。
1:座標 $i$ が $1$ である符号語から座標 $i$ を除くと、それらは座標 $i$ で一致していたので距離は変わらず、長さ $n-1$、重み $w-1$、距離 $2s$ 以上の定重み符号が $m_i$ 語得られる。よって $m_i\le A(n-1,2s,w-1)$ で、$Mw=\sum_im_i\le nA(n-1,2s,w-1)$ である。$M$ は整数なので主張が従う。
2:符号語の相異なる順序対 $(c,c')$ にわたって $\lvert\operatorname{supp}c\cap\operatorname{supp}c'\rvert$ を足した量を $T$ とする。各項は $w-s$ 以下なので $T\le M(M-1)(w-s)$ である。一方、座標 $i$ で両方が $1$ である順序対は $m_i(m_i-1)$ 個なので $T=\sum_im_i^2-\sum_im_i$ であり、Cauchy–Schwarzの不等式 から $\sum_im_i^2\ge(\sum_im_i)^2/n=M^2w^2/n$ である。よって
$$
\frac{M^2w^2}n-Mw\le M(M-1)(w-s)
$$
である。$M\ge1$ として $M$ で割り、整理すると $M\bigl(\frac{w^2}n-w+s\bigr)\le s$、すなわち $M(w^2-wn+s n)\le s n$ である。$w^2-wn+s n>0$ で割れば主張が従う($M=0$ なら明らかである)。$\square$
点 $\{1,\dots,7\}$ の Fano 平面の 7 本の直線 $\{1,2,4\},\{2,3,5\},\{3,4,6\},\{4,5,7\},\{5,6,1\},\{6,7,2\},\{7,1,3\}$ を、直線の点の座標を $1$ とする長さ $7$・重み $3$ の語と見る。相異なる 2 直線はちょうど 1 点で交わるので、距離は $2\cdot3-2=4$ である。よって $A(7,4,3)\ge7$ である。一方、thm-jb-cw の 2 は $s=2$ で $w^2-wn+s n=9-21+14=2>0$ から $A(7,4,3)\le14/2=7$ を与え、1 も $A(6,4,2)=3$(重み $2$、距離 $4$ の語は台が交わらないので $\lfloor6/2\rfloor$ 個以下で、$3$ 個の互いに素な対で等号)から $\lfloor7\cdot3/3\rfloor=7$ を与える。したがって $A(7,4,3)=7$ で、どちらの評価も等号になる。
2 の分母 $w^2-wn+s n$ が正であることは、$4s>n$ ならいつも成り立ち、$4s\le n$ なら $w/n$ が閉区間 $\bigl[\frac12(1-\sqrt{1-4s/n}),\ \frac12(1+\sqrt{1-4s/n})\bigr]$ の外にあることと同じで、重みが長さの半分から十分離れていることを求めている。次の節の定理は、この条件を「球の中の語」に置き換えたものである。
$C\subseteq Q^n$ を距離 $d$ 以上の符号、$y\in Q^n$、$0\le e\le n$ を整数とし、$t=n-e$ とおく。$t^2>n(n-d)$ なら
$$
\lvert B(y,e)\cap C\rvert\le\frac{n(t-n+d)}{t^2-n(n-d)}\le nd
$$
である。条件 $t^2>n(n-d)$ は $e/n< J(d/n)=1-\sqrt{1-d/n}$ と同値である。
$B(y,e)\cap C=\{c_1,\dots,c_M\}$ とし、$M\ge1$ とする($M=0$ なら明らかである)。座標 $k$ ごとに、$c_{i,k}=y_k$ となる $i$ の個数を $m_k$ とし、$\sigma=\sum_km_k$ とおく。$c_i$ は $y$ と $n-d(c_i,y)\ge t$ 個の座標で一致するので、$\sigma\ge Mt$ である。
相異なる $c_i,c_j$ は距離 $d$ 以上なので、一致する座標は $n-d$ 個以下である。座標 $k$ で $c_i$ と $c_j$ がともに $y$ と一致すれば $c_i$ と $c_j$ はそこで一致するので、そのような順序対 $(i,j)$($i\ne j$)を座標ごとに数えて
$$
\sum_km_k(m_k-1)\le M(M-1)(n-d)
$$
である。左辺は $\sum_km_k^2-\sigma\ge \sigma^2/n-\sigma$ である(Cauchy–Schwarzの不等式)。$g(x)=x^2/n-x$ とおくと、$Mt\ge n/2$ なら $g$ は $[n/2,\infty)$ で増加なので $g(Mt)\le g(\sigma)$ であり、$Mt< n/2$ なら $g(Mt)< 0$ である。どちらの場合も
$$
\frac{M^2t^2}n-Mt\le M(M-1)(n-d)
$$
である。$M$ で割って整理すると $M\bigl(t^2-n(n-d)\bigr)\le nt-n(n-d)=n(t-n+d)$ となり、$t^2-n(n-d)>0$ で割れば最初の不等号が出る。$t\le n$ なので分子は $nd$ 以下であり、分母は正の整数なので $1$ 以上である。これで 2 つ目の不等号が出る。
同値性:$t\ge0$ なので $t^2>n(n-d)$ は $t>\sqrt{n(n-d)}$、すなわち $e< n-\sqrt{n(n-d)}=n\bigl(1-\sqrt{1-d/n}\bigr)$ と同じである。$\square$
$e$ が最小距離の半分未満なら球の中の符号語は 1 つ以下である(誤り訂正符号 の定理「最小距離と誤りの訂正」)。thm-jb-free は、それより大きい半径でも、球の中の符号語が $nd$ 個以下に抑えられることを述べている。GRS25 Theorem 7.3.3(p. 142)は条件を $e\le n-\sqrt{n(n-d)}$ とし、個数の上界を $qnd$ とした形で述べ、Exercise 7.5(p. 152)で上界を $n$ に改良する別証明を演習にしている。
2 元符号では、一致の代わりに距離の総和を数えると、より大きい半径まで届く。
$C\subseteq\{0,1\}^n$ を距離 $d$ 以上の符号、$y\in\{0,1\}^n$、$0\le e\le n/2$ を整数とし、$(n-2e)^2>n(n-2d)$ とする。このとき
$$
\lvert B(y,e)\cap C\rvert\le\frac{2dn}{(n-2e)^2-n(n-2d)}\le2dn
$$
である。$d\le n/2$ のとき、条件 $(n-2e)^2>n(n-2d)$ は $e/n< J_2(d/n)$ と同値である。
$B(y,e)\cap C=\{c_1,\dots,c_M\}$ とし、$M\ge1$ とする。$x_i=c_i-y$(座標ごとの $\bmod2$ の差)とおくと、$d(x_i,x_j)=d(c_i,c_j)$ で、$\operatorname{wt}(x_i)=d(c_i,y)\le e$ である。座標 $k$ が $1$ である $x_i$ の個数を $m_k$ とし、$\bar e=\frac1M\sum_km_k=\frac1M\sum_i\operatorname{wt}(x_i)$ とおくと $0\le\bar e\le e$ である。
非順序対の距離の総和 $S=\sum_{i< j}d(x_i,x_j)$ を 2 通りに評価する。各対は $d$ 以上なので $S\ge\frac{M(M-1)}2d$ である。座標 $k$ で異なる対は $1$ の語と $0$ の語の対で $m_k(M-m_k)$ 個あるので、Cauchy–Schwarzの不等式 $\sum_km_k^2\ge(\sum_km_k)^2/n$ を使って
$$
S=\sum_km_k(M-m_k)=M^2\bar e-\sum_km_k^2\le M^2\Bigl(\bar e-\frac{\bar e^2}n\Bigr)
$$
である。2 つを合わせて $n$ を掛け、整理すると $M(M-1)dn\le2M^2(n\bar e-\bar e^2)$、すなわち
$$
M\bigl(dn-2n\bar e+2\bar e^2\bigr)\le dn
$$
である。ここで $dn-2n\bar e+2\bar e^2=\frac12\bigl((n-2\bar e)^2-n(n-2d)\bigr)$ であり、$0\le\bar e\le e\le n/2$ から $(n-2\bar e)^2\ge(n-2e)^2>n(n-2d)$ なので、これは正である。よって
$$
M\le\frac{2dn}{(n-2\bar e)^2-n(n-2d)}\le\frac{2dn}{(n-2e)^2-n(n-2d)}
$$
であり、最後の分母は正の整数なので $M\le2dn$ である。
同値性:$d\le n/2$ なら $n(n-2d)\ge0$ で、$n-2e\ge0$ なので条件は $n-2e>\sqrt{n(n-2d)}$、すなわち $e/n< \frac12\bigl(1-\sqrt{1-2d/n}\bigr)=J_2(d/n)$ と同じである。$\square$
これは GRS25 Theorem 7.3.1(p. 140)の $q=2$ の場合で、同書 pp. 140–141 の二重計数の証明を、個数の評価を明示した形に書いたものである。$d>n/2$ なら $n(n-2d)< 0$ なので、$e\le n/2$ のどの半径でも条件が成り立つ。この場合は Plotkin限界 により符号全体が $2d$ 語以下である。
$0< x\le\frac12$ なら $J_2(x)\ge J(x)$ であり、$0< x\le1$ なら $J(x)>\dfrac x2$ である。
$J(x)>x/2$:$x>0$ なら $\bigl(1-\frac x2\bigr)^2=1-x+\frac{x^2}4>1-x$ で、$1-\frac x2>0$ なので $1-\frac x2>\sqrt{1-x}$ である。
$J_2(x)\ge J(x)$:$r=\sqrt{1-2x}$ とおくと示すべきことは $\sqrt{1-x}\ge\frac{1+r}2$ である。両辺は正なので 2 乗して比べると、右辺の 2 乗は $\frac{1+2r+r^2}4=\frac{2-2x+2r}4$ なので、$1-x\ge\frac{1-x+r}2$、すなわち $1-x\ge r$ と同値である。$x\le1$ なので $1-x\ge0$ で、$(1-x)^2=1-2x+x^2\ge1-2x=r^2$ から従う。$\square$
| $\delta=d/n$ | $\delta/2$(一意の復号) | $J(\delta)$ | $J_2(\delta)$ |
|---|---|---|---|
| $0.1$ | $0.05$ | $0.0513$ | $0.0528$ |
| $0.2$ | $0.1$ | $0.1056$ | $0.1127$ |
| $0.3$ | $0.15$ | $0.1633$ | $0.1838$ |
| $0.4$ | $0.2$ | $0.2254$ | $0.2764$ |
| $0.5$ | $0.25$ | $0.2929$ | $0.5$ |
表の値は小数第 5 位で四捨五入した。$q$ 元符号では、GRS25 Theorem 7.3.1(p. 140)が $J_q(x)=\bigl(1-\frac1q\bigr)\bigl(1-\sqrt{1-\frac{qx}{q-1}}\bigr)$ の手前の半径で個数が $qdn$ 以下であることを述べ、Lemma 7.3.2(p. 142)で $J_q(x)\ge J(x)$ を示している。$q=2$ では $J_q=J_2$ であり、$q\to\infty$ で $J_q(x)\to J(x)$ である(この記事では $q\ge3$ の場合を証明しない)。
16 次の Sylvester 型の Hadamard 行列の行とその補語から作る、長さ $16$、$32$ 語、最小距離 $8$ の 2 元符号 $C$ を考える(Plotkin限界 の定理「Hadamard 行列から作る符号」の 1)。一意に復号できる半径は $\lfloor7/2\rfloor=3$ である。$n(n-2d)=0$ なので、$e\le7$ のすべてで thm-jb-binary の条件が成り立ち、上界は $2dn/(n-2e)^2=256/(16-2e)^2$ である。
| $e$ | $3$ | $4$ | $5$ | $6$ | $7$ |
|---|---|---|---|---|---|
| 上界 $256/(16-2e)^2$ | $2.56$ | $4$ | $7.11$ | $16$ | $64$ |
| 球の中の符号語の最大個数 | $1$ | $4$ | $6$ | $16$ | $16$ |
表の最後の行は $2^{16}$ 個の $y$ をすべて調べた値で、$e=4$ と $e=6$ では上界に達する。$e=6$ の等号は次のように確かめられる。座標を $\mathbb F_2^4$ の元 $x$ で番号付けると、Sylvester 型の行列の行は $x\mapsto u\cdot x$($u\in\mathbb F_2^4$)の値の列、補語は $x\mapsto u\cdot x+1$ の値の列である(Hadamard行列 の節「Sylvester の構成」)。$y$ を $f(x)=x_1x_2+x_3x_4$ の値の列(重み $6$)とする。
$W(u)=\sum_x(-1)^{f(x)+u\cdot x}$ は一致する座標の個数から異なる座標の個数を引いたものなので、$d(y,r_u)=(16-W(u))/2$ である。$W(u)$ は $(x_1,x_2)$ と $(x_3,x_4)$ の和に分かれ、$\sum_{x_1,x_2}(-1)^{x_1x_2+u_1x_1+u_2x_2}=2(-1)^{u_1u_2}$(4 項を書き出せばよい)なので、$W(u)=4(-1)^{u_1u_2+u_3u_4}=\pm4$ である。よって各 $u$ について $d(y,r_u)$ は $6$ か $10$ で、$d(y,\bar r_u)=16-d(y,r_u)$ は $10$ か $6$ である。$16$ 個の $u$ のそれぞれで $r_u,\bar r_u$ のちょうど一方が距離 $6$ にあるので、$B(y,6)$ には $16$ 個の符号語が入る。
Reed–Solomon符号 $\mathrm{RS}_7((0,1,\dots,6),2)$ は $[7,2,6]_7$ 符号で、$n-d=1$ である。thm-jb-free は $t^2>7$、すなわち $t\ge3$ で使え、$t=3$($e=4$)のとき球の中の符号語は $7\cdot2/(9-7)=7$ 個以下である。一意に復号できるのは $e\le\lfloor5/2\rfloor=2$ までなので、Johnson 限界は 2 つ多い誤りまで「候補が少ない」ことを保証する。すべての $y\in\mathbb F_7^7$ を調べると、$e=4$ の球の中の符号語は最大 $6$ 個である。一般に $[n,k]$ の Reed–Solomon 符号では $n-d=k-1$ なので、thm-jb-free の条件は「$y$ と $t>\sqrt{n(k-1)}$ 個の座標で一致する」となる。この範囲の候補をすべて多項式時間で求めるのが リスト復号 の記事の Guruswami–Sudan の方法である。
Johnson 限界は「どの球にも符号語が少ない」ことを述べる。一方、符号語が多ければ、平均をとるとどこかの球には符号語が多く入る。2 つを合わせると符号の大きさの上界が出る。
$C\subseteq Q^n$ と $0\le e\le n$ について、$\lvert B(y,e)\cap C\rvert\ge\lvert C\rvert\,V_q(n,e)/q^n$ をみたす $y\in Q^n$ がある。
$y\in B(c,e)$ と $c\in B(y,e)$ は同じことなので、$\sum_{y\in Q^n}\lvert B(y,e)\cap C\rvert=\sum_{c\in C}\lvert B(c,e)\rvert=\lvert C\rvert\,V_q(n,e)$ である。$q^n$ 個の項の和なので、最大の項は平均 $\lvert C\rvert V_q(n,e)/q^n$ 以上である。$\square$
$0\le\delta\le\frac12$ とし、$1\le d_n\le n$ が $d_n/n\to\delta$ をみたすとする。このとき
$$
\limsup_{n\to\infty}\frac1n\log_2A_2(n,d_n)\le1-H_2\bigl(J_2(\delta)\bigr)
$$
である。
$d_n>n/2$ となる $n$ では、Plotkin限界 の定理「Plotkin 限界」の 1 から $A_2(n,d_n)\le2d_n\le2n$ である。$d_n\le n/2$ となる $n$ について、$x_n=J_2(d_n/n)>0$、$e_n=\lceil nx_n\rceil-1$ とおくと、$0\le e_n< nx_n\le n/2$ である。$C$ を長さ $n$、距離 $d_n$ 以上の符号とすると、lem-jb-average と thm-jb-binary から、ある $y$ について
$$
\frac{\lvert C\rvert\,V_2(n,e_n)}{2^n}\le\lvert B(y,e_n)\cap C\rvert\le2d_nn\le2n^2
$$
である。Gilbert–Varshamov限界 の記事の補題「球の体積の評価」の 2 から $V_2(n,e_n)\ge\binom n{e_n}\ge2^{H_2(e_n/n)n}/(n+1)$ なので、
$$
\frac1n\log_2\lvert C\rvert\le1-H_2\Bigl(\frac{e_n}n\Bigr)+\frac{\log_2\bigl(2n^2(n+1)\bigr)}n
$$
である。$\lvert e_n/n-x_n\rvert\le1/n$ で、$J_2$ と $H_2$ は連続なので、$e_n/n\to J_2(\delta)$ であり、右辺は $1-H_2(J_2(\delta))$ に収束する。$d_n>n/2$ となる $n$ の側は $\frac1n\log_2(2n)\to0\le1-H_2(J_2(\delta))$ である($H_2\le1$)。$\square$
| $\delta$ | $0.1$ | $0.2$ | $0.3$ | $0.4$ |
|---|---|---|---|---|
| Elias–Bassalygo $1-H_2(J_2(\delta))$ | $0.7019$ | $0.4920$ | $0.3117$ | $0.1495$ |
同じ $\delta$ での漸近 Hamming 限界・漸近 Plotkin 限界の値(Gilbert–Varshamov限界 の節「上からの限界との比較」の表)と比べると、表の 4 つの $\delta$ ではいずれも Elias–Bassalygo の限界が最も小さい(GRS25 p. 161 は、それまでに扱ったどの上界よりも強いと述べている)。$q$ 元の形 $R\le1-H_q(J_q(\delta))+o(1)$ は GRS25 Theorem 8.1.1(p. 161)にあり、証明は上と同じく平均の球(同 Lemma 8.1.2)と $q$ 元の Johnson 限界を組み合わせる。
| 外す条件 | 反例 | 成り立たなくなる結論 |
|---|---|---|
| $w^2-wn+s n>0$(thm-jb-cw の 2) | $n=6$、$w=2$、$s=1$ | $A(n,2s,w)\le s n/(w^2-wn+s n)$ |
| 2 元であること(thm-jb-binary) | $[6,3,4]_7$ の Reed–Solomon 符号、$e=3$ | 球の中の符号語が $2dn/((n-2e)^2-n(n-2d))$ 個以下 |
| $t^2>n(n-d)$(thm-jb-free) | $[4,2,3]_7$ の Reed–Solomon 符号、$y=0$、$e=3$ | 球の中の符号語が $nd$ 個以下 |
| $e\le n/2$(thm-jb-binary) | 長さ $8$・$16$ 語・最小距離 $4$ の符号、$e=8$ | 球の中の符号語が $2dn/((n-2e)^2-n(n-2d))$ 個以下 |
要点:各行で、外した条件のほかは仮定をみたし、右の列の上界を超える個数が現れる。
1 行目:$w^2-wn+s n=4-12+6=-2$ で、式の値は $-3$ だが、重み $2$ の長さ $6$ の語 $\binom62=15$ 個はどの 2 つも距離 $2$ 以上なので $A(6,2,2)=15$ である。
2 行目:評価点 $1,\dots,6$、$k=3$ の $\mathbb F_7$ 上の Reed–Solomon 符号は $n=6$、$d=4$ で、$e=3\le n/2$、$(n-2e)^2=0>n(n-2d)=-12$ なので 2 元の場合の式の値は $48/12=4$ である。lem-jb-average から、ある $y$ で半径 $3$ の球の中の符号語は $343\cdot V_7(6,3)/7^6=4897/343>14$ 個以上、すなわち $15$ 個以上ある(すべての $y$ を調べると最大は $20$ 個)。
3 行目:評価点 $0,1,2,3$、$k=2$ の $\mathbb F_7$ 上の Reed–Solomon 符号は $n=4$、$d=3$ で、$t=1$ なので $t^2=1\le n(n-d)=4$ である。$y=0$ から距離 $3$ 以下の符号語は、1 次以下の多項式 $a+bx$ で $0,1,2,3$ のどれかを根にもつものである。$b\ne0$ なら根 $-a/b$ を $\{0,1,2,3\}$ から選んで $4\cdot6=24$ 個、$b=0$ なら $a=0$ の $1$ 個で、計 $25>nd=12$ 個である。
4 行目:Plotkin限界 の定理「Hadamard 行列から作る符号」の 1 を $N=8$ に当てた符号で、$n(n-2d)=0$、$(n-2e)^2=64>0$ だが $e=8>n/2$ である。半径 $8$ の球は全体なので $16$ 個入り、式の値 $64/64=1$ を超える。
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する