基本情報のハミング符号を検査ビットと誤り訂正の例題で理解する

基本情報のハミング符号は、「誤りを見つける」だけでなく、条件の範囲内で「誤った位置を特定して直す」仕組みです。検査式がいくつも並ぶと難しく見えますが、各式の結果を組み合わせて、どの位置を反転するかを判断する問題だと考えると整理できます。

この記事では、4ビットの情報に3ビットの検査用ビットを加える、7ビットのハミング符号を扱います。番号の付け方と偶数パリティを最初に固定し、情報の配置、検査ビットの計算、受信後の訂正、情報の取り出しまでを一つの例で追います。

大切な前提は、基本形の訂正手順が「誤りが高々1ビット」という条件で働くことです。2ビット以上の誤りを同じ手順で必ず直せるわけではありません。計算方法と限界を一緒に押さえ、パリティチェックとの違いを説明できる状態を目指しましょう。

基本情報のハミング符号の仕組み

検出と訂正の違いをつかむ

通信や記憶の途中で、ビットの0と1が反転することがあります。受け取ったビット列だけを見ても、もともとその値だったのか、途中で変わったのかは分かりません。そこで、情報そのものに加えて、正しさを検査するための冗長なビットを付けます。

単純な偶数パリティは、対象のビット列に含まれる1の個数が偶数になるよう、検査用の1ビットを加えます。1ビットだけ反転すれば偶奇が変わるので、異常に気付けます。ただし、どの位置が反転したかを、この一つの結果だけで一意に決めることはできません。

ハミング符号では、異なる組合せのビットを複数回検査します。ある位置の誤りなら検査Aと検査Bが失敗し、別の位置なら検査Bだけが失敗する、といった違いを作ります。失敗の組合せを位置と対応させることで、1ビットの誤りを特定できます。

MITの誤り訂正符号の講義資料では、複数のパリティ検査を使うハミング符号の構成が説明されています。ここで覚えたいのは、検査を何回も繰り返すだけではなく、位置ごとに異なる検査の組合せを割り当てることです。

例えば、七つの棚を調べるときに、毎回すべての棚を同じように検査しても、異常の場所は絞れません。検査対象を変え、各棚に固有の結果が現れるよう設計する必要があります。これが、位置番号の二進表現を使う理由につながります。

7ビットの配置を固定する

この記事では、送る7ビットを左からx1、x2、x3、x4、x5、x6、x7と呼びます。位置1、2、4に検査ビットを置き、位置3、5、6、7に情報ビットを置きます。位置の数え方は教材によって異なるため、実際の試験では問題文の定義を優先してください。

検査ビットを置く位置は1、2、4で、二進数では001、010、100です。一つだけ1が立つ位置に対応します。残りの位置3、5、6、7は、それぞれ011、101、110、111となり、複数の検査で調べる位置になります。

位置	二進表現	この記事での役割
1	001	検査ビットp1
2	010	検査ビットp2
3	011	情報ビットd1
4	100	検査ビットp4
5	101	情報ビットd2
6	110	情報ビットd3
7	111	情報ビットd4

学習用の情報を1101とします。左からd1、d2、d3、d4へ順に対応させるので、x3=1、x5=1、x6=0、x7=1です。この時点では検査ビットが未定なので、並びは「p1、p2、1、p4、1、0、1」と書けます。

いきなり7桁を暗記して書くより、位置番号を書いた下に情報を入れる方が安全です。情報の4桁を位置1から連続して入れてしまうと、後の検査式が正しくても違う符号になります。最初の配置が計算全体の土台です。

「7ビットの符号」と「7ビットの情報」も区別しましょう。この例の符号長は7ビットですが、元の情報は4ビットです。残りの3ビットは検査のために加えたものなので、利用者へ渡す情報へそのまま混ぜないようにします。

検査対象を二進数で選ぶ

検査p1では、位置番号の一番下の桁が1となる位置1、3、5、7を調べます。検査p2では下から二番目の桁が1となる位置2、3、6、7、検査p4では下から三番目の桁が1となる位置4、5、6、7を調べます。

位置5を例にすると、二進表現は101です。下の桁と三番目の桁が1なので、p1とp4の検査対象になります。p2の対象ではありません。位置6なら110なので、p2とp4の対象です。この違いが、誤りを位置5と位置6へ区別する目印になります。

対象位置を毎回丸暗記する必要はありません。位置番号を001から111まで書き、それぞれの列で1になっている行を選べば再現できます。検査式が問題文で与えられている場合は、その式をそのまま使い、この記事の配置へ勝手に置き換えないでください。

