誤り訂正符号

同義語：Hamming符号（高校数学）error-correcting codes

概要

前提知識: 連立1次方程式と掃き出し法, 合同式の計算規則, 絶対値と三角不等式

高校での出発点：0 と 1 の列が途中で化ける

計算機どうしは、情報を $0$ と $1$ の列にして送る。送る途中で雑音が入ると、ところどころの $0$ が $1$ に、$1$ が $0$ に化けることがある。受け取った側は、化けたかどうかを見分け、できれば元に直したい。そのための工夫を 2 つ試す。

3 回繰り返して送る

$1$ 桁の情報 $0$ または $1$ を、同じ数を 3 回並べた $000$ または $111$ にして送る。受け取った 3 桁のうち多い方の数を、送られた情報とみなす。
(1) $111$ を送って 2 桁目が化け、$101$ を受け取った。$1$ が 2 個、$0$ が 1 個なので $1$ と判断し、正しく直せる。
(2) $000$ を送って 1 桁目と 3 桁目が化け、$101$ を受け取った。同じ規則で $1$ と判断してしまい、誤る。
3 桁のうち 1 か所までの化けなら必ず直せるが、2 か所化けると直せない。そのかわり、3 桁送って運べる情報は $1$ 桁だけである。

偶数の検査の桁を付ける

4 桁の情報 $1011$ の後ろに、全体の $1$ の個数が偶数になるように $1$ 桁を付け、$10111$ として送る（$1$ が 4 個）。
(1) 3 桁目が化けて $10011$ を受け取ると、$1$ の個数は 3 個で奇数である。化けたことは分かる。
(2) しかし、どこが化けたかは分からない。$10011$ から 1 か所を変えて $1$ の個数を偶数にする方法は、$00011$、$11011$、$10111$、$10001$、$10010$ の 5 通りあり、どれが送られたかを決められない。
5 桁で 4 桁の情報を運べて効率はよいが、化けたことを知らせるだけで、直すことはできない。

2 つの工夫の違いはどこから来るのか。この記事では、使ってよい語どうしの「離れ具合」を数で測り、次の問いに答える。

何か所までの化けなら、必ず正しく直せるか。→ thm-ecc-distance

繰り返しよりも効率よく、しかも 1 か所の化けを直せる方法はあるか。→ thm-ecc-hamming

高校の見方	この記事の言葉	大学の言葉
違う桁の数	Hamming 距離	距離の公理を満たす関数
$0$ と $1$ の足し算で $1+1=0$	$2$ で割った余りの計算	2 元体 $\mathbb{F}_2$
検査の式 $H\boldsymbol{x}\equiv\boldsymbol{0}$	Hamming 符号	線形符号（部分空間）
誤りの位置を読む	$H\boldsymbol{r}$ の値	シンドローム

言葉の準備：語、符号、Hamming 距離

語・符号・Hamming 距離

$0$ と $1$ を $n$ 個並べた列 $x=x_1x_2\cdots x_n$ を、長さ $n$ の語という。長さ $n$ の語は全部で $2^n$ 個ある。送ってよい語として決めた語の集まり $C$ を符号、$C$ の語を 符号語 という。
2 つの語 $x$、$y$ の Hamming 距離 $d(x,y)$ を、$x_k\ne y_k$ となる位置 $k$ の個数と定める。符号 $C$ の異なる 2 つの符号語の Hamming 距離のうち最小のものを、$C$ の 最小距離 という。

Hamming 距離を数える

$d(10110,\ 11100)$：1 桁目から順に比べると、$1$ と $1$、$0$ と $1$、$1$ と $1$、$1$ と $0$、$0$ と $0$ で、違うのは 2 桁目と 4 桁目なので $d=2$ である。
3 回繰り返す符号 $C=\{000,111\}$ の最小距離は $d(000,111)=3$ である。
長さ 5 の偶数の検査の符号（$1$ の個数が偶数の語の全体、16 個）の最小距離は $2$ である。$1$ の個数が偶数の 2 つの語が 1 か所だけ違うと、一方の $1$ の個数は他方より $1$ だけ多いか少なく、偶奇が変わってしまうので、距離は $1$ にならない。一方 $d(00000,\ 11000)=2$ である。

