初めに
前回の続きです。
データの誤り制御
コンピュータは0か1しか理解できず、その組み合わせによって
音楽を表現したり、テキストを表現したりしています。
そして、コンピュータ同士がデータをやり取りする際も、この0か1で送信・受信しています。
ですが「0なら0」「1なら1」というはっきりとしたデータではなく
あくまでも単なる電気信号のみで、この信号の波形を確認し、0か1かを判断しています。
しかし、電気信号なので伝送距離が伸びれば信号は減衰しますし
別の電気的な干渉を受ければ波形は乱れてしまいます。
こうして生まれるのがデータの誤りです。
パリティチェック
送信するビット列に対して、パリティビットと呼ばれる検査用のビットを付与することでデータの誤りを検出していきます。
これをパリティチェックと呼びます。
付与する方法には2種類あります。
・偶数パリティ
以下のようなビット列があったとして
1001000
偶数パリティでは、ビット列の1の数が偶数になるようにしていきます。
0 1001000
なのでこの場合は0を付与しています。
・奇数パリティ
対して、奇数パリティはビット列の1の数が奇数になるようにしていきます。
1 1001000
なのでこの場合は1を付与します。
ですが、パリティチェックでは「1ビットの誤り」を検出する事だけです。
なのでビット列の1が奇数個であれば
データの誤りを検出できますが
0 1001000
↓
// 検出可能
0 100100①
偶数個であれば検出できません。
0 1001000
↓
// 検出不可
0 100000①
これではどのビットが間違っているかも分からないので誤り訂正も行えません。
・水平垂直パリティチェック
どの方向にパリティビットを付与するかによって誤りを検出する方法です。
例えば、ABCという文字列があったとして
これを文字コードで表現したら以下のようになります。
A B C
↓ ↓ ↓
1 0 0
0 1 0
0 0 1
0 0 0
0 0 0
0 0 0
1 1 1
このビット列の水平・垂直方向にパリティビットを付与していきます。
今回は偶数パリティを用いていきます。
A B C
↓ ↓ ↓
1 0 0 1 // 水平パリティ
0 1 0 1
0 0 1 1
0 0 0 0
0 0 0 0
0 0 0 0
1 1 1 1
0 0 0 0 // 垂直パリティ
ビット列を並べた時の各ビット位置単位で付与するのが水平パリティで
ビット列単位で付与するのが垂直パリティです。
この2つのパリティを組み合わせて使うのが水平垂直パリティです。
縦横両面から誤りを検出できるので、1ビットの誤りであれば
間違っている位置を特定することができ、訂正することができます。
例えば以下のように◯の部分が誤りだったら
縦横から誤りを検出することができるので位置を特定できます。
A B C
↓ ↓ ↓
1 0 0 1
0 1 0 1
0 ① 1 1
0 0 0 0
0 0 0 0
0 0 0 0
1 1 1 1
0 0 0 0
ただし、2ビット以上の誤りが発生すると検出はできますが位置の特定が出来なくなります。
A B C
↓ ↓ ↓
1 0 0 1
0 1 0 1
① ① 1 1
0 0 0 0
0 0 0 0
0 0 0 0
1 1 1 1
0 0 0 0
CRC(巡回冗長検査)
ビット列を特定の式(生成多項式)で割り
その余りをチェック用のデータとして付与する方法です。
// この計算で得られた余りがチェック用のデータとなる
送信するデータ(ビット列) ÷ 生成多項式
これをCRC(Cyclic Redundancy Check)と呼びます。
まず、データを送信する側は計算で得られた余りを
元々のビット列にくっつけて、それをまとめて送信データとします。
こうすることで、そのデータは計算に用いた生成多項式で
割り切れるはずの値に変わります。
// まとめて送信データとする
送信するデータ + 余り
そして受信した側は、送信側と同じ生成多項式を使って計算していきます。
受信したデータ ÷ 生成多項式
データに問題がなければ割り切ることができ、余りが出ません。
余りがあればそのデータに問題があることが分かります。
この方法ではデータの誤り訂正は出来ませんが、連続したビットの誤り(バースト誤り)など
複数ビットの誤りを検出することが可能です。
おわりに
今回はここまでです。
間違っている部分や気になるところがあればコメントして下さい。