Chapter 08

ハミング符号 — 1 ビット誤りを位置ごと言い当てる

この章の主役. 07 章の最後で決定的なヒントを得た——「\(H\)の列を全部違う非零ベクトルにすれば\(d_{\min}\geq3\)、つまり 1 ビット訂正ができる」。
ならば話は早い。\(m = n-k\)ビットで作れる非零ベクトルは\(2^m - 1\)個ある。 その全部を\(H\)の列として並べてしまえばよい。 これが最も効率的な 1 ビット訂正符号になる。
1950 年、ベル研究所のリチャード・ハミングがこの符号を発表した。動機は切実で、当時のリレー式計算機が週末に誤りで止まり、月曜に来ると計算が無駄になっていたという。「機械が誤りを見つけられるなら、なぜ直せないのか」という苛立ちから生まれた符号である。

1. 構成

パラメータ

\(m \geq 2\)を選び:

\[ n = 2^m - 1, \qquad k = 2^m - 1 - m, \qquad d_{\min} = 3 \]

\(m\)	\((n,k)\)	符号化率	検査ビット
2	(3,1)	0.33	2
3	(7,4)	0.57	3
4	(15,11)	0.73	4
5	(31,26)	0.84	5
8	(255,247)	0.97	8

\(n\)が大きいほど効率がよい（検査ビットは\(m\)のまま、情報は指数的に増える）。ただし訂正できるのは常に1 ビットだけなので、長くすると誤りが 2 個入る確率が上がる。実用では (72,64) のような拡張版が ECC メモリで使われる。

検査行列

\(H\)の列に、\(m\)ビットで表せる\(1\)から\(2^m-1\)までの数を2 進表現で並べる。

\(m=3\)（(7,4) ハミング符号）の場合:

\[ H = \begin{bmatrix} 0&0&0&1&1&1&1\\ 0&1&1&0&0&1&1\\ 1&0&1&0&1&0&1 \end{bmatrix} \]

（列を左から読むと \(001, 010, 011, 100, 101, 110, 111\) = 1,2,3,4,5,6,7）

最小距離が 3 である証明

\(d_{\min}\geq 3\): \(H\)の列はすべて相異なる非零ベクトル。
- 1 本の列で和 0 → 零列が必要だが無い ✗
- 2 本の列で和 0 → 2 列が等しい必要があるが全部相異なる ✗
- よって 3 本以上必要。07 章§4 より\(d_{\min}\geq3\) ✓
\(d_{\min}\leq 3\): 実際に 3 本で和が 0 になる組がある。例: \(001 \oplus 010 \oplus 011 = 000\)（1 列目、2 列目、3 列目）✓

よって\(d_{\min}=3\)、1 ビット訂正・2 ビット検出 ∎

2. 復号 — シンドロームが誤り位置を直接指す

原理

位置\(i\)（1 始まり）で 1 ビット誤りが起きたとする。誤りベクトル\(e\)は位置\(i\)だけが 1。

\[ s = eH^T = (H \text{ の第 } i \text{ 列}) \]

\(H\)の第\(i\)列は\(i\)の 2 進表現そのものなので:

\[ \boxed{\text{シンドロームを 2 進数として読むと、それが誤り位置}} \]

これがハミング符号の美しさである. 復号に表引きも探索も要らない。シンドロームを計算したら、それをそのまま整数として読むだけで壊れた場所が分かる。ハードウェアなら XOR ゲートの数段で実装できる。

復号例

\(c = 1011010\)（07 章で作った符号語）を送り、5 ビット目が反転して\(r = 1011110\)を受信したとする。

（ここでは 07 章の\(H\)ではなく、上のハミング流の\(H\)を使う。位置と列番号を対応させるため、符号語のビット順も\(H\)の列順に合わせる約束にする。）

\(r\)の各ビットを\(r_1 \dots r_7\)として\(s = rH^T\)の各成分を計算する:

\(s_1 = r_4 \oplus r_5 \oplus r_6 \oplus r_7\)（\(H\)の 1 行目が 1 の位置）
\(s_2 = r_2 \oplus r_3 \oplus r_6 \oplus r_7\)
\(s_3 = r_1 \oplus r_3 \oplus r_5 \oplus r_7\)

もし\(s = (s_1s_2s_3) = 101_2 = 5\)なら、5 番目のビットが誤り。 \(r\)の 5 ビット目を反転して訂正完了。

3. 完全符号であること

06 章のハミング限界

\[ 2^k \sum_{i=0}^{t}\binom{n}{i} \leq 2^n \]

に\(t=1\)、\(n = 2^m-1\)、\(k = n-m\)を代入する。左辺は:

\[ 2^{n-m}\left[\binom{n}{0} + \binom{n}{1}\right] = 2^{n-m}(1 + n) = 2^{n-m}\cdot 2^m = 2^n \]

（\(1 + n = 1 + 2^m-1 = 2^m\)を使った。）

等号成立 ✓ よってハミング符号は完全符号である ∎

完全符号の意味. \(n\)ビット空間\(2^n\)個のビット列が、各符号語を中心とする半径 1 の球で隙間なく、重なりなく埋め尽くされている。
どんなビット列を受信しても、必ずちょうど 1 つの符号語から距離 1 以内にある。無駄が一切ない、という意味で「これ以上効率のよい 1 ビット訂正符号は存在しない」。
完全符号は極めて稀で、（自明なものを除けば）ハミング符号とゴレイ符号しか存在しないことが証明されている（ティートヴァイネン、1973）。

4. 拡張ハミング符号 (SECDED)

ハミング符号に全体パリティ 1 ビットを追加して\((2^m, 2^m-1-m)\)とすると\(d_{\min}=4\)になる。

なぜ距離が 4 になるか: 元の符号の最小重み 3 の符号語は、1 の個数が奇数なので全体パリティが 1 になり、重みが 4 に増える。重み 4 の符号語は偶数なのでパリティ 0 のまま重み 4。よって最小重みは 4 ✓

能力: 06 章の定理より \(t = \lfloor 3/2 \rfloor = 1\) ビット訂正。同時に 3 ビットまで検出。実用上は「1 ビット訂正 + 2 ビット検出」(SECDED: Single Error Correct, Double Error Detect) として使う。

2 ビット誤りが区別できる理由:

状況	ハミング部シンドローム	全体パリティ
誤り無し	0	0（偶数）
1 ビット誤り	≠0	1（奇数）
2 ビット誤り	≠0	0（偶数）

「シンドロームが 0 でないのにパリティが偶数」＝ 2 ビット誤り。訂正はできないが検出できるので、誤って別のデータに訂正してしまう事故を防げる。

サーバの ECC メモリはこれ. DDR の ECC は典型的に (72,64) SECDED—— 64 ビットのデータに 8 ビットの検査を付け、1 ビット誤りは黙って訂正、 2 ビット誤りは検出して machine check exception を上げる。

5. まとめ

項目	内容
パラメータ	\((2^m-1,\ 2^m-1-m,\ 3)\)
設計原理	\(H\)の列に 1〜\(2^m-1\)の 2 進表現を並べる
復号	シンドロームを整数として読む = 誤り位置
能力	1 ビット訂正 / 2 ビット検出
最適性	完全符号（ハミング限界で等号）
拡張版	全体パリティを追加 → SECDED（ECC メモリ）

次章の予告: ハミング符号は「ランダムに 1 ビット」の誤りに最適だった。しかし現実の通信では、連続した区間がまとめて壊れる（バースト誤り）ことが多い。また「訂正はいらないから、とにかく高速に検出したい」という需要も大きい。その両方に応えるのが、次章の巡回符号と CRC である。