長さ 3 の語は 8 個で、立方体の頂点に置ける（図 1）。2 つの語の Hamming 距離は、立方体の辺をたどって一方から他方へ行くときの、最も少ない辺の数である。$000$ と $111$ は立方体の向かい合う頂点で、距離 $3$ である。
長さ 3 の 8 個の語を立方体の頂点に置いた図。辺でつながった語は距離 1。000 から距離 1 以内の語（青）と 111 から距離 1 以内の語（橙）は重ならず、8 個を 4 個ずつに分ける
Hamming 距離は、ふつうの距離と同じく三角不等式を満たす。

Hamming 距離の三角不等式

長さ $n$ の語 $x$、$y$、$z$ について $d(x,z)\le d(x,y)+d(y,z)$ である。

$x_k\ne z_k$ となる位置 $k$ を 1 つとる。もし $x_k=y_k$ かつ $y_k=z_k$ なら $x_k=z_k$ となってしまうので、$x_k\ne y_k$ と $y_k\ne z_k$ の少なくとも一方が成り立つ。したがって、「$x$ と $z$ が違う位置」は、「$x$ と $y$ が違う位置」か「$y$ と $z$ が違う位置」の少なくとも一方に含まれる。個数を比べて $d(x,z)\le d(x,y)+d(y,z)$ である。

実数の三角不等式 $\lvert a-c\rvert\le\lvert a-b\rvert+\lvert b-c\rvert$（絶対値と三角不等式）と同じ形である。次の主定理の証明では、この不等式だけを使う。

主定理 1：最小距離と直せる誤りの数

受け取った語 $r$ から送られた符号語を推定する規則として、「$r$ に Hamming 距離で最も近い符号語に直す」を使う。これを 最も近い語に直す 規則と呼ぶ。ex-ecc-repeat の「多い方の数」は、この規則そのものである（$101$ は $111$ から距離 $1$、$000$ から距離 $2$）。

最小距離と誤りの訂正

$t$ を $0$ 以上の整数とし、符号 $C$ の最小距離が $2t+1$ 以上であるとする。符号語 $c$ を送り、$t$ か所以下が化けた語 $r$ を受け取ったとき、$r$ に最も近い符号語はただ 1 つで、それは $c$ である。つまり、最も近い語に直す規則で、$t$ か所以下の化けは必ず正しく直せる。

