ネットワーク

【情報を正しく届ける技術】ビット誤り検出・訂正

2つの装置間で通信を行うとき、通信時の回線状況や機器同士のやり取りなど、様々な原因で通信データの送信誤りが起こる。

1ビット誤り検出

代表的な手法として、奇数パリティ、偶数パリティがあります。

パリティとは、ある数字の並びの合計が偶数か奇数かによって通信の誤りを検出する技術です。送りたいデータの最後にパリティビットを付加して、そのビットをもとに誤りを検出します。

奇数パリティ:1の数が奇数になるように、パリティビットを付加する
偶数パリティ:1の数が偶数になるように、パリティビットを付加する

例えば、奇数パリティの場合
送りたいデータが 11100111 だとすると、1の数が6個で偶数になっています。奇数パリティなので、1の数を奇数にするために、パリティビットを1とします。
そうすると、111001111 となります。

1ビット誤り訂正 + 1ビット誤り検出

代表的な手法として、垂直パリティと水平パリティを組み合わせる方法があります。

垂直パリティ:送りたいデータ8ビット(1バイト)だとすると、その1バイトのデータが送られるごとに最後に1ビットのパリティビットをつける
水平パリティ:

1ビット誤り訂正+2ビット誤り検出

代表的な手法として、ハミング符号があります。

データにいくつかの冗長ビットを付加することによって、1ビットの誤りを検出し、それを訂正できる仕組みです。

ハフマン符号とは違います!!

ハフマン符号:出現率によってビット数を決める情報圧縮技術

nビット誤り検出

代表的な手法として、CRC(Cyclic Redundancy Check)があります。

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

送信側:データとCRC(データを多項式で割った余り)を送る。
受信側:データを多項式で割ってでた余り(CRC)、送信側から送られてきたCRCと一致することを確認する。

CRCは、連続する誤りを検出するための誤り制御の仕組みです。CRCのエラーチェックは、改ざん防止などのセキュリティチェックには使えません。これは、データは暗号化されていないテキストであり、多項式は公開されているため、改ざんして再計算することが可能だからです。通信データの場合、ケールブルの不良や混線などによって誤りが一度にまとめて起こることがある(バースト誤り)。このバースト誤りに対しては、複数ビットの誤りを検出できるCRCを用います。家庭や社内のLANで一般的に使われているイーサネットのパケットでは、誤り検出にCRCを用いています。

さらに、知るために、、

https://ja.wikipedia.org/wiki/ハミング符号