【応用情報】データの誤り制御：パリティチェックとハミング符号について解説

この記事ではデータの誤り制御方法であるパリティチェックとハミング符号について解説します。

応用情報ではパリティチェックとハミング符号に関する問題が出題されます。是非最後までご覧ください。

データの誤りとは

データの誤りとは、ビットの内容が0→1や1→0に意図せず変わってしまうことです。
データは0と1のビットの集まりで表現されますが、実体はただの電気信号です。
なので、伝送中に他の電気信号から干渉があれば電気信号が乱れることもありますし、長距離移動すれば電気信号が衰退することもあります。そんな理由から途中でデータの内容が微妙に変わってしまうことがあります。

そこでデータの誤りを検知したり、修正するためにパリティチェックやハミング符号という技術が使われます。

パリティチェック

パリティチェックでは、データのビット列に対してパリティビットと呼ばれる誤り検知用のビットを与えることでデータの誤りを検知します。

例えば偶数パリティで「1010000」というデータを送るとします。その時のパリティビットは0になりますね。
しかし、データを受信した時に、データの一部が化けており「1110000」となっていれば、パリティビットと整合性が取れずにどこかがおかしいことが分かります。

しかし、偶数パリティで出来るのは「どこか1ビットが誤っていること」を検知するだけです。どこが誤っているかということは分からないので、誤りの訂正も出来ません。（奇数パリティも同じです）

水平垂直パリティチェック

水平垂直パリティチェックでは、縦と横からパリティチェックを行います。
例えば、「Hello」とデータを送る時、偶数パリティを使うとパリティビットはこうなります。

水平垂直パリティチェックでは、1ビットの誤りなら特定して訂正することが出来ます。

2ビット以上誤りがある場合は、誤りの位置を特定することは出来ません。

ハミング符号

ハミング符号は、データのビット列に対して検査用の冗長ビットを与えることで誤りを検知する技術です。

4ビットのデータに3ビットの検査用ビットを付与する場合を考えます。
元のデータからビットを抜き取るパターンを3つ作り、1の数が偶数個になるように検査用ビットを設定します。少し難しい表現をすると、それぞれの組合せの排他的論理和が検査用ビットとなります。そして、元のデータに検査用ビットをくっつけたものを送信データとします。

受信者は受信データから組合せ①～③を作り、それぞれの検査用ビットと合わせて1の数が偶数個かどうか検証します。難しい表現をすると、それぞれの排他的論理和が0になるはずです。

仮に伝送の途中でデータのビット列がおかしくなっていたらどうなるでしょうか。
排他的論理和を取った時に1になる組合せが出てきます。よって、データに誤りがあると判断出来るわけです。

2ビットまでの誤り検出と1ビットの誤り訂正が可能

ハミング符号は2ビットまでの誤り検出と1ビットの誤り訂正が可能であると言われます。
検証してみましょう。

もし、送信データのうち1ビット誤りがある場合、このようになります。
全てのパターンで排他的論理和のどれかが1になっていますね。よって、1ビットの誤りは検知可能です。

次に送信データのうち2ビット誤りがある場合、このようになります。
これも全てのパターンで排他的論理和のどれかが1になり、誤りを検知できることが分かります。

では、送信データのうち3ビット誤りがある場合、どうなるでしょうか。
誤りがあるのに、排他的論理和が全て0になることがあります。これでは誤りは検知出来ませんよね。よって、ハミング符号では2ビットまでの誤りは検知出来るが、3ビットの誤りは検知出来ないということが分かります。

では、誤りがあったとしても2ビットまでである場合、
全ての排他的論理和が1になっている時は1番目のビットに誤りがあると特定出来ます。
他のパターンで全ての排他的論理和が1になるパターンは無いですからね（誤りが2ビット以下であるという前提の場合）。よって、この場合のみ誤りの訂正が可能になります。

応用情報技術者試験での出題例

令和6年度春期問4

令和5年度秋期問4、令和3年度秋期問4

令和4年度春期問4