データ表現と符号化・誤り訂正

情報を0と1の並びで表すとき、数の表し方、文字の符号化、誤りを見つけたり直したりする符号が基本となる。試験では、計算で答えを求める問いと、方式の性質を問う問いが混ざって出題される。ここでは、それぞれの考え方を仕組みから整理する。

整数の表現と演算の範囲

符号付き整数は2の補数で表すのが一般的であり、16ビットならば−32,768から32,767までの値を扱える。加算の結果がこの範囲を超えるとオーバフローが起きる。典型的には、正の数同士の和が負になるように、符号が逆転したときにオーバフローが生じる。符号が異なる二数の和は、結果が両者の間に収まるため、どの組合せでもこの範囲を超えない。

逆に、絶対値の和が範囲内に収まっていても、同符号の組合せでは最大値を超えうる。例えば16,384どうしの和は32,768となり、最大値の32,767を一つ上回る。範囲を保証できるかどうかを判定するときは、同符号で最大値に近い値を入れてみる手順が役に立つ。絶対値の大きさだけで判断すると、符号の影響を見落とす。

誤り検出と訂正の方式

パリティは、データの1の個数が偶数か奇数かを一ビットで示す方式である。偶数パリティでは、データ中の1の個数が奇数のときに付加ビットを1とするので、3ビットのデータに付けるパリティビットは3入力のXORに等しい。XORは入力中の1の個数が奇数のとき1を出力するためである。

Hamming符号は、データに冗長ビットを加えて検査式を立て、その結果から誤りの位置を特定して1ビットを訂正する。与えられた符号語で三つの検査式が全て不一致になれば、すべての式に含まれる位置の1ビットが誤っていると判定できる。その位置を反転すれば、正しい符号語が得られる。検査式の組み立て方を一度手で追っておくと、位置の判定が確実になる。

Hamming符号に全体パリティを一つ加えた拡張ハミング符号では、1ビット誤りを訂正しつつ2ビット誤りを検出できる。メモリの誤り制御では、この性質を持つ方式が用いられる。奇数パリティや水平パリティ、チェックサムは誤りを検出する方式であり、位置を特定して訂正する機能は一般に持たない。

同じ組合せは、別の年度の試験でも問われている。拡張ハミング符号が二つの機能を両立させるという性質は、用語の区別とともに覚えておくとよい。

二次元のパリティでは、データを行と列に並べて、それぞれにパリティを付ける。1ビットの誤りはそのビットを含む行と列の不一致で位置が決まるため、訂正できる。2ビット以上の誤りでは、不一致の行や列が重なって位置を一意に決められない場合がある。配置図の網掛け部分がパリティビットであることを見落とすと、データ量の計算も誤る。