データの表現と誤り訂正

データの表現とは、文字・数値・画像などの情報をビット列としてどの形式で持つかを定めることである。誤り訂正は、記録や通信の途中で生じたビットの誤りを、冗長ビットを使って検出し、正しい値へ戻す仕組みである。試験では、表現方式の特徴を計算で確かめる問題と、誤り制御の方式を見分ける問題が中心に問われる。

誤り制御の原理とパリティ検査

誤り制御では、もとのデータに検査用の冗長ビットを付け加え、受信側で検査式を計算して誤りの有無を判定する。偶数パリティや奇数パリティは、1ビットを付加してビットの1の個数の偶奇を揃える方式であり、偶奇の不一致から誤りを検出する。ただし、どのビットが誤ったかを示す情報がないため、この方式だけでは誤りを訂正できない。

検査ビットを複数の式で持たせると、不一致となった式の組合せから誤りの位置を絞り込める。行と列の両方に偶奇検査のビットを置く方式では、データを行と列に並べ、不一致となった行と列の交点を反転させることで訂正する。16ビットのデータを4×4に配置した場合、1ビットの誤りであれば位置を特定して訂正できる。

ハミング符号による1ビット誤りの訂正

ハミング符号は、四ビットの情報に三ビットの検査ビットを加えた七ビットの符号語で構成される代表的な方式である。 各検査式は、符号語の決められた位置のビットを2を法として加えた値として定義される。検査結果c0、c1、c2の値から、i＝c0＋2×c1＋4×c2を求め、左からi番目のビットを反転させると誤りが訂正される。例えば、c0が1、c1が1、c2が0であればiは3となり、左から三ビット目を反転させる。受信語が1000101の場合、この手順で三ビット目が誤りと判定され、訂正後の符号語は1010101となる。 検査式がすべて成立すれば、誤りはないと判断する。

ハミング符号の検査式で三つすべてが不一致となる場合は、三つの式すべてに含まれるビットが誤りと判定される。 同じ形式の問題は繰り返し出題されており、検査式とビットの対応を表にして整理しておくと判断を誤りにくい。

整数表現とオーバフローの判断

符号付き整数は二の補数で表されるため、十六ビットの場合に表せる値の範囲は有限である。加算結果がこの範囲を外れる現象をオーバフローと呼び、判断の基準は、加える二つの数の符号が同じかどうかにある。符号が異なる数どうしの和は、二つの入力値の間に収まるので、範囲を超えることはない。 同じ符号の数を加える場合には、和の絶対値が表現範囲の上限や下限を超えることがある。