誤り訂正符号の仕組み

誤り訂正符号とは、データに冗長な検査ビットを付加し、伝送や記憶の途中で生じたビットの誤りを検出し、一定の範囲では訂正できるようにした符号である。代表例としてパリティ検査とハミング符号があり、検査ビットの配置と検査式の組み方によって、検出や訂正ができる誤りの数が決まる。試験では、検査式の計算から誤り位置を求める手順と、誤り検出と誤り訂正の違いが中心に問われる。

原理と仕組み

ハミング符号では、データビットの間に検査用ビットを挿入し、各検査ビットが特定のデータビットの組合せの偶奇を担当するように配置する。受信側は各検査式を再計算し、結果が0にならない式の組合せから誤り位置を特定する。例えば、符号長7ビットで情報ビット4ビットの符号では、3つの検査結果に1、2、4の重みを付けて足し合わせると、誤り位置の番号が得られる。 検査式がどのビットを含むかという組合せが、位置特定の本質である。

二次元パリティでは、データを行と列に並べ、各行と各列に偶奇検査ビットを付加する。1ビットの誤りがあれば、その誤りのビットが属する行と列の両方で不一致が現れ、その交点として位置が決まる。

判断の基準と数値

検出と訂正の能力は、符号語どうしの距離で整理すると理解しやすい。符号語の間で異なるビット数の最小値をdとすると、d−1ビットまでの誤りは検出でき、(d−1)を2で割った整数部分までの誤りを訂正できる。この関係から、1ビットの誤りを訂正し、さらに2ビットの誤りを検出するためには、通常のハミング符号に検査ビットを追加した拡張ハミング符号を用いる必要がある。

ハミング符号では、情報ビットがm、検査ビットがkのとき、2のk乗がm＋k＋1以上となる最小のkを用いる。情報ビットが4ビットの場合は検査ビットが3ビットとなり、符号長は7ビットとなる。この数値は、問題文で与えられた符号長から検査ビットの数を判断する際の基準になる。