誤り検出・訂正

この記事での学習内容 基本情報 応用情報

偶数パリティ、奇数パリティなど、信頼性を高める技術の考え方、仕組みを理解する。

用語例: CRC、ハミング符号、パリティチェック、ECC、チェックサム

誤り検出・訂正

伝送路城の信号は、ノイズやタイミングのズレなどの影響で、データを正しく伝送できないことがあります。これを「伝送誤り」や「伝送エラー」といいます。伝送誤りがあると、送られたデータは破損してしまいます。正しくデータを送るためには、伝送誤りを検出したり、訂正する必要があります。これらの伝送誤りを検出したり、訂正したりすることを「誤り制御」と呼びます。

誤り制御は「誤り検出」と「誤り訂正」に大別されます。

誤り検出

誤り検出は伝送誤りの検出を行うことです。送信側は誤り検出のための情報を付加して送信し、受信側は誤り検出のための情報を使って、受信したデータをチェックします。

誤りが検出されると、受信したデータを破棄したり、送信側に再送信を要求したりします。

代表的な誤り検出の方式は「パリティチェック」「チェックサム」「CRC」などがあります。
方式により、付加される誤り検出のための情報のサイズや誤り検出の精度が異なってきます。

誤り訂正

誤り訂正は伝送誤りの訂正を行うことです。送信側は誤り訂正のための情報を付加して送信し、受信側は誤り訂正のための情報を使って誤りを検出、必要があれば正しいデータを復元します。

そのため、誤り検出と異なり、送信側に再送信を要求する必要はありません。但し、誤り訂正のための情報は、誤り検出のための情報より大きくなるため、その分通信の効率は低下します。

パリティチェック

パリティとは、値が1のビットの個数が偶数か奇数かをチェックする方式です。送信するビット列に誤り検出用のビット(パリティビット、冗長ビット)を付け加える検出方式です。

偶数パリティと奇数パリティの2つの方式に分かれており、偶数パリティの場合、付加すると値が1のビットが偶数個になり、奇数パリティの場合は値が1のビットが奇数個になります。

ただし、パリティチェックでは誤り検出は出来ても、どのビットに誤りがあるか判断できないため、誤り訂正は出来ません。

パリティチェックはどの方向にパリティビットを付け加えるかによって、垂直パリティと水平パリティの2種に分けられ、さらに両者を組合せた垂直水平パリティという方式もあります。

垂直パリティ

垂直パリティは送信するデータのビット列のまとまり毎(文字単位など)に、1ビットのパリティビットを付け加える方法です。

この方式の場合、どのビット列のまとまり(文字)に誤りがあったかが検出できます。

水平パリティ

水平パリティでは、送信するデータのビット列の同じ位置毎にパリティビットを付け加える方式です。

この方式の場合、どの位置のビットに誤りがあったかが検出できます。

また、データの量(文字数)が増えてもひとまとまりにするビット数が変わらない限りはパリティビットの数が変わりません。

垂直水平パリティ

垂直パリティと水平パリティを組み合わせることによって、1ビットの誤りを検出し、訂正することが出来ます。

チェックサム

データを分割し、文字などのブロック単位のデータを数値とみなして、合計を取った値を検査用の符号としてデータに付け加え、誤りを検出する方法です。

合計を取るブロックの大きさは8ビットや16ビットがあります。合計を計算する時、ブロックサイズの上限値より大きくなった場合、繰り上がりの分は無視されます。

CRC方式(Cyclic Redundancy Check:巡回冗長検査)

送信するビット列をある定数(例えば生成多項式で求められる値)で割って、余りを検査用の符号としてデータに付け加える方式です。

パリティチェックの場合、複数ビットが誤っている時に誤りを検出できない場合がありますが、CRC方式では連続したビットの誤り(=バースト誤り)を検出することが出来ます。但し、訂正はできません。

ハミング符号方式

送信するビット列の中に、誤りを訂正するための符号を付け加える方式です。誤っているビットを検出し、受信側で訂正することが出来ます。この符号、又は仕組みをECC(Error Correcting Code:誤り訂正符号)といいます。

ハミング符号方式では、4ビットの情報に3ビットの誤り検査用符号を加え、2ビットの誤り検出機能と1ビットの誤り訂正機能をもたせたものがあります。よって、ブロック内に2ビットの誤りが発生した場合、誤りの訂正はできませんが検出は可能です。

ハミング符号は伝送時に使うと冗長ビットが多くなり伝送効率が落ちます。しかし、誤り訂正が可能であり、信頼性が高いため、最近のコンピュータのメインメモリにはハミング符号方式の誤り訂正機能を搭載したものが一般化しています。(ECCメモリ)