偶数パリティでは、対象ビットの排他的論理和が0になるようにします。0 XOR 0と1 XOR 1は0、0 XOR 1と1 XOR 0は1です。四つの値なら順番にXORしても、1の個数の偶奇を数えても同じ結果になります。

XORと普通の足し算を混同しないようにしましょう。1 XOR 1は0ですが、普通の加算なら2です。「mod2で計算」と指定されているときは、合計を2で割った余りを使います。1が三つなら余りは1、四つなら余りは0、と確認できます。

検査ビットを求めて送信する

情報1101を入れた並びは「p1、p2、1、p4、1、0、1」でした。p1の対象にある情報ビットはx3、x5、x7なので、値は1、1、1です。すでに1が三つで奇数のため、p1を1にして、全体の1を四つにします。

p2の対象にある情報ビットはx3、x6、x7で、値は1、0、1です。1が二つで偶数なので、p2は0です。p4の対象にある情報ビットはx5、x6、x7で、こちらも1、0、1です。したがってp4も0になります。

求めた値を戻すと、送信する符号語は1010101です。最後に、位置1、3、5、7の1の個数は四つ、位置2、3、6、7では二つ、位置4、5、6、7でも二つ、と三つの検査がすべて偶数になることを確認します。

この「作った直後に検査する」工程は重要です。送信側で検査ビットを計算し間違えたのに、受信側の訂正処理へ進むと、どこが原因か分かりにくくなります。配置、検査値、完成した7桁を分けて確認すれば、手順のどこで間違えたかを追えます。

情報を符号化することは、内容を秘密にする暗号化ではありません。この並び方を知っていれば、情報を取り出せます。ハミング符号が主に扱うのは誤りへの備えであり、盗聴への対策とは目的が違います。冗長なビットを付けたことを、そのまま情報の機密性と結び付けないようにしましょう。

基本情報のハミング符号を例題で解く

検査結果から位置を特定する

送信した1010101の位置5だけが反転し、受信側では1010001になったとします。以下はこの記事独自の学習用の設定です。受信側は送信時の正しい列を直接知るのではなく、受信した列に三つの検査を行って判断します。

s1=x1 XOR x3 XOR x5 XOR x7、s2=x2 XOR x3 XOR x6 XOR x7、s4=x4 XOR x5 XOR x6 XOR x7と定義します。s1は1 XOR 1 XOR 0 XOR 1で1、s2は0 XOR 1 XOR 0 XOR 1で0、s4は0 XOR 0 XOR 0 XOR 1で1です。

したがって、検査結果はs1=1、s2=0、s4=1となります。位置番号として読むときはs4、s2、s1の順なので、101という二進数です。十進数へ直すと4×1＋2×0＋1×1=5です。高々1ビットの誤りという前提の下では、位置5が誤りと判断できます。

もし三つの結果がすべて0なら、1ビットまでの誤りという前提の下では反転する位置がないと判断します。ただし、誤りの個数という前提を外した場合、000だけで完全な無誤りを証明することはできません。複数の反転が重なって検査を通ることもあるためです。

ここでの101は、三つの検査結果を重み4、2、1で並べたものです。受信した情報の3桁でも、反転するビットの値でもありません。失敗した検査の組合せから位置を表す値を作っている、と意味まで確認しましょう。

ニューブランズウィック大学の復号解説では、検査結果と誤りパターンを対応させる考え方が示されています。シンドロームという用語は、この検査結果の組を指します。名称より先に、結果から位置を求める流れを再現できれば大丈夫です。

反転してから情報を取り出す

誤り位置が5と分かったので、受信した1010001の左から5番目を反転します。そこは0なので1へ変え、訂正後は1010101になります。ほかのビットは変更しません。求めた番号をビットの値と取り違え、末尾へ数字を加える処理ではありません。

訂正後にも同じ三つの検査を行います。位置1、3、5、7は1、1、1、1で偶数、位置2、3、6、7は0、1、0、1で偶数、位置4、5、6、7は0、1、0、1で偶数です。シンドロームが000に戻ることを確認できます。

続いて、情報を置いた位置3、5、6、7の値を順に読みます。結果は1、1、0、1で、元の情報1101です。訂正した7ビットの列と、取り出した4ビットの情報の両方を書いておくと、問題がどちらを問うているかに対応しやすくなります。

別の学習用の例として、情報0110を同じ規則で符号化すると1100110になります。この符号の位置2が反転して1000110になった場合、s1=0、s2=1、s4=0です。シンドローム010は十進数2なので、検査ビットそのものの誤りも位置を特定できます。

