データの誤り制御（パリティビット・CRC・ハミング符号）とは？

データの誤り制御（パリティビット・CRC・ハミング符号）の意味

通信や記憶で生じるビット化けを検出・訂正する仕組み。パリティビットは1ビットの誤り検出、CRC（巡回冗長検査）は多ビットの誤りを高精度に検出、ハミング符号は誤り検出に加えて1ビット誤りを自動訂正できる。

データの誤り制御（パリティビット・CRC・ハミング符号）の具体例

偶数パリティでは、データ中の1の個数が偶数になるようにパリティビットを付加する。受信側で1の個数を数え、奇数になっていれば伝送中に誤りが生じたと判断できる。

データの誤り制御（パリティビット・CRC・ハミング符号）は試験でどう引っ掛けられる？

パリティビットは誤り「検出」はできても、単純な奇数・偶数パリティだけでは誤り箇所の「訂正」はできない（訂正まで行えるのはハミング符号）点を混同しやすい。

データの誤り制御（パリティビット・CRC・ハミング符号）が出た過去問

• メモリの誤り制御方式で、2ビットの誤り検出機能と、1ビットの誤り訂正機能をもたせるのに用いられるものはどれか。

  正解：ハミング符号

  要点：ハミング符号は1ビット訂正・2ビット検出（SEC-DED）

  ハミング符号は、データビットに複数の検査ビット（冗長ビット）を付加し、誤りの位置を特定できるようにした誤り訂正符号である。一般にSEC-DED（拡張ハミング符号）として用いられ、1ビットの誤りは訂正でき、2ビットの誤りは訂正はできないが検出できる。このためメモリのECC（誤り訂正符号）として広く使われている。

  出典：平成30年度 秋期 高度共通_午前I試験 am1 問5（IPA）

• ハミング符号とは、データに冗長ビットを付加して、1ビットの誤りを訂正できるようにしたものである。ここでは、X1、X2、X3、X4の4ビットから成るデータに、3ビ…

  正解：0110011

  要点：不成立の検査式すべてに共通するビットが誤りビット

  符号1110011は左からX1=1, X2=1, X3=1, P3=0, X4=0, P2=1, P1=1である。三つの検査式を計算すると、X1⊕X3⊕X4⊕P1＝1、X1⊕X2⊕X4⊕P2＝1、X1⊕X2⊕X3⊕P3＝1となり、いずれも0にならない。三つすべての式に共通して現れるのはX1だけなので、誤っているのはX1である。X1を0に訂正すると0110011となり、三つの式がすべて0になることが確かめられる。

  出典：平成30年度 春期 高度共通_午前I試験 am1 問1（IPA）

• 図のように16ビットのデータを4×4の正方形状に並べ、行と列にパリティビットを付加することによって何ビットまでの誤りを訂正できるか。ここで、図の網掛け部分はパリ…

  正解：1

  要点：水平垂直パリティは1ビット誤りだけ訂正できる

  行方向と列方向の両方に1ビットずつ偶数パリティを付ける水平垂直パリティでは、1ビット誤りが起きると誤った行と誤った列が同時に検出され、その交点として誤り位置を一意に特定できる。位置が分かれば反転させて訂正できるので、訂正能力は1ビットである。2ビット以上の誤りは検出できても位置が絞り込めず訂正はできない。

  出典：令和3年度 秋期 高度共通_午前I試験 am1 問2（IPA）

• 図のように16ビットのデータを4×4の正方形状に並べ、行と列にパリティビットを付加することによって何ビットまでの誤りを訂正できるか。ここで、図の網掛け部分はパリ…

  正解：1

  要点：水平垂直パリティの訂正能力は1ビット

  行と列の両方向にパリティビットを付ける水平垂直パリティでは、1ビット誤りが生じるとパリティ違反の行と列が1つずつ現れ、その交点として誤り位置を一意に特定できる。位置が分かればビットを反転して訂正できるので、訂正できるのは1ビットまでである。2ビット以上では位置を絞り込めない。

  出典：令和5年度 秋期 高度共通_午前I試験 am1 問2（IPA）

• 符号長7ビット、情報ビット数4ビットのハミング符号による誤り訂正の方法を、次のとおりとする。 受信した7ビットの符号語 x1 x2 x3 x4 x5 x6 x7…

  正解：1010101

  要点：c0・c1・c2からi＝3を求め3ビット目を反転する

  受信語1000101をx1〜x7とすると、c0＝x1+x3+x5+x7＝1+0+1+1＝1、c1＝x2+x3+x6+x7＝0+0+0+1＝1、c2＝x4+x5+x6+x7＝0+1+0+1＝0（いずれもmod 2）。i＝1+1×2+0×4＝3となるので、左から3ビット目を反転する。1000101の3ビット目0を1にして1010101が得られる。

  出典：令和6年度 春期 高度共通_午前I試験 am1 問2（IPA）