データの0と1が途中で一つ入れ替わったとき、「何かが違う」と気づくだけでは、元の値には戻せません。どの位置が変わったのかまで分かる仕組みが必要です。ハミング符号は、複数の検査を少しずつ重ね、検査結果の組み合わせから誤りの位置を絞り込む方法です。4ビットのデータを7ビットにする小さな例で、その働きと限界を見ていきます。
簡単にまとめると？
- ハミング符号(7,4)は、4ビットのデータに3ビットの検査情報を加え、7ビット中の1ビットの誤りを訂正できます。
- 3つの検査がどれだけ失敗したかではなく、どの検査が失敗したかが位置を示します。
- 基本の(7,4)では、2ビットの誤りを1ビットと取り違えて直す場合があります。全体のパリティを加えると、1ビット訂正と2ビット検出を両立できます。
検査を重ねると、場所まで分かる
パリティとは、ある範囲に含まれる1の個数が偶数か奇数かを調べる仕組みです。ここでは、送る時点で各検査範囲の1の個数を偶数にそろえる「偶数パリティ」を使います。その範囲で1ビットだけ反転すると、個数の偶奇が変わり、検査に失敗します。
ただし、全体を一度だけ調べても場所は分かりません。そこで、各ビットが異なる検査の組み合わせに入るようにします。例えば6番目は検査2と検査4に入り、検査1には入りません。このビットだけが反転すれば、検査2と4だけが失敗します。この組み合わせを手掛かりに、6番目を選べるのです。［1］
4ビットに、検査用の3ビットを加える
7個の位置を左から1〜7とし、位置1・2・4に検査ビットを置きます。残る位置3・5・6・7がデータ用です。表中のpは検査ビット、dはデータビットを表します。ここではpの添字を位置番号に合わせています。
| 位置 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|
| 役割 | p1 | p2 | d1 | p4 | d2 | d3 | d4 |
| 例の値 | 0 | 1 | 1 | 0 | 0 | 1 | 1 |
検査1は位置1・3・5・7、検査2は位置2・3・6・7、検査4は位置4・5・6・7を調べます。それぞれ、自分の検査ビットを選べば、その範囲の1の個数を偶数にできます。
データを1011とすると、位置3・5・6・7に順に入ります。検査1のデータ側は1・0・1で1が2個なのでp1は0。検査2は1・1・1で3個なのでp2は1。検査4は0・1・1で2個なのでp4は0です。こうして送る7ビットは0110011になります。これは、本稿で選んだデータによる計算例です。
(7,4)という表記は、全体が7ビット、そのうちデータが4ビットという意味です。符号化率は4/7、約57%です。追加する量は元の4ビットに対して3ビットなので75%増になります。「送る全体に占める検査情報の割合3/7」とは分母が異なります。［2］
検査結果110が、6番目を指す
いま、送った0110011の6番目だけが反転し、0110001で届いたとします。検査1の範囲には1が2個あり、偶数のままです。一方、検査2と検査4の範囲では、それぞれ1が3個、1個になり、どちらも奇数です。
検査に通れば0、失敗なら1として、検査4・2・1の順に並べると110です。この診断用のビット列をシンドロームと呼びます。110を2進数として読むと、4＋2＝6。受け取った列の6番目を反転すれば、0110011に戻ります。
偶然この例だけで成り立つわけではありません。各位置を2進数で書くと、1は001、2は010、3は011、……、7は111です。各検査はその桁が1になっている位置を担当します。そのため、1ビットだけの反転なら、失敗した検査の組み合わせが、その位置の2進数表記と一致します。検査用のビット自体が反転しても、同じ方法で位置を特定できます。［1］
2ビットの誤りを、直してはいけない場所に直す
この方法の前提は、1つの7ビットの組に誤りが高々1個ということです。同じ0110011で、今度は位置3と5が同時に反転した場合を考えます。検査1には両方が含まれるため、偶奇の変化が打ち消し合います。検査2は位置3によって失敗し、検査4は位置5によって失敗します。結果は、また110です。
受信側がこれを「6番目だけの誤り」と解釈して6番目を反転すると、元の列から3か所違う0100101になります。しかも、この列は3つの検査をすべて通ります。検査に合う列になったことと、元のデータに戻ったことは同じではありません。
ハミング符号(7,4)の有効な列どうしは、少なくとも3か所違います。これを最小ハミング距離が3といいます。訂正せずに検査だけするなら、1個・2個の反転による異常は検出できます。しかし、1個を自動訂正しながら、同時にすべての2個の誤りを区別するには情報が足りません。000というシンドロームも、誤りが絶対にない証明にはなりません。3個以上の反転で別の有効な列に変わる場合があるためです。
全体のパリティを1ビット増やす意味
7ビット全体にもう1個、偶数パリティのビットを加えると、拡張ハミング符号(8,4)になります。3つの位置検査に加え、8ビット全体の偶奇を調べられます。誤りが高々2ビットなら、1個の反転は全体の偶奇を変え、2個の反転は変えません。
位置検査が失敗し、全体の偶奇も変わっていれば、元の7ビットのどこか1個が反転したと判断できます。位置検査が失敗しているのに全体の偶奇が変わっていなければ、2個の誤りとして、1個だけを直す操作を止めます。位置検査が正常で全体の偶奇だけが変わった場合は、追加した8番目のビットの誤りです。
このように1ビット訂正と2ビット検出を両立する性質は、SECDED（Single Error Correction, Double Error Detection）と呼ばれます。3ビット以上の誤りまで安全に区別する保証ではありません。
本稿では4ビットの全16通りについて計算しました。基本の(7,4)では全112通りの1ビット反転を訂正でき、全336通りの2ビット反転は、単純に位置を直すと別の有効な列になりました。拡張した(8,4)では、全128通りの1ビット反転を訂正し、全448通りの2ビット反転を検出できました。これは定義した符号の網羅計算であり、実機の故障率や通信性能の測定ではありません。
選ぶときは、訂正できる数と検出できる数を分ける
「誤り訂正機能がある」という説明を読むときには、まず何ビットを一つの保護単位とするかを確認します。次に、何個まで直せるのか、直せない場合にどこまで異常を知らせられるのかを分けます。誤りがまとまって起きる環境では、1個だけという前提から外れやすくなります。
ハミング符号の小さな例は、余分なビットを増やすだけでなく、検査範囲をどう重ねるかが重要だと示しています。受信した列をもっともらしい列へ直せても、その判断が成立する誤りの範囲を超えていれば、元の情報を取り戻せたとは限らないのです。
出典
- MIT 6.02, Hari Balakrishnan, Christopher Terman, George Verghese, Coping with Bit Errors using Error Correction Codes。2012年9月23日更新、§5.3、§5.6–5.7、pp.51–53、58–61。
- 同コース、Linear Block Codes: Encoding and Syndrome Decoding。2012年9月23日更新、§6.1–6.3、pp.65–71。本文のビット列・表・図・全パターン確認は、記載した検査規則による独自計算。両章は同じ講義資料です。