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

Chapter 08

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

この章の位置づけ. 07 章 4 節で、検査行列\(H\)の列がすべて 0 でなく互いに異なれば\(d_{\min}\geq 3\)となり、1 ビットの誤りを訂正できることを示した。 検査ビットが\(m\)本なら、\(H\)の列は\(m\)ビットのベクトルで、0 でないものは\(2^m - 1\)通りある。その全部を\(H\)の列に並べれば、検査ビット\(m\)本で符号長が最大の 1 ビット訂正符号ができる。これがハミング符号である。 3 節で、これ以上効率のよい 1 ビット訂正符号は無いことを確かめる。

1950 年、ベル研究所のリチャード・ハミングがこの符号を発表した。当時のリレー式計算機は誤りを検出すると止まるだけで、週末に流した計算が月曜には無駄になっていた。誤りを検出できるなら訂正もできないか、というのが動機である。

この章で使う既出の用語（定義は各リンク先）. 符号化率・\((n,k)\)符号（06 章 1 節）、検出・訂正能力と\(d_{\min}\)、訂正と検出の組み合わせ（06 章 3 節）、二項係数・ハミング限界・完全符号（06 章 4 節）、バースト誤り（06 章 6 節）、 線形符号（07 章 1 節）、検査行列（07 章 3 節）、シンドロームと「\(eH^T\)は\(e\)の 1 の位置の\(H\)の列の XOR」（07 章 4 節）

1. 構成

パラメータ

検査ビット数\(m \geq 2\)を選ぶ。\(H\)は\(m\)行で、列に\(m\)ビットの 0 でないベクトル\(2^m - 1\)本をすべて並べるので、符号長は\(n = 2^m - 1\)である。 07 章 3 節のとおり\(H\)の行数は\(n - k\)なので\(m = n - k\)、すなわち

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

である（\(d_{\min} = 3\)は下で示す）。

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

\(m = 2\)の\((3,1)\)は 3 回繰り返し符号である。\(m\)を大きくすると、検査ビットは\(m\)本のまま情報ビットが指数的に増えるので、符号化率は 1 に近づく。 ただし訂正できるのは常に 1 ビットだけである。各ビットが独立に確率\(p\)で誤るとき、\(n\)ビット中に 2 個以上の誤りが入る確率はおよそ\(\binom{n}{2}p^2\)で、\(n\)の 2 乗に比例して増える。長い符号ほど 1 ビットでは足りなくなりやすい。

検査行列

\(H\)の第\(i\)列に、\(i\)の 2 進表現（\(m\)ビット）を置く。\(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, \dots, 7\)の 2 進表現である。第 1 行が 4 の位、第 2 行が 2 の位、第 3 行が 1 の位に当たる。

この\(H\)は07 章の\(H = [P^T \mid I_3]\)と列の並び順が違うだけで、どちらも 0 でない 3 ビットのベクトルを 1 本ずつ並べている。列の並び順を変えるのはビットの位置を入れ替えることなので、性質（最小距離など）は変わらない。

符号化

この\(H\)では、1, 2, 4 番目の列（\(001, 010, 100\)）がそれぞれ 1 か所だけに 1 を持つ。そこで 1, 2, 4 番目のビットを検査ビット、残りの 3, 5, 6, 7 番目を情報ビットにする。 符号語\(c = c_1 c_2 \cdots c_7\)の条件\(cH^T = 0\)は、\(H\)の各行で 1 が立つ位置のビットの XOR が 0 になることなので、次の 3 式になる。

\[ \begin{aligned} &\text{第 3 行（1 の位）:}\quad c_1 \oplus c_3 \oplus c_5 \oplus c_7 = 0 \\ &\text{第 2 行（2 の位）:}\quad c_2 \oplus c_3 \oplus c_6 \oplus c_7 = 0 \\ &\text{第 1 行（4 の位）:}\quad c_4 \oplus c_5 \oplus c_6 \oplus c_7 = 0 \end{aligned} \]

各式に検査ビットは 1 つずつしか含まれないので、情報ビットから直接決まる:

\[ c_1 = c_3 \oplus c_5 \oplus c_7, \qquad c_2 = c_3 \oplus c_6 \oplus c_7, \qquad c_4 = c_5 \oplus c_6 \oplus c_7 \]

例: 情報ビット\((c_3, c_5, c_6, c_7) = (1, 0, 1, 0)\)なら、\(c_1 = 1 \oplus 0 \oplus 0 = 1\)、\(c_2 = 1 \oplus 1 \oplus 0 = 0\)、\(c_4 = 0 \oplus 1 \oplus 0 = 1\)で、符号語は\(c = 1011010\)である。

最小距離が 3 である証明

方針: 07 章 4 節の定理より、\(d_{\min}\)は「XOR すると 0 になる\(H\)の列の最小本数」である。1 本や 2 本では 0 にならず、3 本で 0 になる組があることを示す。

よって\(d_{\min}=3\)であり、06 章 3 節より 1 ビット訂正、または 2 ビット検出ができる ∎

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

原理

\(i\)番目のビットだけが反転したとする。誤りパターン\(e\)は\(i\)番目だけが 1 である。07 章 4 節のとおり\(eH^T\)は「\(e\)の 1 が立つ位置の\(H\)の列の XOR」なので

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

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

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

になる。一般の線形符号では 07 章のシンドローム表を引く必要があったが、ハミング符号では表も探索も要らず、シンドロームを整数として読むだけで壊れた位置が分かる。ハードウェアでも XOR ゲート数段で作れる。

