Plotkin 限界(Plotkin bound)とは、長さ $n$、最小距離 $d$ の 2 元符号の大きさを、$2d>n$ のとき $A_2(n,d)\le2\lfloor d/(2d-n)\rfloor$、$n=2d$ のとき $A_2(2d,d)\le4d$ で抑える上からの限界である。符号語の対の距離の総和を、最小距離からは下に、各座標の $0$ と $1$ の個数からは上に評価して比べる二重計数で示され、奇数の $d$ では検査の桁を付けてさらに強い形になる。次数 $2d$ の Hadamard 行列があれば、それから作る符号で $n=2d$、$2d-1$、$2d-2$ のときに等号が成り立つ。長さを縮めた符号に当てると、相対距離 $\delta$ の 2 元符号の族の情報率は漸近的に $\max(1-2\delta,0)$ 以下であることがわかる。
前提知識: 誤り訂正符号, Gilbert–Varshamov限界, Hadamard行列
Plotkin 限界(Plotkin bound)とは、最小距離 $d$ が長さ $n$ の半分を超える 2 元符号の大きさを
$$
A_2(n,d)\le2\left\lfloor\frac{d}{2d-n}\right\rfloor\qquad(2d>n)
$$
で抑える上からの限界である。符号語の対の距離を全部足した量を、最小距離からは下に、各座標の $0$ と $1$ の個数からは上に評価して比べる、という二重計数から出る。距離がちょうど長さの半分のときは $A_2(2d,d)\le4d$ となり、次数 $2d$ の Hadamard 行列があれば、それから作る符号で $n=2d$、$2d-1$、$2d-2$ のときに等号が成り立つ。さらに長さを縮めた符号に当てると、相対距離 $\delta\le1/2$ の 2 元符号の族の情報率が漸近的に $1-2\delta$ 以下であることがわかる。
| 問い | 答え |
|---|---|
| 何の限界か | 最小距離 $d$ の 2 元符号の大きさ $A_2(n,d)$ の上界 |
| 主張 | $2d>n$ なら $A_2(n,d)\le2\lfloor d/(2d-n)\rfloor$、$A_2(2d,d)\le4d$ |
| 証明の道具 | 対の距離の総和の二重計数、偶奇による場合分け |
| 等号 | Hadamard 行列の行とその補語から作る符号 |
| 漸近形 | 情報率は $\max(1-2\delta,0)$ 以下 |
$\{0,1\}^n$ の元を長さ $n$ の 語 といい、語 $x,y$ の Hamming 距離 $d(x,y)$ を $x_i\ne y_i$ となる座標 $i$ の個数、重み $\operatorname{wt}(x)$ を $1$ である座標の個数とする。$\{0,1\}^n$ の部分集合を 2 元符号、その元を符号語といい、$1\le d\le n$ について、相異なるどの 2 つの符号語の距離も $d$ 以上である 2 元符号の大きさの最大値を $A_2(n,d)$ と書く(Gilbert–Varshamov限界 の記事の定義「符号と最小距離」の $q=2$ の場合)。語 $x$ のすべての座標を入れ替えた語を 補語 といい $\bar x$ と書く。$d(x,\bar y)=n-d(x,y)$ である。
$A_2(n,1)=2^n$(全体の符号)であり、$A_2(n,2)=2^{n-1}$ である(重みが偶数の語の全体が最小距離 $2$ をもち、Singleton の限界 $A_2(n,d)\le2^{n-d+1}$ と一致する。Singleton の限界は Gilbert–Varshamov限界 の記事の命題「3 つの上界」の 1)。Plotkin 限界が効くのは距離の大きい側である。
$C\subseteq\{0,1\}^n$ を $M$ 語の符号とし、$S=\sum_{(c,c')}d(c,c')$ を符号語の順序対の全体にわたる和とする。$i$ 番目の座標が $1$ である符号語の個数を $m_i$ とすると
$$
S=2\sum_{i=1}^nm_i(M-m_i)\le2n\left\lfloor\frac{M^2}4\right\rfloor
$$
である。
$d(c,c')$ は $c,c'$ が異なる座標の個数なので、$S$ は「座標 $i$ と、$i$ 番目が異なる順序対 $(c,c')$」の組の個数である。座標 $i$ を固定すると、そのような順序対は $1$ を持つ符号語と $0$ を持つ符号語の組で、向きを入れて $2m_i(M-m_i)$ 個ある。整数 $m$ について $m(M-m)=\frac{M^2-(M-2m)^2}4$ であり、$M$ が偶数なら $(M-2m)^2\ge0$、奇数なら $(M-2m)^2\ge1$ なので、$m(M-m)\le\lfloor M^2/4\rfloor$ である。$\square$
$1\le d\le n$ とする。
1:$C$ を、相異なる符号語の距離がすべて $d$ 以上の符号とし、$M=\lvert C\rvert$ とおく。$d\le n$ から $d\ge2d-n$ なので右辺は $2$ 以上であり、$M\le1$ なら主張は明らかである。$M\ge2$ とする。順序対の和 $S$ は相異なる順序対 $M(M-1)$ 個のそれぞれが $d$ 以上なので $S\ge M(M-1)d$ である。lem-plk-sum と合わせて場合を分ける。
1 の証明の要は、座標ごとの寄与 $m(M-m)$ が $M$ の偶奇で $M^2/4$ か $(M^2-1)/4$ に抑えられることである。$q$ 元符号では同じ二重計数と Cauchy–Schwarz の不等式から $qd>(q-1)n$ のとき $A_q(n,d)\le qd/(qd-(q-1)n)$ が出る(Gilbert–Varshamov限界 の記事の命題「3 つの上界」の 3。GRS25 Theorem 4.4.1, p. 81 はこれを実ベクトルの配置の補題から示し、Exercise 4.17, p. 92 で二重計数の証明を演習にしている)。$q=2$ では右辺は $2d/(2d-n)$ で、1 はこれを偶奇の分だけ改良したものである。
奇数の $d$ では、1 語ずつに検査の桁を付けることで、さらに強い形になる。
$d$ が奇数で $1\le d\le n$ なら $A_2(n,d)=A_2(n+1,d+1)$ である。
$\le$:最小距離 $d$ 以上の長さ $n$ の符号の各語 $x$ の末尾に $\operatorname{wt}(x)$ の偶奇(偶数なら $0$、奇数なら $1$)を付ける。$d(x,y)=\operatorname{wt}(x)+\operatorname{wt}(y)-2\lvert\{i: x_i=y_i=1\}\rvert$ なので、$d(x,y)$ と $\operatorname{wt}(x)+\operatorname{wt}(y)$ の偶奇は等しい。$d(x,y)\ge d+1$ なら付けたあとも $d+1$ 以上である。$d(x,y)=d$ は奇数なので $\operatorname{wt}(x)$ と $\operatorname{wt}(y)$ の偶奇が異なり、付けた桁が異なるので距離は $d+1$ になる。
$\ge$:最小距離 $d+1$ 以上の長さ $n+1$ の符号の各語から最後の座標を除くと、距離は高々 $1$ しか減らないので $d$ 以上のままで、$d\ge1$ なので相異なる語は相異なる語に写る。$\square$
$d$ を奇数とする。
lem-plk-parity により $A_2(n,d)=A_2(n+1,d+1)$ である。1:$2(d+1)>n+1$ は $2d+1>n$ と同値なので、thm-plk-main の 1 を長さ $n+1$、距離 $d+1$ に当てればよい。2:$n=2d+1$ なら $n+1=2(d+1)$ なので、thm-plk-main の 2 から $A_2(2d+2,d+1)\le4(d+1)$ である。$\square$
| $(n,d)$ | 限界 | $A_2(n,d)$ | 等号を与える符号 |
|---|---|---|---|
| $(8,4)$ | $4d=16$ | $16$ | 位数 $8$ の Hadamard 行列から(thm-plk-hadamard の 1) |
| $(7,4)$ | $2\lfloor4/1\rfloor=8$ | $8$ | 同じ行列から(thm-plk-hadamard の 2) |
| $(6,4)$ | $2\lfloor4/2\rfloor=4$ | $4$ | 同じ行列から(thm-plk-hadamard の 3) |
| $(5,3)$ | cor-plk-odd:$2\lfloor4/2\rfloor=4$ | $4$ | $(6,4)$ の符号の最後の座標を除く |
| $(4,3)$ | cor-plk-odd の 1:$2\lfloor 4/3\rfloor=2$ | $2$ | $\{0000,1110\}$ |
どの行でも限界に達する符号があるので、限界がそのまま $A_2(n,d)$ の値である。$(5,3)$ に thm-plk-main の 1 をそのまま当てると $2\lfloor3/1\rfloor=6$ にしかならず、cor-plk-odd の改良が効いている。
Plotkin 限界の等号は、行どうしが直交する $\pm1$ 行列、すなわち Hadamard行列 から作る符号で達成される。$\pm1$ の列を $1\mapsto0$、$-1\mapsto1$ で 2 元の語に読み替えると、2 つの行の内積は「一致する座標の個数 $-$ 異なる座標の個数」なので、長さ $N$ の 2 行が直交することは、対応する語の距離が $N/2$ であることと同じである。
$N\ge2$ 次の正規化された Hadamard 行列(第 1 行と第 1 列の成分がすべて $1$)の行を上の読み替えで語 $r_1,\dots,r_N\in\{0,1\}^N$ にする。
$i\ne j$ なら第 $i$ 行と第 $j$ 行は直交するので $d(r_i,r_j)=N/2$ であり、$d(r_i,\bar r_j)=N-N/2=N/2$、$d(r_i,\bar r_i)=N$ である。とくに $2N$ 個の語は相異なり、最小距離は $N/2$ である。
1:$n=N$、$d=N/2$ で thm-plk-main の 2 の右辺は $4d=2N$ である。
2:正規化により第 1 列の成分はすべて $1$、すなわちどの $r_i$ も第 1 座標が $0$ なので、第 1 座標を除いても距離は変わらない。$n=N-1$、$d=N/2$ で $2d-n=1$ なので、thm-plk-main の 1 の右辺は $2\lfloor N/2\rfloor=N$ である。
3:Hadamard行列 の命題「列も直交する」により第 2 列は第 1 列(成分がすべて $1$)と直交するので、第 2 列には $1$ と $-1$ がちょうど $N/2$ 個ずつある。第 2 座標が $0$ の $r_i$ どうしは最初の 2 座標で一致するので、それらを除いても距離は $N/2$ のままである。$N\ge4$ なので同じ記事の定理「次数は 1, 2 か 4 の倍数」により $4\mid N$ であり、$n=N-2$、$d=N/2$ で $2d-n=2$、thm-plk-main の 1 の右辺は $2\lfloor N/4\rfloor=N/2$ である。$\square$
Sylvester の構成(Hadamard行列 の定理「Kronecker 積は Hadamard 行列」)から $N=2^m$ のすべてで等号の符号が得られ、このとき 1 の符号は 1 次の Reed–Muller 符号 $\mathrm{RM}(1,m)$ である(Reed–Muller符号)。Paley の構成で $N=12$($q=11$)とすると、長さ $12$・$24$ 語、長さ $11$・$12$ 語、長さ $10$・$6$ 語の、いずれも最小距離 $6$ の符号が得られる。$24$ も $12$ も $6$ も $2$ の冪でないので、これらは線形符号ではありえない。
thm-plk-main は $2d>n$ でしか使えないが、長さを縮めた符号に当てると距離が小さい場合にも効く。
$1\le d\le n$ なら
$$
A_2(n,d)\le2d\cdot2^{\max(n-2d+1,\,0)}
$$
である。したがって、$d_n/n\to\delta$($0\le\delta\le1$)をみたす $1\le d_n\le n$ について
$$
\limsup_{n\to\infty}\frac1n\log_2A_2(n,d_n)\le\max(1-2\delta,0)
$$
である。
$2d>n$ なら thm-plk-main の 1 と $2d-n\ge1$ から $A_2(n,d)\le2\lfloor d/(2d-n)\rfloor\le2d$ である。
$2d\le n$ とし、$n'=2d-1$($\le n-1$)とおく。$C$ を、相異なる符号語の距離が $d$ 以上の長さ $n$ の符号とする。語 $u\in\{0,1\}^{n-n'}$ ごとに、最初の $n-n'$ 座標が $u$ である符号語の残りの $n'$ 座標の集合を $C_u$ とする。最初の $n-n'$ 座標が一致する 2 つの符号語の距離は残りの座標だけで決まるので、$C_u$ は長さ $n'$、相異なる語の距離が $d$ 以上の符号で、$\lvert C_u\rvert$ は先頭が $u$ の符号語の個数に等しい。$2d>n'$ なので thm-plk-main の 1 から $\lvert C_u\rvert\le2\lfloor d/1\rfloor=2d$ である。$u$ は $2^{n-n'}=2^{n-2d+1}$ 通りなので $\lvert C\rvert\le2d\cdot2^{n-2d+1}$ である。
後半:前半と $d_n\le n$ から
$$
\frac1n\log_2A_2(n,d_n)\le\max\Bigl(1-\frac{2d_n}n+\frac1n,\ 0\Bigr)+\frac{1+\log_2n}n
$$
であり、$n\to\infty$ とすると右辺は $\max(1-2\delta,0)$ に収束する。$\square$
$q$ 元符号でも同じ縮め方から情報率は漸近的に $1-q\delta/(q-1)$ 以下になる(GRS25 Corollary 4.4.2, p. 81)。2 元符号の情報率 $R$ と相対距離 $\delta$ についての上界と下界の比較は Gilbert–Varshamov限界 の節「上からの限界との比較」にある。漸近 Hamming 限界 $1-H_2(\delta/2)$($H_2$ は 2 元エントロピー関数)と比べると、$1-2\delta$ の方が小さいのは $\delta$ がおよそ $0.3128$ より大きいときで、$\delta$ が小さいところでは Hamming 限界の方が強い。どちらも Elias–Bassalygo の限界で改良される(GRS25 Theorem 8.1.1, p. 161)。$\delta>1/2$ では、thm-plk-main の 1 から $A_2(n,d)$ は $n$ によらず有界になり、情報率が正の符号の族はない。
| 外す条件 | 反例 | 成り立たなくなる結論 |
|---|---|---|
| $2d>n$(thm-plk-main の 1) | $n=7$、$d=3$ | $A_2(n,d)\le2\lfloor d/(2d-n)\rfloor$ |
| $d$ が奇数(cor-plk-odd の 1) | $n=7$、$d=4$ | $A_2(n,d)\le2\lfloor(d+1)/(2d+1-n)\rfloor$ |
| 2 元であること(thm-plk-main の 1) | 3 元、$n=3$、$d=2$ | 大きさが $2\lfloor d/(2d-n)\rfloor$ 以下 |
| $n=2d$(thm-plk-main の 2) | $n=5$、$d=2$ | 大きさが $4d$ 以下 |
要点:各行の符号の大きさが、右の列の式の値を超える。
1 行目:$2d-n=-1$ で右辺は $2\lfloor-3\rfloor=-6$ だが、Hamming符号 $[7,4,3]_2$ は $16$ 語で最小距離 $3$ である。
2 行目:$2d+1=9>7$ で右辺は $2\lfloor5/2\rfloor=4$ だが、thm-plk-hadamard の 2 を $N=8$ に当てた符号は $8$ 語で最小距離 $4$ である。偶数の $d$ では lem-plk-parity の検査の桁が距離を増やさない。
3 行目:$2d=4>3$ で右辺は $4$ だが、3 元の Reed–Solomon 符号 $\{(a,a+b,a+2b): a,b\in\mathbb F_3\}$ は $9$ 語で最小距離 $2$ である(Reed–Solomon符号 の例「小さい Reed–Solomon 符号」)。lem-plk-sum の $m(M-m)\le M^2/4$ が 2 文字に分けることを使っている。
4 行目:重みが偶数の長さ $5$ の語は $16$ 個で最小距離 $2$ であり、$4d=8$ を超える。$n=5>2d$ なので thm-plk-main の 2 の縮め方では $2d>n'$ の符号に届かない。
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する