トップ > スキル : IT系ラーニング > 基礎理論 > 応用数学

IT系ラーニング_基礎理論

誤り制御方式

誤り制御とは、データ伝送時に発生するデータの誤りを検出することで、以下のような方式があります。

  • パリティチェック方式
  • CRC方式
  • ハミング符号方式

パリティチェック方式

パリティチェック方式は、データにパリティビットと呼ばれる1ビットの検査用ビットを付加して、ビット列から1ビットの誤りを検出する方式です。
パリティビットを付加する際に、「1」のビット数の合計を偶数にする方式を偶数パリティ、「1」のビット数の合計を奇数にする方式を奇数パリティといいます。

パリティチェック方式

例えば、送信者は「1001101」を偶数パリティでデータを送信したとします。すると「10011010」が伝送路を移動します。このとき、データ伝送の際にノイズなどで1ビット反転してしまい、結果として受信者に「11011010」が到達します。あらかじめ偶数パリティを使っていると送信者と受信者で決めていたので、受信者は受信データ「11011010」を調べます。すると、「1」のビット数が5個あり、偶数ではないので、おかしいと検知できるのです。つまり途中で何らかのビット反転(あるいはビット欠損)があったと判断できるので、送信者にもう一度同じものを送信してくれるように要求するわけです。

CRC方式

CRCは、ビット列のデータをある生成多項式で割った余りを検査用のCRC符号として、データに付加して送信する方式です。受信側は、受信したデータが同じ生成多項式で割り切れるか否かで誤りの発生を検出します。

CRC方式

例)1101のようなビット列Dは、多項式D(x)=X3+X2+1のように表すことができます。
CRCによる誤り検出は、送信側でメッセージをひとつの多項式で表現し、これをCRCの生成多項式G(X)で割り算し、その剰余を情報ビットに続けて伝送路に送り出します。よって、情報ビットと付加された検査ビットを多項式で表現したものはG(X)で割り切れるのです。

例)1101を101で割ったとき、商が11、余りが10になります。1101の後に10を付加した結果の110111は101で割ると、商が1110、余りが0になります。
そこで、受信側では受信データをG(x)で割り算し、剰余が0であれば誤りがなしとし、剰余が0でなければ誤りがあったと判定します。

ハミング符号方式

ハミング符号方式は、誤りをただ検出するだけでなく、誤っているビットを受信側で判断して訂正する方式です。誤りがあったデータを再送する必要がないため、CRC方式のように再送要求をしなくてもよいのです。

データのビット列の一部に冗長ビットを付加して、データと付加ビットとの演算規則を設定してメモリ誤りの検出をします。
誤りを検出したら、正しいデータに訂正することができます。
情報ビットのほかに数ビットのチェック用のビットを付加することで、所定の計算を行い、ビット誤りを起こした位置を検出し自動訂正します。ただし、2ビットの誤りは検出できますが、訂正することはできません。
ハミングコードは、1ビットの誤りを自動訂正できます。2ビットの誤りは検出だけです。

【誤り制御方式】