アダマール符号

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動: 案内検索
アダマール符号 (32, 6, 16) の行列。NASAのマリナー9号リード・マラー符号 (1, 5) で使われた。

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

構築[編集]

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

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

復号[編集]

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

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

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

歴史[編集]

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

最適性[編集]

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

脚注[編集]

  1. ^ CODING THEORY I. Part of Math 4410 - Mathematics of Coding Theory
  2. ^ Combinatorics in Space The Mariner 9 Telemetry System
  3. ^ Optimal binary linear codes of dimension at most seven, David B. Jaffe, Iliya Bouyukliev.