情報の符号化と誤り訂正

情報の符号化とは、文字や数値を0と1の並びで表す規則を定めることであり、誤り訂正符号はそこに冗長なビットを加えて、伝送や記録の途中で生じたビット誤りを検出し訂正できるようにする。本単元では、ハミング符号による誤り位置の特定、パリティを用いた2次元の誤り訂正、可変長符号の平均符号長、そしてデータ圧縮に伴う時間の計算を扱う。

原理・仕組み

ハミング符号は、データビットの間に検査ビットを置き、各検査ビットがある組合せのビットと合わせて偶数パリティになるように定める符号である。情報ビットが4ビットの場合、3つの検査ビットを付加して符号を構成する。

受信側では、検査ビットごとに検査式を計算し、結果が0にならない式の組合せから誤りの位置を求める。検査式の結果を重み付きの2進数として並べると、その値が誤りのあるビットの位置を示すので、そのビットを反転すれば1ビットの誤りを訂正できる。

具体的には、検査式c0、c1、c2の結果をc0＋2×c1＋4×c2で求めると、受信語1000101では値が3となり、左から3ビット目が誤りと分かる。この位置を反転すると正しい符号語1010101が得られる。

2次元パリティは、データを正方形状に並べ、各行と各列にパリティビットを付加する方式である。行と列の検査結果の交点として誤りの位置を特定するため、1ビットの誤りを訂正できる。

判断の基準や数値

訂正できる誤りの数は方式によって異なる。2次元パリティでは、1ビットの誤りなら誤った行と列の交点を反転することで訂正できるが、2ビットの誤りは位置を一意に定められず、一般には訂正できない。 4ビットの誤りでも、長方形の四隅が反転すると各行と各列のパリティが保たれ、誤りを検出できない場合がある。

ハミング符号の判定は、受信語の3つの検査式の結果を調べることから始まる。3つの式がすべて不一致になる場合は、3つの式すべてに含まれるビットが誤りである。 一つの検査式だけが不一致のときは、その式にだけ含まれる検査ビットの側が誤りである可能性を調べる必要がある。