誤り訂正符号と圧縮符号化

誤り訂正符号は、データに冗長ビットを付加して、誤りの検出や位置の特定を可能にする符号である。圧縮符号化は、データの冗長性を減らして、記憶容量や転送時間を少なくする符号化である。両者は目的が異なるが、どちらも符号の長さと能力の間のトレードオフを理解する必要がある。

誤りの検出と訂正の原理

パリティビットは、1ビットを付加して1の個数の偶奇をそろえる方式である。1ビットの誤りを検出できるが、その位置は分からないため訂正はできない。誤りを訂正するには、誤りの位置を一意に特定できるだけの検査情報が必要になる。

ハミング符号は、冗長ビットを複数の検査式に配置し、検査結果の組合せから誤りの位置を求める方式である。検査結果を2進数として並べると誤りのあるビットの位置が得られる。受信語の例では、検査結果がc0、c1、c2の順に1、1、0となり、位置3が特定される。 同じ検査式の考え方は、 のように、どの情報ビットがどの検査式に含まれるかを表で整理して用いる。

全部の検査式に含まれるビットに誤りがあれば、すべての検査が不一致になる。ハミング符号1110011の例では、三つの検査がすべて不一致となり、三つの式すべてに含まれる先頭のビットの誤りと判定できる。 この判定の手順を理解すれば、検査結果のパターンから誤り位置を逆算できる。

行と列にパリティを付加する二次元の方式では、16ビットを4×4に並べることで、1ビットの誤りを行と列の交点として特定できる。 2ビット以上の誤りでは、誤りの位置を一意に決められないため、一般には訂正できない。また、四隅のように長方形の角の4ビットが同時に反転すると、各行と各列のパリティが保たれ、誤りを検出できない場合がある。

符号の区別と検出能力

奇数パリティ、水平パリティ、チェックサムは、主に誤りの検出に用いられる方式である。これに対し、メモリの誤り制御で2ビットの誤り検出と1ビットの誤り訂正を両立させる方式として問われるのはハミング符号である。 拡張ハミング符号は、ハミング符号に全体のパリティを加えたものであり、2ビットの誤りを検出する機能を持たせる。