アダマール符号

この符号はアダマール行列に基づいている。H を次数 2ⁿ のアダマール行列としたとき、符号語は H と −H の行で与えられ、−1 を 0 に置き換えて使う。これにより、長さ 2ⁿ の符号語が 2^n + 1 個得られる。アダマール行列の行は互いに直交なので、最小ハミング距離は 2^n - 1 となる。このようにして [2ⁿ, n + 1, 2^n − 1] 符号が構築される。

また、2^n − 1 個のベクトル全てが奇数個の1を含むようなパリティ検査行列を生成することでも、アダマール符号を構築できるし、再帰符号化処理でも構築可能である。

最小ハミング距離は 2^n − 1 なので、最大 t = 2^n − 2 − 1 個の誤りを訂正できる。以下にそのアルゴリズムを示す。

符号語を受信すると、まず全ての0を −1 に置き換えて、1/−1 ベクトル v に変換する。そして (v H^T) を計算する。最大絶対値のエントリと対応する行が符号語となる。正の場合は符号語は H にあり、負なら −H にある。

証明を以下に示す。誤りがない場合、(v H^T) という積は、1つのエントリだけ +/−2ⁿ となり、他は0になる。v に誤りが含まれる場合、絶対値で考えると0だったエントリの一部が大きくなり、最大だったエントリが若干小さくなる。1つの誤りでこの値は2ずつ変化する。従って、元々0だった値は最大で 0 + 2t = 2^n − 1 − 2 となる。一方最大エントリは 2ⁿ − 2t = 2ⁿ − 2^n − 1 + 2 = 2^n − 1 + 2 となる。従って、最大限誤りがあっても、正しい行の絶対値は他の行の絶対値よりも大きい。