Hamming符号
概要
Hamming符号（Hamming code）とは、有限体 $\mathbb F_q$ の上で、$\mathbb F_q^r$ の各 $1$ 次元部分空間から $0$ でないベクトルを 1 つずつ選んで列に並べた $r\times n$ 行列（$r\ge2$、$n=(q^r-1)/(q-1)$）を検査行列とする線形符号である。$[n,n-r,3]$ 符号で、符号語を中心とする半径 $1$ の球が空間を埋め尽くす完全符号であり、1 か所の誤りでは、シンドロームが化けた位置と値をそのまま示す。同じパラメータの線形符号は座標の並べ替えと定数倍を除いてこれに限り、双対符号（単体符号）の $0$ でない符号語の重みはすべて $q^{r-1}$ である。
$0$ と $1$ の列を送るとき、化けた文字が 1 つだけなら必ず直せるようにしたい。線形符号 の言葉では、検査行列のどの 2 本の列も一次独立なら最小距離が $3$ 以上になり、1 か所の誤りを訂正できる。$r$ 行の検査行列にこの条件を満たす列を並べられるだけ並べると、長さ $(q^r-1)/(q-1)$ の符号ができる。これが Hamming 符号（Hamming code）である。二元で $r=3$ のときは、$1$ から $7$ を 2 進法で書いた列を並べた $[7,4,3]$ 符号になり、受け取った語の検査の結果（シンドローム）が、化けた位置そのものを 2 進法で表す。
Hamming 符号は、符号語を中心とする半径 $1$ の球が空間をすき間も重なりもなく埋め尽くす 完全符号 の代表例であり、そのパラメータをもつ線形符号は、座標の並べ替えと各座標の $0$ でない定数倍で移り合うものを除いてほかにない。高校数学の範囲での長さ $7$ の場合の説明は 誤り訂正符号 にある。
この記事では、一般の $q$ について Hamming 符号を定義し、それが 1 個の誤りを訂正する完全な $[n,n-r,3]_q$ 符号であること（thm-ham-params）、シンドロームによる復号（thm-ham-decoding）、同じパラメータの線形符号は Hamming 符号と同値なものに限ること（thm-ham-unique）、双対符号のすべての $0$ でない符号語の重みが $q^{r-1}$ であること（thm-ham-simplex）を証明する。
定義
以下、$q$ は素数冪、$\mathbb F_q$ は位数 $q$ の 有限体、$r\ge2$ とする。語の重み $\operatorname{wt}$、Hamming 距離 $d$、$[n,k,d]_q$ 符号、検査行列の用語は 線形符号 に従い、$e_j$ は第 $j$ 座標だけが $1$ の語とする。
$\mathbb F_q^r$ の $1$ 次元部分空間を 直線 とよぶ。$0$ でない元はちょうど 1 つの直線に入り、各直線は $0$ でない元を $q-1$ 個含むので、直線の個数は
$$
n=\frac{q^r-1}{q-1}=1+q+\dots+q^{r-1}
$$
である（直線の全体は 射影空間 $\mathbb P^{r-1}(\mathbb F_q)$ の点の全体である）。
$\mathbb F_q^r$ の各直線から $0$ でない元を 1 つずつ選び、それらを列として並べた $r\times n$ 行列を $H$ とする。
$$
\mathcal H_r=\{x\in\mathbb F_q^n : Hx^{\mathsf T}=0\}
$$
を Hamming 符号 という。二元（$q=2$）では直線と $0$ でない元が 1 対 1 に対応するので、$H$ の列は長さ $r$ の $0$ でない列のすべてであり、$n=2^r-1$ である。
列の選び方と並べ方には自由度がある。二元では、第 $j$ 列を $j$ の 2 進法の表示（上の行を上の位とする）にとる並べ方がよく使われる。選び方を変えても、得られる符号は座標の並べ替えと各座標の $0$ でない定数倍で移り合う（thm-ham-unique）。
$q=2$、$r=3$ で第 $j$ 列を $j$ の 2 進法の表示にとると
$$
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}
$$
で、$\mathcal H_3$ は $2^4=16$ 個の符号語をもつ $[7,4,3]_2$ 符号である（Mac03 §1.2、pp. 8–10）。語 $x$ が符号語であることは、$x_j=1$ となる $j$ の 2 進法の表示を、繰り上がりなしに各位ごとに足すと $0$ になることと同値である。例えば $(1,0,1,1,0,1,0)$ は、$1,3,4,6$ の表示 $001,011,100,110$ の各位の $1$ の個数がどれも偶数なので符号語である。
$q=3$、$r=2$ では直線は $4$ 本で、代表元を $(0,1)$、$(1,0)$、$(1,1)$、$(1,2)$ にとると
$$
H=\begin{pmatrix}0&1&1&1\\1&0&1&2\end{pmatrix}
$$
となり、$\mathcal H_2$ は $(1,0,1,2)$ と $(0,1,1,1)$ で張られる $[4,2,3]_3$ 符号である。$0$ でない $8$ 個の符号語の重みはすべて $3$ である（$a(1,0,1,2)+b(0,1,1,1)=(a,b,a+b,2a+b)$ の成分のうち、$(a,b)\ne(0,0)$ なら $0$ になるのは高々 1 つ）。
主定理
$\mathcal H_r$ は $[n,n-r,3]_q$ 符号（$n=(q^r-1)/(q-1)$）であり、$1$ 個の誤りを訂正する完全符号である。すなわち、$\mathbb F_q^n$ のどの語も、ある符号語からの距離が $1$ 以下であり、そのような符号語はちょうど 1 つである。
次元。 $H$ の列のうち $e_1,\dots,e_r$（$\mathbb F_q^r$ の標準基底）の直線から選んだ列は $\lambda_1e_1,\dots,\lambda_re_r$（$\lambda_i\ne0$）で一次独立なので、$H$ の階数は $r$ であり、$\dim\mathcal H_r=n-r$ である。
最小距離。 語 $x$ について $Hx^{\mathsf T}=\sum_jx_jh_j$（$h_j$ は第 $j$ 列）である。重み $1$ の符号語 $ae_j$（$a\ne0$）は $ah_j=0$ を意味し、$h_j\ne0$ に反する。重み $2$ の符号語 $ae_i+be_j$（$i\ne j$、$a,b\ne0$）は $h_i=-a^{-1}bh_j$ を意味し、$h_i$ と $h_j$ が同じ直線に入ることになって、各直線から 1 つずつ選んだことに反する。よって $0$ でない符号語の重みは $3$ 以上である。一方、$e_1$、$e_2$、$e_1+e_2$ の直線から選んだ列 $\alpha e_1$、$\beta e_2$、$\gamma(e_1+e_2)$ は $\alpha^{-1}(\alpha e_1)+\beta^{-1}(\beta e_2)-\gamma^{-1}\gamma(e_1+e_2)=0$ を満たすので、対応する 3 座標に $\alpha^{-1}$、$\beta^{-1}$、$-\gamma^{-1}$ を置いた重み $3$ の符号語がある（$r\ge2$ を使った）。0 でない符号語の重みの最小値が最小距離なので（線形符号 の命題「最小距離と最小の重み」）、最小距離は $3$ である。
完全であること。 最小距離が $3$ なので、符号語を中心とする半径 $1$ の球は互いに交わらない（2 つの球に共通の語があれば、三角不等式から中心の距離が $2$ 以下になる）。各球は中心と、1 座標を $q-1$ 通りに変えた語からなり $1+n(q-1)=q^r$ 個の語を含むので、球の和集合は
$$
q^{n-r}\cdot q^r=q^n
$$
個の語からなり、$\mathbb F_q^n$ 全体である。$\square$
Mac03 §13.3（p. 210）は、二元の場合に検査行列の列を長さ $r$ の $0$ でない列すべてとする符号として Hamming 符号を定義し、どの 1 か所の誤りも異なるシンドロームを生むので訂正できることを述べている。長さと情報率は次のとおりで、$r$ が大きくなると情報率は $1$ に近づく。
| $r$ | $2$ | $3$ | $4$ | $5$ | $6$ |
|---|---|---|---|---|---|
| 二元 $[n,n-r]$ | $[3,1]$ | $[7,4]$ | $[15,11]$ | $[31,26]$ | $[63,57]$ |
| 三元 $[n,n-r]$ | $[4,2]$ | $[13,10]$ | $[40,36]$ | $[121,116]$ | $[364,358]$ |
$r=2$ の二元 Hamming 符号は $\{000,111\}$、すなわち長さ $3$ の反復符号である。
シンドロームによる復号
語 $y$ を受け取り、$s=Hy^{\mathsf T}\in\mathbb F_q^r$ とおく。
- $s=0$ なら $y$ は符号語である。
- $s\ne0$ なら、$s=\lambda h_j$ となる番号 $j$ と $\lambda\in\mathbb F_q^\times$ がただ 1 組あり、$y-\lambda e_j$ は $y$ からの距離が $1$ 以下の唯一の符号語である。
二元で第 $j$ 列を $j$ の 2 進法の表示にとったときは、$s$ を 2 進法の表示とみた数が化けた位置 $j$ である。
1 は定義である。2：$s\ne0$ はちょうど 1 つの直線に入り、その直線から選んだ列 $h_j$ はちょうど 1 本である。$s$ と $h_j$ は同じ直線の $0$ でない元なので、$s=\lambda h_j$ となる $\lambda\ne0$ がただ 1 つある。$H(y-\lambda e_j)^{\mathsf T}=s-\lambda h_j=0$ なので $y-\lambda e_j$ は符号語で、$y$ からの距離は $1$ である。距離 $1$ 以下の符号語が 2 つあれば、その 2 つの距離は $2$ 以下になり、最小距離 $3$（thm-ham-params）に反する。二元では $\lambda=1$ で、$s=h_j$ は $j$ の表示そのものである。$\square$
二元の $[7,4,3]$ 符号（ex-ham-small の $H$）で、符号語 $(1,0,1,1,0,1,0)$ を送り、第 5 座標が化けて $y=(1,0,1,1,1,1,0)$ を受け取ったとする。$y_j=1$ となる $j=1,3,4,5,6$ の表示 $001,011,100,101,110$ を各位ごとに足すと、上の位から $1$ が $3,2,3$ 個で $s=(1,0,1)^{\mathsf T}$ であり、これは $5$ の表示である。第 5 座標を直して $(1,0,1,1,0,1,0)$ を得る。
三元の $[4,2,3]$ 符号（同じ例の $H$）で、符号語 $(1,0,1,2)$ の第 2 座標に $2$ が加わり $y=(1,2,1,2)$ を受け取ったとする。$s=Hy^{\mathsf T}=(0+2+1+2,\ 1+0+1+4)^{\mathsf T}=(2,0)^{\mathsf T}=2h_2$ なので $j=2$、$\lambda=2$ で、$y-2e_2=(1,0,1,2)$ に直る。
一意性
座標の並べ替えと、各座標の $0$ でない定数倍の合成（$x\mapsto(\mu_jx_{\pi^{-1}(j)})_j$、$\pi$ は置換、$\mu_j\ne0$）で移り合う 2 つの符号を 同値 という。この写像は線形で Hamming 距離を保つ。
$n=(q^r-1)/(q-1)$ とする。最小距離が $3$ 以上の長さ $n$、次元 $n-r$ の線形符号 $C\subset\mathbb F_q^n$ は、$\mathcal H_r$ と同値である。とくに、def-ham-code で列の選び方と並べ方を変えて得られる符号は互いに同値である。
$C$ の検査行列を $H'$（$r\times n$、階数 $r$）、その第 $j$ 列を $h'_j$ とする。prf-ham-params の最小距離の段と同じく、重み $1$・$2$ の符号語がないことから、$h'_j$ はどれも $0$ でなく、どの 2 本も同じ直線に入らない。$n$ 本の列が相異なる $n$ 本の直線に入り、直線はちょうど $n$ 本なので、各直線にちょうど 1 本の列が入る。よって置換 $\pi$ と $\lambda_j\ne0$ で $h'_j=\lambda_jh_{\pi(j)}$ と書ける。このとき
$$
x\in C\iff\sum_jx_j\lambda_jh_{\pi(j)}=0\iff y\in\mathcal H_r,\qquad y_{\pi(j)}=\lambda_jx_j
$$
なので、同値の写像 $x\mapsto y$ が $C$ を $\mathcal H_r$ に写す。後半は、別の選び方で作った行列 $H'$ の核に前半を当てはめればよい（その核は thm-ham-params により条件を満たす）。$\square$
線形性は外せない。二元では、Hamming 符号と同じ長さ・符号語の個数をもち 1 個の誤りを訂正する完全符号でありながら、座標の並べ替えと平行移動でどの線形符号にも移らないものが存在する（完全符号 の非線形の例）。
双対符号
$\mathcal H_r$ の双対符号 $\mathcal H_r^\perp$ は $H$ の行で張られ（線形符号 の命題「双対符号の次元」）、次元は $r$ である。これを 単体符号（simplex code）という。
$\mathcal H_r^\perp$ の $0$ でない符号語の重みはすべて $q^{r-1}$ である。したがって $\mathcal H_r^\perp$ は $[n,r,q^{r-1}]_q$ 符号であり、相異なる 2 つの符号語の距離はつねに $q^{r-1}$ である。
$\mathcal H_r^\perp$ の元は $a\in\mathbb F_q^r$ について $c_a=(a\cdot h_1,\dots,a\cdot h_n)$ と書け、$H$ の階数が $r$ なので $a\ne0$ なら $c_a\ne0$ である。$a\ne0$ を固定すると、$c_a$ の第 $j$ 座標が $0$ であることは $h_j\in W=\{v : a\cdot v=0\}$ と同値である。$W$ は $r-1$ 次元の部分空間で、$h_j\in W$ となるのは $h_j$ の直線が $W$ に含まれるときである。$W$ に含まれる直線は $(q^{r-1}-1)/(q-1)$ 本で、各直線から列はちょうど 1 本選ばれているので、$c_a$ の $0$ の座標の個数は $(q^{r-1}-1)/(q-1)$ である。よって
$$
\operatorname{wt}(c_a)=\frac{q^r-1}{q-1}-\frac{q^{r-1}-1}{q-1}=\frac{q^r-q^{r-1}}{q-1}=q^{r-1}
$$
である。距離の主張は $d(c_a,c_b)=\operatorname{wt}(c_{a-b})$ から従う。$\square$
二元で $r=3$ なら $\mathcal H_3^\perp$ は $[7,3,4]$ 符号で、$0$ でない $7$ 個の符号語はどれも重み $4$ である。$\mathcal H_3$ そのものの重みの分布は、重み $0,3,4,7$ がそれぞれ $1,7,7,1$ 個である（Mac03 §13.1、p. 206 の図 13.1。$16$ 個の符号語を書き出すと確かめられる）。
拡大 Hamming 符号
$q=2$ とし、$\mathcal H_r$ の各符号語 $c$ の末尾に $c_1+\dots+c_n$ を付け加えた語の全体を $\widehat{\mathcal H}_r\subset\mathbb F_2^{2^r}$ とする。$\widehat{\mathcal H}_r$ は $[2^r,2^r-r-1,4]_2$ 符号で、すべての符号語の重みは偶数である。
付け加える写像は線形な単射なので、$\widehat{\mathcal H}_r$ は次元 $2^r-r-1$ の線形符号である。付け加えた座標は元の語の $1$ の個数の偶奇なので、拡大した語の重みは偶数である。$0$ でない符号語の重みは元の重み（$3$ 以上）以上で偶数だから $4$ 以上であり、元の重み $3$ の符号語（thm-ham-params）は重み $4$ になるので、最小距離は $4$ である。$\square$
$\widehat{\mathcal H}_3$ の重みの分布は重み $0,4,8$ がそれぞれ $1,14,1$ 個である（Mac03 の $\mathcal H_3$ の分布 $1,7,7,1$ で、重み $3$ と $4$ の符号語がともに重み $4$ になる）。すべての重みが $4$ の倍数なので、符号語 $u,v$ について、$u$ と $v$ がともに $1$ の座標の個数を $m$ とすると $\operatorname{wt}(u+v)=\operatorname{wt}(u)+\operatorname{wt}(v)-2m$ から $2m\equiv0\pmod4$、すなわち $m$ は偶数で $u\cdot v=0$ である。よって $\widehat{\mathcal H}_3\subset\widehat{\mathcal H}_3^\perp$ で、次元はともに $4$ だから $\widehat{\mathcal H}_3$ は自己双対である。Golay符号 の拡大二元 Golay 符号は、同じ性質（自己双対で重みが $4$ の倍数）をもつ $[24,12,8]$ 符号である。
反例
| 外す条件 | 反例 | 成り立たなくなること |
|---|---|---|
| 列が $0$ でない | 二元の $H$（ex-ham-small）に零の列を第 8 列として付け加えた $3\times8$ 行列の核 | 最小距離が $3$ |
| すべての直線から列を選ぶ | 二元の $H$ から第 7 列を除いた $3\times6$ 行列の核（短縮 Hamming 符号） | 完全符号であること |
| 各直線から 1 つだけ選ぶ（$q\ge3$） | $q=3$、$r=2$ で $0$ でない $8$ 個の元をすべて列にした行列の核 | 最小距離が $3$ |
1 行目：$8$ 本の列のうち $0$ でない $7$ 本は各直線から 1 本ずつのままだが、第 8 列が $0$ なので $e_8$ が重み $1$ の符号語になり、最小距離は $1$ である。2 行目：除いた後の 6 本の列は相異なる $0$ でない列なので最小距離は $3$ のままだが、符号語は $2^3=8$ 個で $8\cdot(1+6)=56< 2^6$ となり、半径 $1$ の球が空間を覆わない。シンドローム $(1,1,1)^{\mathsf T}$ の語はどの符号語からも距離 $2$ 以上離れている（線形符号 の例「長さ 6 の二元符号の復号」はこの符号の座標を並べ替えたものである）。3 行目：$h$ と $2h$ が同じ直線に入るので、$2e_i-e_j$（$h_j=2h_i$）が重み $2$ の符号語になる。
補足
$q$ が素数冪のとき、$1$ 個の誤りを訂正する完全符号の長さは $(q^m-1)/(q-1)$ の形に限り、$2$ 個以上の誤りを訂正する自明でない完全符号のパラメータは二元・三元の Golay 符号のものに限る（完全符号。後半はこの記事では証明しない）。Mac03 §13.3（p. 209）は、二元の完全符号の一覧として Hamming 符号・奇数の長さの反復符号・二元 Golay 符号を挙げている（そこでは反復符号も自明でないものに数えている）。前半と後半を合わせると、$q$ が素数冪のとき、反復符号のような自明な完全符号を除いて、長さがいくらでも大きくとれる完全符号のパラメータは Hamming 符号のものだけである。
Hamming 符号の名は、1940 年代後半から 1950 年代初めにかけて Bell 研究所で線形符号の研究を始めた Richard Hamming による（Jud25 §8.1.3、p. 144）。
関連項目
参考文献
Mathpediaは寄付と、参考文献の書籍リンク（Amazonアソシエイト）の紹介料で運営されています。 支援について ／ 寄付する
