アダマール符号

アダマール符号（アダマールふごう、英: Hadamard code）は、信号の誤り検出訂正に使われる符号体系。名称はジャック・アダマールに由来する。[2ⁿ, n + 1, 2^n − 1] 符号の一種である。n が大きいと転送レートは低くなるが、多くの誤りを訂正可能である。

アダマール符号 (32, 6, 16) の行列。NASAのマリナー9号のリード・マラー符号 (1, 5) で使われた。

構築

この符号はアダマール行列に基づいている。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 となる。従って、最大限誤りがあっても、正しい行の絶対値は他の行の絶対値よりも大きい。

歴史

アダマール符号は1971年のマリナー9号のミッションで画像転送時の誤り訂正に使われた。このミッションでの符号語長は6ビットで、64階調のグレイスケールを表していた。通信機の制限により、最大データ長は30ビットとなっていた。反復符号の代わりに [32, 6, 16] のアダマール符号が使われた。ワード当たり最大7ビットの誤りを訂正可能である。5-反復符号と比べると、このアダマール符号の誤り訂正能力は優れており、転送レートは同じである。この符号を採用した理由の1つとして、復号アルゴリズムが効率的だという点もある。これに使われた回路を "Green Machine" と呼んだ。この回路では高速フーリエ変換を使って復号速度を3倍に強化していた。

最適性

n <= 6 のアダマール符号は最適であることが証明されている。