基本的な知識を復習しつつAP対策するシリーズ。
この記事ではデータの誤りの検出と復元についてまとめます。
データの誤り?
RAMは電磁気的な干渉によってあるビットだけが反転してしまうことがあります。
またネットワーク上でデータをやり取りするときにも、ノイズが発生したりしてデータがおかしくなってしまうことがあります。
これらをデータの誤りといいます。
この記事ではこのようなデータの誤りを検出したり訂正したりする方法をまとめます。
パリティチェック
パリティチェックはシンプルな誤り検出方法です。
まずこのようなビット列があるとします。
これに一つ、余分なビットをつけます。 これをパリティビットと呼びます。
パリティビットには、ビット列の中の1の数の合計が偶数になるように値を入れます。
今回の場合は1です。
そしてこのビット列を送信します。
受信側ではビット列の中の1の数を数えます。
これが奇数であれば、いずれかのビットが誤っているということがわかります。
ただし2ビット誤りがあった場合には1の数が偶数になってしまうため検出できません。
また、どのビットが誤っているかはわからないので、誤りの検出のみで訂正はできません。
ちなみに、上記の方法は偶数パリティと呼びます。
これとは別に1の数が奇数になるようにパリティビットを設定する奇数パリティという方法もあります。
水平垂直パリティチェック
水平垂直パリティチェックは、前節のパリティチェックを応用した誤り検出方法です。
前節の方法では誤りの訂正はできませんでしたが、この方法を使うと検出だけでなく訂正まで行うことができます。
いま、次のような三つのビット列を送信することを考えます。
まずこれらそれぞれについてパリティビットをくっつけます。
これを垂直パリティビットと呼びます（ここでは偶数パリティとします）。
次にこれらのビット列のiビット目の集合を一つのビット列とみなして、
このビット列にもパリティビットをくっつけます。
これを水平パリティビットと呼びます。
ここで、ビットに一つ誤りが生じたとします。
すると下図のように水平パリティチェックと垂直パリティチェックに一回ずつ引っかかります。
こうなると、誤りが生じているビットが明らかになります。
なのでこれを反転すれば訂正したことになり、正しいデータが得られます。
このように水平垂直パリティチェックを使うと1ビットの誤りを検出し、さらに訂正まで行うことができます。
ハミング符号
ハミング符号を使うと2ビットまでの誤りを検出でき、かつ誤りが1ビットであれば訂正できます。
今、次のようなビット列を考えます。
次に、この4ビットのうちの3つを抽出した組み合わせを作ります。
この組み合わせについて、それぞれ排他的論理和を求めます。
そしてこれらの結果を元の4ビットのくっつけて送信します。
受信側では受信した7ビットのうちの前半4ビットをみて、
送信側と同様に組み合わせごとの排他的論理和を求めます。
この結果を付加された3ビットの部分と比較して、異なっていれば誤りがあるということになります。
誤りがある場合、誤っていた組み合わせの全てに含まれるビットで誤りが生じていることがわかります。
なのでこれを反転すれば訂正できることになります。
このハミング符号方式はECCメモリという誤り訂正機能のついたメモリで使われたりします。
CRC
水平垂直パリティチェックでは、1ビットの誤りのみが検出できるのに対し、
CRCを使うとバースト誤り（何ビットも連続する誤り）が検出できます。
CRCでは、送る前の値を生成多項式と呼ばれる式で割ります。
本当はビット列ですが、下図では便宜的に10進数で示しています。
生成多項式はとりあえず名前だけ覚えておけば良さそうです。
重要なのは、その式が何者であれ、割り算なので「余り」が発生するということです。
送信側はこの余りの値を付与してデータを送信します。
受信側は受け取った値を送信側と同じ生成多項式で除算します。
そして余りの値が送信側から受け取った余りの値と同一であれば、正しいと判定します。
この方法であれば仮に2ビットの誤りが生じていても検出できるため、CRCではバースト誤りが検出できるということになります。
その他の関連用語
最後にその他の関連用語をまとめておきます。
| 用語 | 説明 |
|---|---|
| チェックサム | データの合計値を付与して送信し、受信側でもデータの合計値があっていれば誤りなしとする誤り検出方法 |
| チェックディジット | データからある計算式に基づいて算出した誤り検出用の値 クレジットカードやバーコードに使われる |
| バースト誤り | 複数ビットに連続した誤りのこと |
過去問
参考
過去問はこちらのサイトのものを使わせていただいております。 www.ap-siken.com
