アダマール符号

アダマール符号（アダマールふごう、英: Hadamard code）は、信号の誤り検出訂正に使われる符号体系。名称はジャック・アダマールに由来する。[2"n", "n" + 1, 2"n" − 1] 符号の一種である。"n" が大きいと転送レートは低くなるが、多くの誤りを訂正可能である。
構築.
この符号はアダマール行列に基づいている。"H" を次数 2"n" のアダマール行列としたとき、符号語は "H" と −"H" の行で与えられ、−1 を 0 に置き換えて使う。これにより、長さ 2"n" の符号語が 2"n" + 1 個得られる。アダマール行列の行は互いに直交なので、最小ハミング距離は 2"n" - 1 となる。このようにして [2"n", "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"n" となり、他は0になる。"v" に誤りが含まれる場合、絶対値で考えると0だったエントリの一部が大きくなり、最大だったエントリが若干小さくなる。1つの誤りでこの値は2ずつ変化する。従って、元々0だった値は最大で 0 + 2"t" = "2""n" − 1 − 2 となる。一方最大エントリは 2"n" − 2"t" = 2"n" − 2"n" − 1 + 2 = 2"n" − 1 + 2 となる。従って、最大限誤りがあっても、正しい行の絶対値は他の行の絶対値よりも大きい。
歴史.
アダマール符号は1971年のマリナー9号のミッションで画像転送時の誤り訂正に使われた。このミッションでの符号語長は6ビットで、64階調のグレイスケールを表していた。通信機の制限により、最大データ長は30ビットとなっていた。反復符号の代わりに [32, 6, 16] のアダマール符号が使われた。ワード当たり最大7ビットの誤りを訂正可能である。5-反復符号と比べると、このアダマール符号の誤り訂正能力は優れており、転送レートは同じである。この符号を採用した理由の1つとして、復号アルゴリズムが効率的だという点もある。これに使われた回路を "Green Machine" と呼んだ。この回路では高速フーリエ変換を使って復号速度を3倍に強化していた。
最適性.
n <= 6 のアダマール符号は最適であることが証明されている。