「情報の位置だけが訂正対象」と決めつけないことが大切です。7ビットのどこか一つという条件なら、検査ビットも含めて扱います。ただし、問題文が情報部分の誤りに限定していたり、独自の対応表を示したりしている場合は、その条件に従います。

検査ビット数と距離の意味

検査ビットがr個あれば、検査結果の組合せは2のr乗通りあります。1ビットの誤りを訂正するには、各位置の誤りと、誤りがない状態を区別できなければなりません。情報をmビット、検査をrビットとすれば、少なくともm＋r＋1通りを表せる必要があります。

したがって、この基本形では2のr乗がm＋r＋1以上となるかを調べます。情報4ビットなら、r=2では4通りしかなく、必要な7通りへ届きません。r=3なら8通りで、4＋3＋1=8を満たします。これが情報4ビットに検査3ビットを加える理由の一つです。

情報ビット数を変えた場合も、候補のrを小さい方から代入して確認できます。情報11ビットならr=4で、16が11＋4＋1=16以上となります。情報12ビットでは同じr=4だと、16が12＋4＋1=17へ届きません。r=5なら32が12＋5＋1=18以上となります。検査ビットを増やすと、その追加分も検査される位置として右辺へ入る点に注意します。

ただし、この不等式を満たすというだけで、検査式をどう選んでも訂正できるわけではありません。誤り位置ごとに異なる結果が出るよう構成する必要があります。不等式は、区別に必要な組合せ数を確認する条件として使います。

ハミング距離は、二つの同じ長さのビット列を比べて、値が異なる位置の個数を数えたものです。例えば1010101と0100101は、位置1、2、3が異なるので距離は3です。数を十進数として引き算した差や、1の個数そのものではありません。

有効な符号語の間隔が十分にあれば、受信した列がどの符号語に近いかで訂正を考えられます。通常の7ビットのハミング符号では最小距離が3で、1ビットの誤りを訂正できます。距離と能力の関係は、同大学のハミング符号の説明でも確認できます。

2ビット誤りを直せない理由

通常の7ビットのハミング符号を、1ビット訂正の手順で復号する場合、2ビット誤りを1ビット誤りと必ず区別できるわけではありません。「シンドロームが0以外なら、その番号を必ず反転すればよい」と条件を外して覚えると、別の正しい符号語へ誤って変更することがあります。

例えば、正しい1010101の位置1と位置2が反転すると、受信列は0110101です。検査するとs1=1、s2=1、s4=0なので、結果を位置番号へ読むと3になります。1ビット誤りだと思って位置3を反転すると、0100101になります。

この0100101は検査を通りますが、元の1010101とは違います。取り出した情報も変わります。検査結果が0へ戻ったという事実だけで、複数ビット誤りを含むどんな受信列でも正しく復元したと保証できないことが分かります。

一方、有効な符号語かどうかだけを調べ、訂正をしない使い方なら、最小距離3の符号では2ビット誤りを検出できます。「2ビットの異常に気付く能力」と「1ビットを訂正しつつ2ビット誤りも区別する能力」は同じではありません。問題が検出のみか、自動訂正まで行うかを確認しましょう。

通常の7ビット符号へ全体のパリティをさらに加えた拡張ハミング符号は、1ビット訂正と2ビット検出を組み合わせる代表例です。SECDEDという表現に出会ったら、単一誤りの訂正と二重誤りの検出を指すと整理します。ただし、これも任意の個数の誤りを処理できるという意味ではありません。

基本情報のハミング符号のまとめ

解く順序は、位置番号と偶奇の規則を確認し、受信列を検査式へ入れ、シンドロームから誤り位置を求める、です。その後に指定位置を反転し、再検査してから情報ビットを取り出します。問題が符号語を問うのか情報を問うのかで、最後の答えが変わります。

よくある計算ミスは、位置を右から数えてしまうこと、s1・s2・s4を重みと逆順に並べること、XORを普通の加算として扱うことです。受信列の上に位置番号を書き、検査結果の横へ重み1・2・4を明記すれば、見直す場所がはっきりします。

パリティだけの検出を復習したい場合は、基本情報のパリティチェックの計算と検出限界を、XORの操作で迷う場合は基本情報の論理演算と真理値表を確認してください。この記事の中心は、複数の検査結果を位置へ対応させることです。

まずは情報1101の符号化と、位置5の誤り訂正を、自分の手で最初から再現してみましょう。続けて検査ビットが誤る例を一つ試すと、情報部分しか直せないという誤解を防げます。関連分野の確認には基本情報の過去問アプリも使えますが、この独自例題と同じ問題の収録を保証するものではありません。