パリティチェックとハミング符号｜やさしい基礎理論

矢沢久雄
2024-08-23 更新

この連載は、基本情報技術者試験の受験者を対象としたものです。
多くの受験者が苦手としている「情報の基礎理論」の分野から毎回１つずつテーマをあげて、やさしくポイント解説と問題解説を行います。
苦手分野を克服して、試験の得点をアップしましょう。

今回のテーマは、「パリティチェック」と「ハミング符号」です。

1 パリティチェックの仕組み
2 ハミング符号の仕組み
3 パリティチェックとハミング符号に関する問題の例（その1）
4 パリティチェックとハミング符号に関する問題の例（その2）

パリティチェックの仕組み

今回のテーマである「パリティチェック（parity check、偶奇検査）」と「ハミング符号（ハミングは、考案者Richard W. Hammingの名前）」は、どちらもデータ通信におけるエラーチェック方式です。

はじめに、パリティチェックの仕組みを説明しましょう。
例として、7ビットの情報に1ビットのパリティビット（検査用ビット）を付加して、全体で8ビットのデータにして送信するとしましょう。

パリティチェックには、「偶数パリティ」と「奇数パリティ」があり、どちらを使うのかを、あらかじめデータの送信者と受信者が取り決めておきます。

偶数パリティの場合は、8ビットの中にある1の数が偶数個になるようにパリティビットを設定します。
たとえば「0101010」という7ビットの情報には1が奇数個あるので、送信者はパリティビットを「1」にして「01010101」という8ビットのデータを送ります。
データの受信者は、受信したデータの1の数を確認し、それが偶数ならエラーがなく、奇数ならエラーがあると判断します。

奇数パリティの場合は、8ビットの中にある1の数が奇数個になるようにパリティビットを設定します。
たとえば「0101010」という7ビットの情報には1が奇数個あるので、送信者はパリティビットを「0」にして「01010100」という8ビットのデータを送ります。
データの受信者は、受信したデータの1の数を確認し、それが奇数ならエラーがなく、偶数ならエラーがあると判断します。

パリティチェックでは、１ビットのエラーを検出できますが、複数ビットのエラーは検出できません。
たとえば、偶数パリティで「01010101」というデータの2か所でエラーが生じて（0と1が反転して）「10010101」となった場合は、データの中にある1の数は偶数個なので、エラーを検出できません。
また、パリティチェックは、エラーを検出できても、どの位置がエラーなのかを特定できないので、エラーの訂正はできません。

ここまでに説明したパリティチェックは、「垂直パリティ」と呼ばれるものです。
パリティチェックの信頼性を向上させるために、「水平パリティ」が使われることもあります。
水平パリティでは、データをいくつか送ったら、「BCC（Block Check Character）」という検査専用のデータを送ります。

たとえば、8ビットのデータを4つ送るたびにBCCを送る場合には、図１に示したように4つのデータの同じ位置（縦方向に見て同じ桁位置）でパリティビット（ここでは偶数パリティを使います）を設定した8ビットのデータがBCCです。
データごとに垂直パリティをチェックし、さらにブロック（4つのデータのまとまり）ごとに水平パリティをチェックすることで、エラーを検出する精度が高まり、信頼性が向上します。

【図1】　垂直パリティと水平パリティの例

　1個目のデータ 01010101　・・・赤色は垂直パリティ
　2個目のデータ 01010000　・・・赤色は垂直パリティ
　3個目のデータ 01001101　・・・赤色は垂直パリティ
　4個目のデータ 01000100　・・・赤色は垂直パリティ
　　　　　　BCC 　 00001100　・・・青色は水平パリティ

ハミング符号の仕組み

次に、ハミング符号の仕組みを説明しましょう。

パリティチェックは、エラーの検出ができても、訂正はできませんでしたが、ハミング符号は、エラーの検出と訂正ができます。
エラーの位置を特定できるからです。
そのために、ハミング符号では、パリティチェックよりも多くの検査用ビットを使います。

例として、4ビットの情報に3ビットの検査用ビットを付加して、全体で7ビットのデータ（このデータを「ハミング符号」と呼びます）にして送信するとしましょう。
x1、x2、x3、x4の4ビットに、p1、p2、p3の3ビットを付加して、[x1][x2][x3][p3][x4][p2][p1]という順序のデータにします。
（※区切りがわかりやすいように[ ]で囲んでいます）
この順序にする理由は、すぐ後で説明します。

p1、p2、p3の値は、図2に示した式で決めます。

たとえば、4ビットの情報が0101なら、x1＝0、x2＝1、x3＝0、x4＝1であり、p1＝0 XOR 0 XOR 1＝1、p2＝0 XOR 1 XOR 1＝0、p3＝0 XOR 1 XOR 0＝1なので、ハミング符号は[x1][x2][x3][p3][x4][p2][p1]＝0101101です。