上の図で情報語と誤り位置を変えると、符号語・受信語・シンドロームと訂正結果が表示される。

復号例

1 節の符号語\(c = 1011010\)を送り、5 番目のビットが反転して\(r = 1011110\)を受信したとする。シンドロームの各ビットは、1 節の 3 式の左辺を\(r\)で計算したものである:

2 進数として読むと\(101_2 = 5\)なので、5 番目のビットが誤りである。\(r\)の 5 番目を反転すると\(1011010 = c\)に戻る。

2 ビット誤りでは誤訂正が起きる

同じ\(c = 1011010\)の 1 番目と 2 番目が反転して\(r = 0111010\)を受信したとする。シンドロームは\(H\)の第 1 列と第 2 列の XOR で\(001 \oplus 010 = 011\)、つまり 3 と読める。 復号器は 3 番目のビットを反転して\(0101010\)を出力するが、これは元の\(c\)とは 3 か所違う別の符号語である。2 ビット誤りを「1 ビット誤り」と誤認して、誤りを増やしてしまった。 1 ビット訂正と 2 ビット検出を同時にはできないので（06 章 3 節、\(t + e \leq d_{\min} - 1 = 2\)）、これを防ぐには 4 節の拡張が要る。

3. 完全符号であること

06 章 4 節のハミング限界

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

に\(t=1\)、\(n = 2^m-1\)、\(k = n-m\)を代入すると、\(1 + n = 2^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 \]

となり、等号が成り立つ。よってハミング符号は完全符号である ∎

\(n\)ビットのビット列\(2^n\)個は、各符号語を中心とする半径 1 の球で、隙間なく重なりなく埋め尽くされている。どのビット列を受信しても、距離 1 以内にある符号語はちょうど 1 つである。 ハミング限界は 1 ビット訂正できる符号が満たすべき上限なので、同じ符号長\(n = 2^m - 1\)で 1 ビット訂正できる符号のうち、情報ビット数\(k\)はハミング符号が最大である。

2 値の完全符号は、自明なもの（符号語が 1 つだけの符号、全ビット列を符号語にした符号、\(n\)が奇数の\(n\)回繰り返し符号）を除くと、ハミング符号と\((23, 12)\)ゴレイ符号しかないことが知られている（1973 年、ティートヴァイネンらによる。証明は長いので省略する）。

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

ハミング符号の符号語の末尾に、全体の 1 の個数を偶数にする全体パリティを 1 ビット追加すると、\((2^m, 2^m-1-m)\)符号で\(d_{\min}=4\)になる。

距離が 4 になる理由: 全体パリティを付けると、符号語の重みは必ず偶数になる。元の重みが奇数なら 1 増え、偶数ならそのままである。 元の符号の 0 でない符号語は重みが 3 以上なので、追加後の重みは「3 なら 4」「4 なら 4」「5 以上なら 6 以上」となり、最小は 4 である。重み 3 の符号語は存在するので、最小距離はちょうど 4 である。

能力: \(d_{\min} = 4\)なので、06 章 3 節より「1 ビット訂正し、2 ビットは検出する」（\(t = 1, e = 2\)、\(t + e = 3 = d_{\min} - 1\)）使い方ができる。これをSECDED（Single Error Correct, Double Error Detect）という。

2 ビット誤りを 1 ビット誤りと区別できる理由: 受信語について、元のハミング符号部分のシンドロームと、全体（パリティビットを含む）の 1 の個数の偶奇の 2 つを見る。

状況ハミング部のシンドローム全体の 1 の個数判断
誤り無し0偶数そのまま
ハミング部の 1 ビット誤り0 でない奇数シンドローム位置を訂正
追加したパリティビットの誤り0奇数パリティビットを訂正
2 ビット誤り0 でない偶数訂正せず、検出を報告

1 ビット反転すると 1 の個数の偶奇が変わり、2 ビット反転すると元に戻る。そのため「シンドロームが 0 でないのに偶数」は 2 ビット誤りを示す。2 節の例のような誤訂正をせずに済む。 4 個以上の偶数個の誤りでも同じ組み合わせになりうるが、起きる確率がはるかに小さいので、実用上は 2 ビット誤りとして扱う。

ECC メモリ: サーバの ECC メモリは、64 ビットのデータに 8 ビットの検査を付けた\((72,64)\) SECDED 符号を使うのが典型である。これは\(m = 7\)の拡張ハミング符号\((128,120)\)から、情報ビットを 56 本使わない（常に 0 とみなして送らない）ことで得られる短縮符号である。\(H\)の列を 72 本だけ使うことになり、列が互いに異なる性質は保たれるので、SECDED の能力もそのまま保たれる。 1 ビット誤りは自動で訂正し、2 ビット誤りは検出して CPU に例外（machine check exception）を通知する。

5. まとめ

項目内容
パラメータ\((2^m-1,\ 2^m-1-m,\ 3)\)
設計原理\(H\)の第\(i\)列に\(i\)の 2 進表現を置く
符号化1, 2, 4, … 番目を検査ビットにすると、各検査ビットが情報ビットの XOR で決まる
復号シンドロームを整数として読むと誤り位置
能力1 ビット訂正、または 2 ビット検出
最適性完全符号（ハミング限界で等号）
拡張版全体パリティを追加して SECDED（ECC メモリ）

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