エラー訂正符号(Error Correction Code)

再送と並んで広く用いられているエラー訂正法にエラー訂正符号がある。エラー検出と同様に、エラー訂正符号もデータにチェックビットを付けるのであるが、単にエラーを見つけるだけでなく、元のデータが推測できるようにチェックビットを付ける。

図2.13 コードワード間の距離が3あれば1ビットエラーの球は重ならない

前に述べたように、1ビットエラーのワードは元のコードワードから距離1離れたところに位置する。つまり、 n次元2進空間でコードワードを中心とした半径1の球の中にある。図2.13に示すように、すべてのコードワード間の距離が3かそれ以上であれば、各コードワードを中心とする1ビットエラーの球は重ならない。したがって、受信したデータがコードワード1を中心とする黄色の球の中にあれば、送られたのはコードワード1であると推定でき、それがコードワード2を中心とする緑の1ビットエラーの球の中にあれば、送られたのはコードワード2であると推定できる。

コードワード間の距離を3以上にする1つの方法は、送信するデータの後に、チェックビットとしてデータと同じものを2回付けるという風にすればよい。コードワード1と2のデータ部が1ビットしか異なっていない場合でも、同じものが2回チェックビットに含まれるので、全体としては3ビットが異なり距離は3となる。そして、このコーディングの場合は同じデータが3回送られてくるので、どれかの1回にエラーがあってもビットごとの多数決を取れば、正しいデータに戻すことができる。

このような3回繰り返してデータを送る方法は最小距離3のコードワード群を作り出す1つの方法であるが、チェエクに必要なビット数という点では効率が良いとは言えない。3回の繰り返しほど多数のチェックビットを使わないで、最小距離3のコードワードを作り出す1つの方法がハミングコードである。

図2.14 4ビットのデータに3ビットのチェックビットを付けるハミングコードのHマトリクス

図2.14はコード長7ビットのハミングコードを生成するHマトリクスと呼ばれる行列である。この行列は各列を縦にみると、第1列は001、次は010、011というように2進数が昇順にならんでいる。そして、各列に1が1個しかない列をチェックビット、2個以上の1がある列をデータビットとし、それぞれC0～C2、D0～D3と名付ける。