ハミング符号
(7,3)ハミング符号の場合に符号語に2ビットの誤りが含まれている場合を考えてみる。この時位置 i と jに誤りが含まれているとすると
Y = x ⋅ G ⊕ e i ⊕ e j {\displaystyle Y=x\cdot G\oplus e_{i}\oplus e_{j}}
となり、検査行列との積を取ると
Y ⋅ H T = e i ⋅ H T ⊕ e j ⋅ H T {\displaystyle Y\cdot H^{T}=e_{i}\cdot H^{T}\oplus e_{j}\cdot H^{T}}
となる。この時 ei ≠ ej であるため、上記の式は検査行列の任意の2つの列の値排他的論理和が出力される。検査行列の定義より列の値は全て相違となるので 2ビット誤りの時も検査行列との積が零ベクトルになることはない。ただし、別の検査行列の値と一致するため誤訂正を起こすことになる。
すなわち単純なハミング符号で誤り検出のみを行うと 2ビットの誤りまで検出できる。しかし、1ビット誤り(訂正可能)か 2ビット誤り(訂正不可能)であるかを判断する術がないため、この二つの機能を同時に実装することができない。そこでハミング符号に符号語全体のパリティビットを付加することで 1ビットの誤り訂正と同時に、2ビットまでの誤りの検出を行うことが可能になる(SECDED("single error correction, double error detection"))。これを拡張ハミング符号という。
符号の生成は単純なハミング符号で生成された符号語の全ビットの排他的論理和を符号語の末尾に追加する。符号化、復号の例で使用した 1 0 1 1 1 0 0 の場合、パリティビットは 0 なので末尾に 0 を加えた 1 0 1 1 1 0 0 0 になる。復号には、以下のような検査行列を用いる。
H = [ 1 0 1 1 1 0 0 0 1 1 0 1 0 1 0 0 0 1 1 1 0 0 1 0 1 1 1 1 1 1 1 1 ] {\displaystyle H={\begin{bmatrix}1&0&1&1&1&0&0&0\\1&1&0&1&0&1&0&0\\0&1&1&1&0&0&1&0\\1&1&1&1&1&1&1&1\\\end{bmatrix}}}
この行列は、先ほどまで使用した検査行列に、新たに全て 0の列を一番右側に加え、全て 1 の行を一番下に加えたものである。
誤り訂正の方法は、通常のハミング符号と同様である。この時 1ビット誤りなら検査行列のいずれかの列と同じ値になるが、2ビット誤りの場合は検査行列の列の値に含まれない値を出力する。これにより 1ビットの誤り訂正と2ビットの誤りの検出が同時に行える。