化けた位置が $t$ か所以下なので $d(c,r)\le t$ である。$c$ 以外の符号語 $c'$ をとる。最小距離が $2t+1$ 以上なので $d(c,c')\ge2t+1$ である。lem-ecc-triangle を $c$、$r$、$c'$ に使うと $d(c,c')\le d(c,r)+d(r,c')$ なので、
$$ d(r,c')\ge d(c,c')-d(c,r)\ge(2t+1)-t=t+1>t\ge d(c,r) $$
である。よって、$c$ 以外のどの符号語も $r$ から $c$ より遠い。$r$ に最も近い符号語はただ 1 つで、$c$ である。

$t=1$ なら「最小距離 $3$ 以上なら 1 か所の化けを直せる」、$t=2$ なら「最小距離 $5$ 以上なら 2 か所まで直せる」となる。直すのをあきらめて「化けたかどうか」だけを知りたいときは、条件が弱くてすむ。

最小距離と誤りの検出

符号 $C$ の最小距離が $s+1$ 以上なら、$1$ か所以上 $s$ か所以下の化けがあると、受け取った語は符号語ではない。つまり、化けたことが必ず分かる。

符号語 $c$ を送り、$1$ か所以上 $s$ か所以下が化けた $r$ を受け取ったとすると $1\le d(c,r)\le s$ である。$r$ は $c$ と違い、もし $r$ が符号語なら、$c$ と異なる 2 つの符号語の距離が $s$ 以下になり、最小距離が $s+1$ 以上であることに反する。よって $r$ は符号語ではない。

2 つの工夫を主定理で見直す

3 回繰り返す符号は最小距離 $3=2\cdot1+1$ なので、thm-ecc-distance（$t=1$）により 1 か所の化けを直せる。cor-ecc-detect（$s=2$）により、直さずに検出だけするなら 2 か所までの化けに気づける。ex-ecc-repeat の (2) は、2 か所の化けを「直そう」として誤った例である。
偶数の検査の符号は最小距離 $2$ なので、cor-ecc-detect（$s=1$）により 1 か所の化けに気づけるが、thm-ecc-distance は $t=0$ でしか使えない。実際 ex-ecc-parity の (2) では、受け取った語から距離 $1$ の符号語が 5 つあり、最も近い符号語が 1 つに決まらなかった。

図 1 で言えば、$000$ と $111$ のまわりの「距離 1 以内」の 2 つの集まりが重ならないことが、thm-ecc-distance の $t=1$ の場合である。化けた語は、送った符号語のまわりの集まりから外に出ない。

$2$ で割った余りの世界の連立 1 次方程式

効率のよい符号を作るために、$0$ と $1$ の計算を決める。足し算と掛け算の結果を $2$ で割った余りで置き換える（合同式の計算規則の法 $2$ の計算）。

$+$	$0$	$1$
$0$	$0$	$1$
$1$	$1$	$0$

掛け算はふつうと同じ（$1\cdot1=1$、ほかは $0$）である。$1+1=0$ なので、$-1$ は $1$ と同じで、「引く」と「足す」は同じ計算になる。語 $x$、$y$ の和 $x+y$ は桁ごとの和で、例えば $10110+11100=01010$ である。$x+y$ で $1$ になる桁は $x$ と $y$ が違う桁なので、
$$ d(x,y)=(x+y\text{ の }1\text{ の個数}) $$
である。語の $1$ の個数を、その語の重さという。
この世界でも、連立1次方程式と掃き出し法の掃き出しがそのまま使える。$0$ でない数は $1$ だけで、$1$ で割るのは何もしないことなので、先頭の 1 を作る変形は要らず、行の入れ替えと「ある行を別の行に足す」だけで済む。

法 2 で掃き出す

法 $2$ の連立方程式 $x_1+x_2\equiv1$、$x_2+x_3\equiv0$、$x_1+x_3\equiv1\pmod2$ を解く。
$$ \left(\begin{array}{ccc|c}1&1&0&1\\ 0&1&1&0\\ 1&0&1&1\end{array}\right) \xrightarrow{R_3+R_1} \left(\begin{array}{ccc|c}1&1&0&1\\ 0&1&1&0\\ 0&1&1&0\end{array}\right) \xrightarrow[R_3+R_2]{R_1+R_2} \left(\begin{array}{ccc|c}1&0&1&1\\ 0&1&1&0\\ 0&0&0&0\end{array}\right) $$
3 行目では $1+1=0$ を使った（例えば $R_3+R_1$ の 1 列目は $1+1=0$、最後の列も $1+1=0$）。自由な文字は $x_3$ で、$x_1=1+x_3$、$x_2=x_3$ である。$x_3$ は $0$ か $1$ の 2 通りなので、解は $(1,0,0)$ と $(0,1,1)$ のちょうど 2 つである。どちらも 3 本の式を満たす（例えば $(0,1,1)$ で $0+1=1$、$1+1\equiv0$、$0+1=1$）。

実数の連立方程式では、自由な文字が 1 つあれば解は無数だった。法 $2$ の世界では、自由な文字は $0$ か $1$ しかとらないので、解をもつとき、自由な文字が $f$ 個なら解はちょうど $2^f$ 個である。

主定理 2：Hamming 符号

長さ 7 の語 $x=x_1x_2\cdots x_7$ に、次の $3\times7$ 行列 $H$ で 3 本の検査の式を課す。$H$ の第 $j$ 列は、$j$ を 2 進法で書いた 3 桁を、上から $4$ の位、$2$ の位、$1$ の位の順に縦に並べたものである（n進法と記数法）。
$$ H=\begin{pmatrix}0&0&0&1&1&1&1\\ 0&1&1&0&0&1&1\\ 1&0&1&0&1&0&1\end{pmatrix},\qquad \begin{cases}x_4+x_5+x_6+x_7\equiv0\\ x_2+x_3+x_6+x_7\equiv0\\ x_1+x_3+x_5+x_7\equiv0\end{cases}\pmod 2 $$
例えば第 6 列 $\begin{pmatrix}1\\1\\0\end{pmatrix}$ は $6=4+2$ を表す。

Hamming 符号

上の $H$ について、$H\boldsymbol{x}\equiv\boldsymbol{0}\pmod2$ を満たす長さ 7 の語 $x$ の全体を Hamming 符号（長さ 7）という。ここで $x$ は縦に並べたベクトルとみる。

3 本の式は、図 2 の 3 つの円で見ることができる。位置 $p$ を、$p$ を 2 進法で書いて $1$ の立つ位の円すべてに入る領域に置く。検査の式は「各円の中の数の和が偶数」という条件になる。例えば「$4$ の位の円」には位置 $4,5,6,7$ が入り、1 本目の式に当たる。
3 つの円が重なって 7 つの領域ができる。位置 p の数は、p を 2 進法で書いて 1 の立つ位の円すべてに入る領域に置く

4 桁の情報を符号語にする

3 本の式を掃き出すと、先頭の 1 は $x_1$、$x_2$、$x_4$ の列にでき、自由な文字は $x_3$、$x_5$、$x_6$、$x_7$ の 4 つである。$x_1$、$x_2$、$x_4$ のうち、1 本目の式は $x_4$ だけを、2 本目は $x_2$ だけを、3 本目は $x_1$ だけを含むので、それぞれの式を移項して（法 $2$ では $-1=1$ だから符号は変わらない）
$$ x_1=x_3+x_5+x_7,\qquad x_2=x_3+x_6+x_7,\qquad x_4=x_5+x_6+x_7 $$
と解ける。情報 $1011$ を $x_3=1$、$x_5=0$、$x_6=1$、$x_7=1$ に入れると、$x_1=1+0+1=0$、$x_2=1+1+1=1$（$3$ を $2$ で割った余り）、$x_4=0+1+1=0$ で、符号語は $\boxed{0110011}$ である。3 本の式を確かめると $0+0+1+1=2$、$1+1+1+1=4$、$0+1+0+1=2$ で、どれも偶数である（図 3）。

Hamming 符号の性質

Hamming 符号の符号語はちょうど $16$ 個である。
Hamming 符号の最小距離は $3$ である。したがって 1 か所の化けは、最も近い語に直す規則で必ず正しく直せる。
符号語の $j$ 番目が 1 か所だけ化けた語 $r$ を受け取ると、$Hr$ は $H$ の第 $j$ 列に等しい。つまり $Hr$ を 2 進法の数として読むと、化けた位置 $j$ が分かる。
長さ 7 のどの語も、ちょうど 1 つの符号語から距離 $1$ 以内にある。

段 1（(1)：符号語の数）．ex-ecc-encode のとおり、掃き出すと自由な文字が $x_3$、$x_5$、$x_6$、$x_7$ の 4 つで、それぞれ $0$ か $1$ を自由に選べ、選ぶごとに $x_1$、$x_2$、$x_4$ がただ 1 通りに決まる（連立1次方程式と掃き出し法の定理「簡約な階段の形と解の読み方」は、法 $2$ の計算でも同じ証明で成り立つ）。よって符号語は $2^4=16$ 個である。
段 2（和も符号語）．$x$、$y$ が符号語なら $H(x+y)\equiv Hx+Hy\equiv\boldsymbol{0}+\boldsymbol{0}=\boldsymbol{0}$ なので、$x+y$ も符号語である。すべて $0$ の語 $0000000$ も符号語である。
段 3（(2)：最小距離）．異なる符号語 $x$、$y$ の距離 $d(x,y)$ は $x+y$ の重さで、段 2 により $x+y$ は $0000000$ でない符号語である。よって、$0000000$ でない符号語の重さが $3$ 以上であることを示せばよい。

重さ $1$ の語 $e_j$（$j$ 番目だけ $1$）なら、$He_j$ は $H$ の第 $j$ 列で、どの列も $\boldsymbol{0}$ でないから符号語ではない。
重さ $2$ の語 $e_i+e_j$（$i\ne j$）なら、$H(e_i+e_j)$ は第 $i$ 列と第 $j$ 列の和である。2 つの列は違う数を表すので、ある桁で $0$ と $1$ が違い、その桁の和は $1$ である。よって $\boldsymbol{0}$ でなく、符号語ではない。
したがって $0000000$ でない符号語の重さは $3$ 以上である。一方 $1110000$ は、第 1・2・3 列の和 $\begin{pmatrix}0\\0\\1\end{pmatrix}+\begin{pmatrix}0\\1\\0\end{pmatrix}+\begin{pmatrix}0\\1\\1\end{pmatrix}\equiv\begin{pmatrix}0\\0\\0\end{pmatrix}$ なので重さ $3$ の符号語である。よって最小距離はちょうど $3$ で、後半は thm-ecc-distance（$t=1$）による。
段 4（(3)：位置を読む）．符号語 $c$ の $j$ 番目が化けた語は $r=c+e_j$ である（$1$ を足すと $0$ と $1$ が入れ替わる）。$Hr\equiv Hc+He_j\equiv\boldsymbol{0}+(\text{第 }j\text{ 列})$ なので、$Hr$ は第 $j$ 列に等しい。$H$ の第 $j$ 列は $j$ の 2 進法の表示だったので、$Hr$ を上から $4$ の位、$2$ の位、$1$ の位と読むと $j$ になる。
段 5（(4)：すき間なく覆う）．符号語 $c$ から距離 $1$ 以内の語は、$c$ 自身と、$c$ の 1 か所を変えた 7 個の、あわせて 8 個である。2 つの異なる符号語 $c$、$c'$ について、両方から距離 $1$ 以内の語 $w$ があれば、lem-ecc-triangle により $d(c,c')\le d(c,w)+d(w,c')\le2$ となり、(2) に反する。よって 16 個の符号語の「距離 1 以内」の集まりは互いに重ならず、あわせて $16\times8=128$ 個の語を含む。長さ 7 の語は $2^7=128$ 個なので、どの語もちょうど 1 つの集まりに入る。

化けた位置を読んで直す

ex-ecc-encode の符号語 $0110011$ を送り、5 番目が化けて $0110111$ を受け取ったとする。$Hr$ を計算すると
$$ \begin{aligned} x_4+x_5+x_6+x_7&=0+1+1+1=3\equiv1,\\ x_2+x_3+x_6+x_7&=1+1+1+1=4\equiv0,\\ x_1+x_3+x_5+x_7&=0+1+1+1=3\equiv1 \end{aligned} $$
で、$Hr=\begin{pmatrix}1\\0\\1\end{pmatrix}$ を 2 進法で読むと $4+1=5$ である。5 番目を直して $0110011$ に戻り、情報の桁 $x_3x_5x_6x_7=1011$ が得られる。図 4 では、和が奇数になった「$4$ の位の円」と「$1$ の位の円」の両方に入り、「$2$ の位の円」に入らない領域が位置 $5$ である。

送った語 0110011。3 つの円のどれも、中の数の和が偶数

5 番目が化けた 0110111。4 の位の円と 1 の位の円の和が奇数になり、その 2 つだけに入る領域の位置 5 が化けたと分かる

3 つの方法を比べる。「気づける化け」は直さずに検出だけに使う場合（cor-ecc-detect）、「直せる化け」は最も近い語に直す場合（thm-ecc-distance）である。

符号	語の長さ	情報の桁数	効率	最小距離	気づける化け	直せる化け
3 回繰り返す	$3$	$1$	$\frac13$	$3$	2 か所まで	1 か所まで
偶数の検査（長さ 5）	$5$	$4$	$\frac45$	$2$	1 か所	なし
Hamming 符号（長さ 7）	$7$	$4$	$\frac47$	$3$	2 か所まで	1 か所まで

Hamming 符号は、3 回繰り返す符号と同じく 1 か所の化けを直せて、効率は $\frac47>\frac13$ とずっとよい。4 桁の情報を繰り返しで送ると $12$ 桁かかるが、Hamming 符号なら $7$ 桁で済む。

例と反例：どの条件が効いているか

外す条件	反例	成り立たなくなること
化けは $t$ か所以下	Hamming 符号で 2 か所が化ける（ex-ecc-two）	最も近い符号語は送った語（thm-ecc-distance）
最小距離が $2t+1$ 以上（$t=1$）	偶数の検査の符号（ex-ecc-parity）	1 か所の化けを直せる
$H$ の列がすべて異なる	第 7 列を第 6 列と同じにした行列（ex-ecc-same-column）	最小距離 $3$、化けた位置が分かる（thm-ecc-hamming）

反例：2 か所が化けると別の語に直してしまう

符号語 $0110011$ を送り、1 番目と 2 番目が化けて $1010011$ を受け取ったとする。$Hr$ は第 1 列と第 2 列の和 $\begin{pmatrix}0\\0\\1\end{pmatrix}+\begin{pmatrix}0\\1\\0\end{pmatrix}=\begin{pmatrix}0\\1\\1\end{pmatrix}$ で、2 進法で $3$ と読める。規則どおり 3 番目を直すと $1000011$ になる。これは符号語（3 本の式は $0+0+1+1$、$0+0+1+1$、$1+0+0+1$ でどれも偶数）だが、送った $0110011$ とは距離 $3$ の別の符号語である。受け取った $1010011$ は、送った語から距離 $2$、$1000011$ から距離 $1$ なので、最も近い語に直す規則は必ず誤る。thm-ecc-distance は化けが $t=1$ か所以下のときだけを保証している。

反例：同じ列があると位置が分からない

$H$ の第 7 列を第 6 列と同じ $\begin{pmatrix}1\\1\\0\end{pmatrix}$ に替えた行列 $H'$ で符号を作る。$e_6+e_7=0000011$ は $H'(e_6+e_7)$ が同じ列 2 つの和 $\boldsymbol{0}$ なので符号語で、重さは $2$ である。この符号の最小距離は $2$ で、thm-ecc-distance の $t=1$ の条件を満たさない。実際、6 番目が化けても 7 番目が化けても $H'r$ は同じ $\begin{pmatrix}1\\1\\0\end{pmatrix}$ になり、どちらが化けたかを区別できない。thm-ecc-hamming の証明の段 3 で、列がすべて異なることを使ったのはこのためである。

大学数学で見る

thm-ecc-hamming の証明の段 2 のとおり、Hamming 符号は足し算で閉じている。$0$ と $1$ の 2 つの数からなる世界は、足し算・引き算・掛け算と $0$ でない数での割り算ができる体の最も小さい例で、$\mathbb{F}_2$ と書く（有限体）。長さ $n$ の語の全体は $\mathbb{F}_2$ 上のベクトル空間 $\mathbb{F}_2^n$ で、Hamming 符号はその中の $H\boldsymbol{x}=\boldsymbol{0}$ の解の全体、つまり 4 次元の部分空間である（ベクトル空間）。このように部分空間になっている符号を 線形符号 といい、受け取った語 $r$ から計算する $Hr$ を シンドローム という。
thm-ecc-hamming (4) の数え方は、どの符号にも使える。1 か所の化けを直せる長さ $n$ の符号 $C$ では、各符号語の「距離 1 以内」の $n+1$ 個の語の集まりが重ならないので、$\lvert C\rvert\,(n+1)\le2^n$ である。等号が成り立つ符号、つまりすき間なく覆う符号を 完全符号 という。長さ 7 の Hamming 符号は $16\times8=2^7$ で完全符号である。

一般の Hamming 符号と、ほかの符号を開く

長さ 7 の Hamming 符号の $H$ は、$0$ でない 3 桁の $0,1$ の列をすべて 1 回ずつ並べた行列だった。$r$ 桁の列をすべて並べると、長さ $2^r-1$、情報の桁数 $2^r-1-r$、最小距離 $3$ の符号が得られ、これも 1 か所の化けを直せる完全符号である（Wei26。証明は $r=3$ の場合と同じで、段 1〜5 の $3$ を $r$ に、$7$ を $2^r-1$ に読みかえればよい）。完全符号には、Hamming 符号のほかに Golay 符号と呼ばれるものもある（Wei26b）。

語を $0$ と $1$ ではなく大きな数の列にして、余りの計算で誤りを直す方法もある。Sho08 §4.6.2 は、整数をいくつかの互いに素な数で割った余りの列として送り、いくつかの余りが化けても元の整数を復元する方法を述べ、それを Reed–Solomon 符号の整数版と呼んでいる（§17.5 に多項式の場合がある）。

演習

受け取った語を直す

Hamming 符号の符号語を送り、1 か所以下が化けた $1101011$ を受け取った。送られた符号語と、情報の桁 $x_3x_5x_6x_7$ を求めよ。

解答を開く

$Hr$ を計算すると、$x_4+x_5+x_6+x_7=1+0+1+1=3\equiv1$、$x_2+x_3+x_6+x_7=1+0+1+1=3\equiv1$、$x_1+x_3+x_5+x_7=1+0+0+1=2\equiv0$ で、$Hr=\begin{pmatrix}1\\1\\0\end{pmatrix}$、2 進法で $6$ である。6 番目を直した $1101001$ が送られた符号語で（3 本の式は $1+0+0+1$、$1+0+0+1$、$1+0+0+1$ でどれも偶数）、情報の桁は $x_3x_5x_6x_7=0001$ である。

符号語の数の上限

長さ 5 の符号 $C$ の最小距離が $3$ 以上なら、$C$ の符号語は 5 個以下であることを示せ。

解答を開く

各符号語 $c$ について、$c$ から距離 $1$ 以内の語は $c$ 自身と 1 か所を変えた 5 個の、あわせて 6 個である。異なる符号語 $c$、$c'$ の両方から距離 $1$ 以内の語 $w$ があれば、lem-ecc-triangle により $d(c,c')\le2$ となり、最小距離が $3$ 以上であることに反する。よって、これらの集まりは重ならず、$6\lvert C\rvert\le2^5=32$ である。$\lvert C\rvert\le\frac{32}6<6$ なので、$\lvert C\rvert\le5$ である。（計算機ですべての場合を調べると、実際には 4 個が最大である。例えば $00000$、$11100$、$00111$、$11011$ はどの 2 つも距離 $3$ 以上である。）

さらに先へ

検査の式 $H\boldsymbol{x}\equiv\boldsymbol{0}$ は、連立1次方程式と掃き出し法の連立方程式を法 $2$ で考えたものだった。同じように、条件を連立 1 次方程式として読む例に魔方陣がある。
行列で構造を表すもう 1 つの例として、次に読む隣接行列と道の数では、グラフの形を $0$ と $1$ の行列で表し、行列の累乗で道の数を数える。
2 進法の読み方は n進法と記数法で扱う。数字の和の余りだけを見て全体の性質を調べる考え方は、各位の数字の和で $3$ や $9$ の倍数を見分ける倍数の判定法と通じる（偶数の検査は、$1$ の個数の和を $2$ で割った余りを見ている）。