誤り検出と誤り訂正の符号

誤り検出・誤り訂正の符号は、データに冗長ビット（検査ビット）を付加し、伝送や記憶の過程で生じたビット誤りを見つけたり直したりする仕組みである。冗長ビットを増やすほど検出・訂正できる誤りは増えるが、その分だけ伝送量や記憶領域の負担も増える。本単元では、誤り検出の原理、2次元パリティによる訂正、ハミング符号の検査式、そして方式ごとの能力の違いを整理する。

誤り検出の原理

奇数パリティや水平パリティは、ビット列の1の個数の偶奇や、行ごとの検査によって誤りを検出する方式である。これらは誤りがあることを知らせることができるが、どのビットが誤っているかを特定できないため、単独では訂正に使えない。

チェックサムも、データから計算した値を照合して誤りを検出する方式である。通常は検出を目的とし、誤りの訂正までは行わない。

2次元パリティによる誤り訂正

16ビットのデータを4×4の正方形状に並べ、行と列の両方にパリティビットを付加する方式を2次元パリティという。1ビットだけが誤った場合は、パリティ検査で誤りのある行と列が特定されるため、その交点のビットを反転すれば訂正できる。

一方、2ビット以上の誤りには同じ方式で対応しきれない。同じ行や列に誤りが並ぶ場合などには誤りの位置を一意に決められず、訂正は保証されない。

さらに、誤りの組合せによっては各行と列のパリティがすべて保たれ、誤りそのものを検出できない場合もある。

ハミング符号の検査式と誤り位置の特定

ハミング符号は、冗長ビットを複数の検査式の組合せに割り当てることで、1ビットの誤りを訂正できるように構成された符号である。符号長7ビット、情報ビット4ビットの例では、3つの検査結果を重みを付けて合わせた値がそのまま誤りの位置を示す。その位置のビットを反転すれば、誤りが訂正される。