【図2】　ハミング符号の検査ビットを決める式

　p1 ＝ x1 XOR x3 XOR x4
　p2 ＝ x1 XOR x2 XOR x4
　p3 ＝ x1 XOR x2 XOR x3

[x1][x2][x3][p3][x4][p2][p1]という順序にするのは、誤りのある位置の特定を容易にするためです。

図3に示したように、p1、p2、p3を求める式に、1、2、4という重みを割り当てると、重みの足し算で誤りのある位置がわかります。

たとえば、もしも、重み1の式と重み2の式が誤りなら、それらの両方に含まれているのはx4なので、x4が誤りです。
このx4の位置（最下位ビットを1ビット目とした位置）は、誤りのある式の重みを足した1＋2＝3ビット目で求められます。

【図3】　式に割り当てた重みで、誤りのある位置を特定できる

　p1 ＝ x1 XOR x3 XOR x4　・・・重み1
　p2 ＝ x1 XOR x2 XOR x4　・・・重み2
　p3 ＝ x1 XOR x2 XOR x3　・・・重み4

　 7 　 6 　 5 　 4 　 3 　 2 　 1　　・・・位置
　[x1][x2][x3][p3][x4][p2][p1]

　・どの式にも誤りがないなら、データに誤りはない。
　・重み1の式だけが誤りなら、1ビット目のp1が誤りである。
　・重み2の式だけが誤りなら、2ビット目のp2が誤りである。
　・重み1と重み2の式が誤りなら、1＋2＝3ビット目のx4が誤りである。
　・重み4の式だけが誤りなら、4ビット目のp3が誤りである。
　・重み1と重み4の式が誤りなら、1＋4＝5ビット目のx3が誤りである。
　・重み2と重み4の式が誤りなら、2＋4＝6ビット目のx2が誤りである。
　・重み1と重み2と重み4の式が誤りなら、1＋2＋4＝7ビット目のx1が誤りである。

パリティチェックとハミング符号に関する問題の例（その1）

パリティチェックとハミング符号に関する問題を2つ紹介しましょう。
はじめは、パリティチェック（垂直パリティ）の記述を選ぶ問題です。

問1（出典：H25春問4）

通信回線の伝送誤りに対処するパリティチェック方式（垂直パリティ）の記述として、適切なものはどれか。

　ア　　1ビットの誤りを検出できる。
　イ　　1ビットの誤りを訂正でき、2ビットの誤りを検出できる。
　ウ　　奇数パリティならば1ビットの誤りを検出できるが、偶数パリティでは1ビットの誤りも検出できない。
　エ　　奇数パリティならば奇数個のビット誤りを、偶数パリティならば偶数個のビット誤りを検出できる。

パリティチェックは、ビットの誤りを検出できるので、選択肢アは適切です。

パリティビットは、誤りを検出できても訂正ができないので、選択肢イは不適切です。
パリティチェックでは、偶数パリティでも基数パリティでも、１ビットの誤りを検出できることに変わりはないので、選択肢ウとエは不適切です。

したがって、選択肢アが正解です。

パリティチェックとハミング符号に関する問題の例（その2）

次は、ECCメモリで用いられているエラーチェック方式を選ぶ問題です。
選択肢の中には、パリティチェックとハミング符号だけでなく、チェックサムというエラーチェック方式もあります。

問2（出典：H18春問23）

ECCメモリで、2ビットの誤りを検出し、1ビットの誤りを訂正するために用いるものはどれか。

　ア　偶数パリティ　　　イ　垂直パリティ　　　ウ　チェックサム　　　エ　ハミング符号

ECCメモリは、エラーの検出と訂正が可能なメモリです。
ECCは、Error Checking and Correcting（エラーの検出と訂正）という意味です。
パリティチェックは、エラーの検出ができても訂正ができませんが、ハミング符号はエラーの検出と訂正ができます。

したがって、選択肢エが正解です。

選択肢ウのチェックサムは、データをいくつか送ったら、データの合計値を検査用のデータ（これをチェックサムと呼びます）として送るというエラーチェック方式です。
たとえば、12、34、56、78という4個のデータを送ったら、チェックサムとして12＋34＋56＋78＝180を送ります。
チェックサムは、それまでに送ったいずれかのデータにエラーがあることを検出できますが、データの訂正はできません。

基本情報技術者試験の公開問題を見ると、過去問題（過去の試験に出題された問題）の再利用が多いことがわかります。
したがって、試験に合格するために最も効率的で効果的な学習方法は、できなかった問題があれば、できるようになるまで練習することです。
もしも、今回取り上げた問題がすぐにできなかったら、できるようになるまで練習してください。

それでは、またお会いしましょう！