Plotkin限界

同義語:Plotkin boundPlotkinの限界

概要

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)$ 以下であることがわかる。

$$\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限界, 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$

Plotkin 限界

$1\le d\le n$ とする。

  1. $2d>n$ なら $A_2(n,d)\le2\left\lfloor\dfrac{d}{2d-n}\right\rfloor$ である。
  2. $A_2(2d,d)\le4d$ である。

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 と合わせて場合を分ける。

  • $M$ が偶数のとき:$M(M-1)d\le2n\cdot M^2/4$ を $M/2$ で割ると $2(M-1)d\le nM$、すなわち $M(2d-n)\le2d$ である。$2d-n>0$ で割って $M/2\le d/(2d-n)$ となり、$M/2$ は整数なので $M/2\le\lfloor d/(2d-n)\rfloor$ である。
  • $M$ が奇数のとき:$\lfloor M^2/4\rfloor=(M^2-1)/4$ なので $M(M-1)d\le n(M-1)(M+1)/2$ である。$M-1>0$ で割ると $2Md\le n(M+1)$、すなわち $M(2d-n)\le n$ である。両辺に $2d-n$ を足して $(M+1)(2d-n)\le2d$ となり、$(M+1)/2$ は整数なので $(M+1)/2\le\lfloor d/(2d-n)\rfloor$、とくに $M\le2\lfloor d/(2d-n)\rfloor-1$ である。
    どちらの場合も $M\le2\lfloor d/(2d-n)\rfloor$ である。
    2:$C\subseteq\{0,1\}^{2d}$ を、相異なる符号語の距離がすべて $d$ 以上の符号とする。第 1 座標が $0$ の符号語と $1$ の符号語のうち多い方を $C'$ とすると $\lvert C'\rvert\ge\lvert C\rvert/2$ である。$C'$ の符号語から第 1 座標を除くと、$C'$ の符号語どうしは第 1 座標で一致しているので距離は変わらず、長さ $2d-1$、相異なる語の距離が $d$ 以上の符号が $\lvert C'\rvert$ 語得られる(距離 $d\ge1$ なので相異なる語は相異なる語に写る)。$2d>2d-1$ なので 1 から $\lvert C'\rvert\le2\lfloor d/1\rfloor=2d$ であり、$\lvert C\rvert\le4d$ である。$\square$

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$ の Plotkin 限界

$d$ を奇数とする。

  1. $2d+1>n$ なら $A_2(n,d)\le2\left\lfloor\dfrac{d+1}{2d+1-n}\right\rfloor$ である。
  2. $A_2(2d+1,d)\le4d+4$ である。

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 の改良が効いている。

Hadamard 行列による等号

Plotkin 限界の等号は、行どうしが直交する $\pm1$ 行列、すなわち Hadamard行列 から作る符号で達成される。$\pm1$ の列を $1\mapsto0$、$-1\mapsto1$ で 2 元の語に読み替えると、2 つの行の内積は「一致する座標の個数 $-$ 異なる座標の個数」なので、長さ $N$ の 2 行が直交することは、対応する語の距離が $N/2$ であることと同じである。

Hadamard 行列から作る符号

$N\ge2$ 次の正規化された Hadamard 行列(第 1 行と第 1 列の成分がすべて $1$)の行を上の読み替えで語 $r_1,\dots,r_N\in\{0,1\}^N$ にする。

  1. $\{r_1,\dots,r_N,\bar r_1,\dots,\bar r_N\}$ は長さ $N$、$2N$ 語、最小距離 $N/2$ の符号で、thm-plk-main の 2 の等号 $A_2(N,N/2)=2N$ を与える。
  2. 各 $r_i$ から第 1 座標を除いた $N$ 語は、長さ $N-1$、最小距離 $N/2$ の符号で、thm-plk-main の 1 の等号 $A_2(N-1,N/2)=N$ を与える。
  3. $N\ge4$ とする。第 2 座標が $0$ である $r_i$ はちょうど $N/2$ 個あり、それらから最初の 2 座標を除いた $N/2$ 語は、長さ $N-2$、最小距離 $N/2$ の符号で、thm-plk-main の 1 の等号 $A_2(N-2,N/2)=N/2$ を与える。

$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$ でしか使えないが、長さを縮めた符号に当てると距離が小さい場合にも効く。

漸近 Plotkin 限界

$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'$ の符号に届かない。

歴史と広がり

  • 名前の由来。 名前は、最小距離を指定した 2 元符号についての Plotkin の論文(Plo60)に由来する。GRS25 §4.4(pp. 81–87)は $q$ 元の形を Plotkin 限界と呼び、$\delta\ge1-1/q$ の符号の族は情報率が $0$ であることを導いている。
  • 等号の符号。 thm-plk-hadamard の 1 の上界 $4d=2n$ が 2 元で等号をもつことは GRS25 Exercise 4.14(p. 91)にあり、$q$ 元の $d=(1-1/q)n$ の場合の上界 $2(q-1)n$ は Exercise 4.13(p. 91)にある。
  • 線形符号の場合。 線形符号では、Griesmer の限界 $n\ge\sum_{i=0}^{k-1}\lceil d/q^i\rceil$ から Plotkin 限界の $q$ 元の形が導ける(GRS25 Exercises 4.18・4.19, p. 92)。
  • リスト復号との関係。 半径を固定した球の中の符号語の個数を数える Johnson限界 の証明も、対の距離の総和を二重計数する同じ型の議論である。

関連項目

参考文献

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