完全符号
概要
完全符号（perfect code）とは、$q$ 個の文字からなる長さ $n$ の語の全体 $A^n$ の部分集合で、符号語を中心とする Hamming 距離の半径 $t$ の球が空間をすき間も重なりもなく分割するものである。最小距離が $2t+1$ 以上の符号はつねに Hamming の限界 $\lvert C\rvert\sum_{i\le t}\binom ni(q-1)^i\le q^n$ を満たし、完全符号はその等号の場合で、最小距離はちょうど $2t+1$ になる。$q$ が素数冪のとき、$1$ 個の誤りを訂正する完全符号の長さは $(q^s-1)/(q-1)$ の形に限り、自明なものを除く完全符号のパラメータは Hamming 符号と二元・三元の Golay 符号のものに限る。
最小距離が $2t+1$ 以上の符号では、符号語を中心とする半径 $t$ の球は互いに交わらない。球の中の語の個数は中心によらないので、符号語の個数と球の大きさの積は空間の語の個数を超えられない。これが Hamming の限界（球充填限界）である。等号が成り立つとき、球は空間をすき間も重なりもなく埋め尽くし、どんな語を受け取っても、距離 $t$ 以内にただ 1 つの符号語が見つかる。このような符号を 完全符号（perfect code）という。
完全符号は数の一致を要求する強い条件で、ほとんど存在しない。アルファベットの大きさが素数冪のとき、自明なものを除く完全符号のパラメータは、$1$ 個の誤りを訂正する Hamming符号 と二元・三元の Golay符号 のものに限ることが知られている（thm-perf-classification）。
この記事では、Hamming の限界（thm-perf-hamming-bound）と完全符号の最小距離（prop-perf-distance）、自明な完全符号、$1$ 個の誤りを訂正する完全符号の長さが $(q^s-1)/(q-1)$ の形に限ること（thm-perf-length-one）、数は一致するのに存在しない例（prop-perf-n90）、非線形の完全符号の構成（thm-perf-nonlinear）を証明し、分類定理（thm-perf-classification）を述べる。
定義
球の大きさ
$q\ge2$ とし、$q$ 個の元からなる集合 $A$ を アルファベット とする。$A^n$（$n\ge1$）の元を長さ $n$ の 語、$A^n$ の部分集合 $C$ を 符号、その元を 符号語 という。語 $u,v$ の Hamming 距離 $d(u,v)$ は $u_i\ne v_i$ となる $i$ の個数で、$A^n$ の上の 距離空間 の距離である（三角不等式は座標ごとの比較から従う。線形符号 の補題「Hamming 距離の性質」と同じ証明）。$\lvert C\rvert\ge2$ のとき、相異なる 2 つの符号語の距離の最小値を $C$ の 最小距離 $d(C)$ という。$A=\mathbb F_q$（$q$ は素数冪）で $C$ が線形部分空間なら、$C$ は 線形符号 である。
語 $v$ を中心とする半径 $t$ の 球 を $B_t(v)=\{u\in A^n: d(u,v)\le t\}$ とする。$v$ とちょうど $i$ 個の座標で異なる語は、座標の選び方 $\binom ni$ 通りとそれぞれの座標の値 $q-1$ 通りで $\binom ni(q-1)^i$ 個あるので、
$$
\lvert B_t(v)\rvert=V_q(n,t)=\sum_{i=0}^{t}\binom ni(q-1)^i
$$
であり（$i>n$ の項は $0$）、$v$ によらない。
$t\ge0$ とし、$C\subset A^n$ を、相異なる 2 つの符号語の距離がすべて $2t+1$ 以上の符号とする（$\lvert C\rvert=1$ でもよい）。このとき
$$
\lvert C\rvert\cdot V_q(n,t)\le q^n
$$
であり、等号が成り立つことと、$A^n$ のどの語もある符号語からの距離 $t$ 以下にあることは同値である。
符号語 $c\ne c'$ と $u\in B_t(c)\cap B_t(c')$ があれば、三角不等式から $d(c,c')\le d(c,u)+d(u,c')\le2t$ となり仮定に反する。よって球 $B_t(c)$（$c\in C$）は互いに交わらず、その和集合の元の個数は $\lvert C\rvert V_q(n,t)$ で、$q^n$ 以下である。等号は、和集合が $A^n$ 全体であることと同値である。$\square$
完全符号
$t\ge0$ とする。符号 $C\subset A^n$ について、$A^n$ のどの語 $u$ にも $d(u,c)\le t$ となる符号語 $c$ がちょうど 1 つあるとき、すなわち球 $B_t(c)$（$c\in C$）が $A^n$ の分割をなすとき、$C$ を $t$ 個の誤りを訂正する 完全符号（perfect $t$-error-correcting code）という。
Golay符号 では、$A=\mathbb F_q$ の線形符号について、最小距離が $2t+1$ 以上で Hamming の限界の等号が成り立つことを完全符号の定義としている。thm-perf-hamming-bound と次の命題により、これはこの記事の定義を次元 $1$ 以上の線形符号に限ったものと一致する。Mac03 §13.3（p. 208）は、符号語を中心とする半径 $t$ の球が重なりなく空間を埋めることを二元の完全符号の定義としている。
$C\subset A^n$ を $\lvert C\rvert\ge2$ の符号、$t\ge0$ とする。
- 球 $B_t(c)$（$c\in C$）が互いに交わらないことと $d(C)\ge2t+1$ は同値である。
- $C$ が $t$ 個の誤りを訂正する完全符号であることと、$d(C)\ge2t+1$ かつ $\lvert C\rvert V_q(n,t)=q^n$ であることは同値である。
- $C$ が $t$ 個の誤りを訂正する完全符号なら $d(C)=2t+1$ である。とくに $t$ は $C$ から $t=(d(C)-1)/2$ で決まり、完全符号の最小距離は奇数である。
1：$d(C)\ge2t+1$ なら球が交わらないことは prf-perf-hamming-bound で示した。逆に、ある $c\ne c'$ で $\delta=d(c,c')\le2t$ なら、$c$ と $c'$ が異なる $\delta$ 個の座標のうち $\lfloor\delta/2\rfloor$ 個で $c'$ と同じ値、残りの座標で $c$ と同じ値をとる語 $u$ は、$d(u,c)=\lfloor\delta/2\rfloor\le t$、$d(u,c')=\lceil\delta/2\rceil\le t$ を満たし、2 つの球に共通である。
2：分割をなすことは、球が互いに交わらず和集合が $A^n$ であることなので、1 と thm-perf-hamming-bound から従う。
3：$d=d(C)\ge2t+1$ は 2 による。$d\ge2t+2$ と仮定する。$d(c,c')=d$ となる符号語 $c,c'$ をとり、2 つが異なる座標から $t+1$ 個を選んでそこでは $c'$ と同じ値、ほかでは $c$ と同じ値をとる語を $x$ とする。$d(x,c)=t+1$ であり、$c$ 以外の符号語 $c''$ については $d(x,c'')\ge d(c,c'')-d(x,c)\ge d-t-1\ge t+1$ である。よって $x$ はどの球 $B_t(c'')$ にも入らず、完全符号であることに反する。$\square$
線形な完全符号では、復号の表が球の形をそのまま映す。
$C\subset\mathbb F_q^n$ を $t$ 個の誤りを訂正する $k$ 次元の線形な完全符号とする。このとき $q^{n-k}=V_q(n,t)$ であり、$q^{n-k}$ 個の 剰余類 $v+C$ のそれぞれは重み $t$ 以下の元をちょうど 1 つ含む。とくに、剰余類の代表元はちょうど重み $t$ 以下の語の全体である。
等式は $\lvert C\rvert=q^k$ と完全符号の定義から従う。$v$ に対し $d(v,c)\le t$ となる符号語 $c$ があり、$v-c\in v+C$ の重みは $d(v,c)\le t$ である。重み $t$ 以下の $u,u'\in v+C$ について $u-u'\in C$ の重みは $2t$ 以下で、prop-perf-distance の $d(C)=2t+1$ から $u=u'$ である（$C=\{0\}$ のときも直接分かる）。$\square$
Mac03 §13.3（p. 208）の言い方では、完全符号では 1 つの球の中の誤りの個数と、シンドロームの個数が等しい。
例
自明な完全符号
- $C=A^n$ は $0$ 個の誤りを訂正する完全符号である。
- 1 つの語だけからなる $C=\{c\}$ は、$t\ge n$ のとき $t$ 個の誤りを訂正する完全符号である。
- $n$ が奇数のとき、二元の反復符号 $C=\{0\cdots0,\ 1\cdots1\}\subset\mathbb F_2^n$ は $(n-1)/2$ 個の誤りを訂正する完全符号である。
1 は $B_0(c)=\{c\}$ から、2 は $B_t(c)=A^n$（$t\ge n$）から従う。3：$t=(n-1)/2$ とする。語 $u$ の $1$ の個数を $w$ とすると $d(u,0\cdots0)=w$、$d(u,1\cdots1)=n-w$ で、$n$ が奇数なので $w\le t$ と $n-w\le t$ のちょうど一方が成り立つ。$\square$
これら 3 種類を 自明な完全符号 という。$q\ge3$ では、長さ $n\ge2$ の反復符号は完全符号ではない（長さ $1$ の反復符号は $A^1$ 全体で、1 の場合である）。実際、$t=\lfloor(n-1)/2\rfloor$ とし、相異なる 3 文字 $\alpha,\beta,\gamma\in A$ を使って $\alpha$ と $\beta$ を $\lfloor n/2\rfloor$ 個ずつ並べ、$n$ が奇数なら残りの 1 か所を $\gamma$ にした語 $u$ をとると、どの文字も $u$ に $\lfloor n/2\rfloor$ 回以下しか現れないので、$u$ とどの符号語との距離も $n-\lfloor n/2\rfloor=t+1$ 以上であり、$u$ はどの球 $B_t(c)$ にも入らない。例えば $q=3$、$n=3$ の反復符号 $\{000,111,222\}$ は最小距離 $3$ だが、$3\cdot V_3(3,1)=3\cdot7=21< 27$ である。
Hamming 符号と Golay 符号
| 符号 | $q$ | $n$ | $\lvert C\rvert$ | $t$ | 数の一致 |
|---|---|---|---|---|---|
| Hamming符号 | 素数冪 | $\frac{q^r-1}{q-1}$ | $q^{n-r}$ | $1$ | $q^{n-r}(1+n(q-1))=q^{n-r}q^r$ |
| 二元 Golay符号 | $2$ | $23$ | $2^{12}$ | $3$ | $1+23+253+1771=2^{11}$ |
| 三元 Golay 符号 | $3$ | $11$ | $3^6$ | $2$ | $1+22+220=3^5$ |
| 二元の反復符号 | $2$ | 奇数 | $2$ | $\frac{n-1}2$ | $\sum_{i\le(n-1)/2}\binom ni=2^{n-1}$ |
Hamming 符号が完全符号であることは Hamming符号 の定理「Hamming 符号のパラメータ」、Golay 符号は Golay符号 の定理「二元 Golay 符号」「三元 Golay 符号」で証明されている。表の最後の行の等式は、prf-perf-trivial の 3 の数え方そのものである。
1 個の誤りを訂正する完全符号の長さ
$t=1$ のとき Hamming の限界の等号は $\lvert C\rvert\,(1+n(q-1))=q^n$ である。$q$ が素数冪なら、この数の条件だけで長さが決まる。
$q=p^m$（$p$ は素数、$m\ge1$）とし、$\lvert A\rvert=q$ とする。$A^n$ に $1$ 個の誤りを訂正する完全符号 $C$ があれば、ある整数 $s\ge1$ について
$$
n=\frac{q^s-1}{q-1},\qquad\lvert C\rvert=q^{n-s}
$$
である。逆に、$s\ge2$ についてこの長さの完全符号は、$A=\mathbb F_q$ の Hamming 符号として存在する。
球 $B_1(c)$（$c\in C$）は $A^n$ を分割し、どれも $V_q(n,1)=1+n(q-1)$ 個の語を含むので $\lvert C\rvert(1+n(q-1))=q^n=p^{mn}$ である。よって $1+n(q-1)$ は $p^{mn}$ の約数であり、$p^a$ と書ける。$a=ms+b$（$0\le b< m$）と割ると、$q\equiv1\pmod{q-1}$ より
$$
1\equiv1+n(q-1)=p^a=q^sp^b\equiv p^b\pmod{q-1}
$$
である。$b\ge1$ なら $m\ge2$ で、$1< p^b\le p^{m-1}=q/p\le q/2< q$ だから $0< p^b-1< q-1$ となり、$q-1$ が $p^b-1$ を割ることに反する。よって $b=0$、$1+n(q-1)=q^s$ で、$n=(q^s-1)/(q-1)$、$\lvert C\rvert=q^n/q^s=q^{n-s}$ である。$n\ge1$ から $s\ge1$ である。後半は Hamming符号 の定理「Hamming 符号のパラメータ」である。$\square$
$s=1$ は $n=1$、$\lvert C\rvert=1$ の自明な場合である。$q$ が素数冪でないと、割り切れる条件だけでは長さが決まらない。例えば $q=6$、$n=19$ では $1+5\cdot19=96=2^5\cdot3$ が $6^{19}$ を割るが、$19$ は $(6^s-1)/5$ の形（$1,7,43,\dots$）ではない。素数冪でない $q$ について $1$ 個の誤りを訂正する完全符号がどこまで存在するかは、よく分かっていない（Ben26 p. 1）。
数は一致するのに存在しない例
二元で $t=2$ のとき、$V_2(90,2)=1+90+4005=4096=2^{12}$ なので、$2^{78}$ 個の符号語をもつ長さ $90$ の完全符号は Hamming の限界の等号を満たしうる。しかし、そのような符号はない。
$\mathbb F_2^{90}$ に $2$ 個の誤りを訂正する完全符号は存在しない。
そのような符号 $C$ があったとする。$c_0\in C$ をとって $C-c_0=\{c-c_0: c\in C\}$ に取り替えても、距離が保たれるので完全符号のままである。よって $0\in C$ としてよい。prop-perf-distance の 3 により $d(C)=5$ である。
第 1・2 座標が $1$ で、ほかにちょうど 1 つの座標が $1$ の重み $3$ の語の集合を $X$ とする。$\lvert X\rvert=88$ である。$x\in X$ について $d(x,c)\le2$ となる符号語 $c$ がただ 1 つあり、$d(x,0)=3$ なので $c\ne0$、したがって $\operatorname{wt}(c)=d(c,0)\ge5$ である。$x$ と $c$ がともに $1$ の座標の個数を $m\le3$ とすると
$$
2\ge d(x,c)=3+\operatorname{wt}(c)-2m\ge3+5-2m
$$
なので $m=3$、$\operatorname{wt}(c)=5$ であり、$c$ の台は $x$ の台を含む。逆に、重み $5$ の符号語 $c$ で第 1・2 座標が $1$ のものについて、台が $c$ の台に含まれる $x\in X$ は、残る $3$ つの座標から 1 つを選んで $3$ 個あり、どれも $d(x,c)=2$ を満たす。よって $X$ は、そのような $c$ ごとの $3$ 元の集合に分割され、$3$ が $88$ を割ることになる。これは矛盾である。$\square$
二元で $t=2$ のとき、$V_2(n,2)=1+n+\binom n2$ が $2$ の冪になる $n\le2000$ は、計算すると $n=1,2,5,90$ だけである（$n=1,2$ は 1 語だけの自明な場合、$n=5$ は反復符号）。
非線形の完全符号
thm-perf-length-one は長さと符号語の個数を決めるが、符号そのものは決めない。二元では、Hamming 符号と同じパラメータで線形符号と同値でない完全符号が作れる。ここで二元の符号 $C,C'\subset\mathbb F_2^n$ が 同値 とは、座標の置換 $\sigma$ と語 $w$ で $C'=\{\sigma(c)+w: c\in C\}$ と書けることをいう。この操作は Hamming 距離を保つ。
$C\subset\mathbb F_2^n$ を $1$ 個の誤りを訂正する完全符号とし、$\lvert C\rvert\ge2$ とする。関数 $f\colon C\to\mathbb F_2$ を任意にとり、$\pi(u)=u_1+\dots+u_n\in\mathbb F_2$ として
$$
C'=\{(u,\ u+v,\ \pi(u)+f(v)) : u\in\mathbb F_2^n,\ v\in C\}\subset\mathbb F_2^{2n+1}
$$
とおく。
- $C'$ は長さ $2n+1$ の $1$ 個の誤りを訂正する完全符号である。
- $C$ が線形で、$f(0)=0$ かつ $f(v+v')\ne f(v)+f(v')$ となる $v,v'\in C$ があれば、$C'$ はどの線形符号とも同値でない。
1：$(u,v)$ から語を作る写像は、最初の $n$ 座標から $u$ が、次の $n$ 座標と $u$ の和から $v$ が読めるので単射であり、$\lvert C'\rvert=2^n\lvert C\rvert=2^n\cdot2^n/(n+1)$ である（$C$ について Hamming の限界の等号を使った）。$1+(2n+1)=2(n+1)$ だから $\lvert C'\rvert(1+(2n+1))=2^{2n+1}$ で、prop-perf-distance の 2 により、$d(C')\ge3$ を示せばよい。
距離の評価を開く
相異なる $(u,u+v,\pi(u)+f(v))$ と $(u',u'+v',\pi(u')+f(v'))$ を比べる。$v=v'$ なら $u\ne u'$ で、最初の $2n$ 座標の距離は $2d(u,u')$ である。$d(u,u')=1$ なら $\pi(u)\ne\pi(u')$ で最後の座標も異なり、距離は $3$、$d(u,u')\ge2$ なら距離は $4$ 以上である。$v\ne v'$ なら、$v+v'=(u+u')+((u+v)+(u'+v'))$ と三角不等式から、最初の $2n$ 座標の距離は $d(u,u')+d(u+v,u'+v')\ge d(v,v')\ge3$ である（prop-perf-distance の 3 により $d(C)=3$）。
2：$u=0$ とすると $(0,v,f(v))\in C'$（$v\in C$）で、とくに $0=(0,0,f(0))\in C'$ である。$(0,v,f(v))+(0,v',f(v'))=(0,v+v',f(v)+f(v'))$ が $C'$ に入るなら、最初の $n$ 座標から $u=0$、次の $n$ 座標から $v+v'$ が決まり、最後の座標は $\pi(0)+f(v+v')=f(v+v')$ でなければならない。仮定よりこれは成り立たないので、$C'$ は線形でない。$C'$ が線形符号 $L$ と同値で $C'=\{\sigma(c)+w : c\in L\}$ なら、$0\in C'$ から $w\in\sigma(L)$ で、$\sigma(L)$ は線形なので $C'=\sigma(L)$ が線形になり、矛盾する。$\square$
$C$ を長さ $7$ の二元 Hamming 符号、$c^\ast$ をその $0$ でない符号語の 1 つとし、$f(c^\ast)=1$、ほかの符号語で $f=0$ とする。$c^\ast$ と異なる $0$ でない符号語 $v'$ について $v=c^\ast$ とすると、$v+v'\ne c^\ast$ なので $f(v+v')=0\ne1=f(v)+f(v')$ である。thm-perf-nonlinear により、$2^{11}$ 個の符号語をもつ長さ $15$ の $1$ 個の誤りを訂正する完全符号で、線形符号と同値でないものが得られる（長さ $15$ の二元 Hamming 符号と同じパラメータ）。全符号語を書き出すと、最小距離 $3$ と $2^{11}\cdot16=2^{15}$ が確かめられる。
非線形の $1$ 個の誤りを訂正する二元完全符号を最初に構成したのは Vasil'ev である（KA08 p. 1）。こうした符号は長さが大きくなると非常に多く、その個数の評価が研究されている（同）。
分類定理
$q$ を素数冪、$\lvert A\rvert=q$ とし、$C\subset A^n$ を自明でない（prop-perf-trivial の 3 種類のどれでもない）$t$ 個の誤りを訂正する完全符号とする。このとき $(n,\lvert C\rvert,t)$ は次のどれかである。
- Hamming 符号のパラメータ：$t=1$、ある $s\ge2$ について $n=(q^s-1)/(q-1)$、$\lvert C\rvert=q^{n-s}$。
- 二元 Golay 符号のパラメータ：$q=2$、$(n,\lvert C\rvert,t)=(23,2^{12},3)$。
- 三元 Golay 符号のパラメータ：$q=3$、$(n,\lvert C\rvert,t)=(11,3^6,2)$。
$t=1$ の場合は thm-perf-length-one で証明した（$s=1$ は自明な場合）。$t\ge2$ の場合は、Tietäväinen と、独立に Leontiev–Zinoviev が 1973 年に証明した（Ben26 p. 1、Caz24 p. 3 の Table 1 と文献表。この記事では証明しない）。完全符号の分類には、完全符号があればある多項式（Lloyd の多項式）の零点が区間 $[1,n]$ の相異なる $t$ 個の整数になるという Lloyd の定理が有力な道具として使われてきた（Ben26 p. 3。定理の言明は Caz24 Theorem 4、p. 9）。逆に、1〜3 のパラメータをもつ完全符号は Hamming 符号と Golay 符号として実際に存在する。
分類はパラメータについてのもので、符号そのものの分類ではない。1 のパラメータには thm-perf-nonlinear のように線形でない完全符号もある。二元の場合に限った一覧は Mac03 §13.3（p. 209）にもある（そこでは奇数の長さの反復符号も自明でないものに数えている）。
$q$ が素数冪でないときは、$t\ge3$ の自明でない完全符号はないことが Best・Hong・Reuvers の仕事で知られているが、$t=1,2$ の場合は一般には未解決である（Ben26 p. 1）。$t=2$ については、存在しない $q$ の値が数多く確かめられている（Caz24 p. 1、Ben26 pp. 1–2）。
反例
| 外す条件 | 反例 | 成り立たなくなること |
|---|---|---|
| 距離が $2t+1$ 以上（thm-perf-hamming-bound） | $C=\mathbb F_2^n$、$t=1$ | $\lvert C\rvert V_q(n,t)\le q^n$ |
| $t=1$（thm-perf-length-one） | 二元 Golay 符号（$t=3$、$n=23$） | $n=(q^s-1)/(q-1)$ の形 |
| 自明でない（thm-perf-classification） | 長さ $5$ の二元の反復符号（$t=2$） | パラメータが Hamming 符号か Golay 符号のもの |
1 行目：最小距離は $1$ で、$2^n(1+n)>2^n$ である。2 行目：$23$ は $2^s-1$ の形でない（$2^4-1=15< 23< 31=2^5-1$）。3 行目：$\{00000,11111\}$ は prop-perf-trivial の 3 により $2$ 個の誤りを訂正する完全符号だが、$q=2$、$t=2$ なので、Hamming 符号のパラメータ（$t=1$）でも、二元 Golay 符号のパラメータ $(23,2^{12},3)$ でも、三元 Golay 符号のパラメータ（$q=3$）でもない。
関連項目
参考文献
Mathpediaは寄付と、参考文献の書籍リンク（Amazonアソシエイト）の紹介料で運営されています。 支援について ／ 寄付する
