ハミング符号とは？意味をやさしく解説

ハミング符号とは

ハミング符号はデータの誤りを検出し、訂正するための方法として広く利用されています。1950年にリチャード・ハミングによってベル研究所で考案されたこの手法は、線型誤り訂正符号の一種であり、特に1ビットの誤りを修正できる特徴を持ちます。

概要

この符号は、エラー発生率の低い環境での高速なデータ処理を目的に設計されています。例えば、ECCメモリやRAID 2などのストレージシステム、さらにはデータ圧縮ソフトウェアのWinRARにおけるリカバリレコードなど、様々な場面で利用されています。ハミング符号は、他の誤り訂正符号と比較して、処理速度が速いという利点がありますが、その分誤り訂正能力は限られているため、環境によって使い分ける必要があります。

基本概念

ハミング符号は整数 m に基づいて構築されます。符号長 n と情報数 k は以下の式で求められます。

- 符号長: n = 2^m - 1
- 情報数: k = n - m

特に、m = 3 の場合、n = 7、および k = 4 となり、4ビットの元データを7ビットの符号語に変換します。この場合を (7,4) ハミング符号と呼びます。

この符号を実現するためには、検査行列と生成行列という2つの特別な行列を用います。これらの行列は、誤り検出や訂正のための演算に使用されるもので、加算は排他的論理和（XOR）によって行われます。

検査行列と生成行列

検査行列 H は m 行 n 列の行列であり、すべての列の要素が異なり、かつゼロの列は存在しない条件を満たします。例えば、(7,4) ハミング符号における検査行列の一例は以下の通りです。

```
H = [
[1, 0, 1, 1, 1, 0, 0],
[1, 1, 0, 1, 0, 1, 0],
[0, 1, 1, 1, 0, 0, 1]
]
```

一方、生成行列 G は、以下のような条件を満たす非零の行列として定義されます。

```
H G^T = 0
G H^T = 0
```

この行列は組織符号という特別な形で表現されることが多く、生成行列は次のようになります。

```
G = [
[1, 0, 0, 0, 1, 1, 0],
[0, 1, 0, 0, 0, 1, 1],
[0, 0, 1, 0, 1, 0, 1],
[0, 0, 0, 1, 1, 1, 1]
]
```

符号化

符号化のプロセスでは、生成行列 G を使用して送信したいデータとの乗算を行います。例えば、ビット列 `1011` を符号化する場合、出力される符号は以下のようになります。

```
[1, 0, 1, 1] * G = [1, 0, 1, 1, 1, 0, 0]
```

誤り訂正と復号

受信データの復号は、検査行列 H と受信したデータの積を求める形で行われます。誤りが存在しない場合は、受信したデータと検査行列の積がゼロベクトルになります。しかし、一ビットの誤りがある場合、受信データと検査行列を掛けると、その誤りの位置を特定することができます。これにより、誤りがどのビットにあるかを認識し、訂正できます。

たとえば、受信データ `1111100`が誤りを含む場合、検査行列との積を求めることで、その誤りが2番目のビットであることが分かります。これにより、誤りを訂正して元のデータを取り出すことができます。

拡張ハミング符号

通常のハミング符号では、1ビットの誤りを訂正し、2ビットの誤りを検出することが難しいため、拡張ハミング符号という手法が用いられています。これにより、符号語のパリティビットを追加し、1ビットの訂正と同時に2ビットの誤りを検出できるようにします。例えば、ビット列の全状態の排他的論理和を計算し、その結果を符号の末尾に付加します。これによって、より高い誤り検出能力を実現することができます。

参考文献

- Hamming, R. W. (1950). "Error detecting and error correcting codes". Bell System Tech. J. 29: pp. 147-160.
- J.ユステセン、T.ホーホルト、『誤り訂正符号入門』、阪田省二郎、栗原正純、松井一、藤沢匡哉訳、森北出版、2005年、ISBN 4-627-81711-8
- 今井秀樹、『符号理論』、コロナ社、1990年、ISBN 4-88552-090-8
- 情報理論とその応用学会編、『符号理論とその応用』、培風館、2003年、ISBN 4-563-01453-2

ハミング符号