誤り検出・訂正符号とは？

誤り検出・訂正符号の意味

データ伝送・記憶時のビット化けを検出、あるいは自動的に訂正するための冗長データを付加する技術。パリティビットは1ビットの誤り検出、ハミング符号は1ビット誤りの検出と訂正、CRC（巡回冗長検査）は伝送誤りの検出に使われる。

誤り検出・訂正符号の具体例

7ビットのデータに1ビットの偶数パリティを付加すると、1ビットのビット反転が起きた場合にパリティの偶奇が崩れることで誤りを検出できる。ハミング符号はさらに誤りの発生位置を特定して自動訂正できる。

誤り検出・訂正符号は試験でどう引っ掛けられる？

パリティビットは誤りの「検出」はできても、どのビットが誤ったかの特定や「訂正」は基本的にできない。

誤り検出・訂正符号と関連する用語

• 2進数と論理演算の基礎

誤り検出・訂正符号が出た過去問

• WANを介して二つのノードをダイヤルアップ接続するときに使用されるプロトコルであり，リンク制御やエラー処理機能をもつものはどれか。

  正解：PPP

  要点：PPPはリンク制御とエラー処理をもつ2点間接続プロトコル

  PPPは2点間を接続するデータリンク層のプロトコルで、リンクの確立・維持・切断を行うリンク制御機能や、誤り検出などのエラー処理機能をもつ。認証や複数の上位プロトコルの多重化にも対応している。

  出典：平成29年度 春期 応用情報技術者試験 午前 問33（IPA）

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

  正解：ハミング符号

  要点：ハミング符号は1ビット誤り訂正と2ビット誤り検出を担う。

  ハミング符号は、データビットに複数の検査ビットを付加し、誤りの有無だけでなく誤った位置まで特定できる誤り訂正符号である。メモリ（ECCメモリ）では一般にSEC-DED方式として用いられ、1ビット誤りの訂正と2ビット誤りの検出を同時に実現する。パリティやチェックサムは検出のみで、訂正はできない。

  出典：平成30年度 秋期 応用情報技術者試験 午前 問9（IPA）

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

  正解：0110011

  要点：ハミング符号は不成立の検査式の共通ビットが誤り位置

  与えられた符号1110011をX1X2X3P3X4P2P1＝1,1,1,0,0,1,1と対応させ、3つの検査式を計算する。P1の式は1⊕1⊕0⊕1＝1、P2の式は1⊕1⊕0⊕1＝1、P3の式は1⊕1⊕1⊕0＝1と、3式すべてが0にならない。3つの式すべてに共通して現れるのはX1だけなので、誤りビットはX1であり、これを0に反転した0110011が正しい符号となる。

  出典：平成30年度 春期 応用情報技術者試験 午前 問3（IPA）

• 3ビットのデータx1, x2, x3に偶数パリティビットcを付加する回路はどれか。

  正解：回路図ウ：x1,x2,x3を入力とし、x1,x2をXOR素子に入力、その出力とx3をXOR素子に入力してcを出力する論理回路（出力x1,x2,x3はそのまま通過）

  要点：偶数パリティは全データビットのXORで生成できる

  偶数パリティは、データビットとパリティビットを合わせた1の個数が偶数になるように付加します。これは各ビットの排他的論理和（XOR）を取ることと同じで、c = x1 XOR x2 XOR x3 で求まります。したがってXORを2段に接続し、出力に否定を付けない回路が正解です。

  出典：令和1年度 秋期 応用情報技術者試験 午前 問23（IPA）

• メモリの誤り検出及び訂正を行う方式のうち、2ビットの誤り検出機能と、1ビットの誤り訂正機能をもつものはどれか。

  正解：ハミング符号

  要点：ハミング符号は1ビット訂正・2ビット検出ができる

  ハミング符号は複数の検査ビットを付けることで、1ビットの誤りなら位置を特定して訂正でき、2ビットの誤りは検出できる（SEC-DED）。パリティやチェックサムは誤りの有無を知るだけで、誤った位置を特定できないため訂正はできない。

  出典：令和2年度 10月 応用情報技術者試験 午前 問10（IPA）