アダマール符号

アダマール符号について

アダマール符号（Hadamard code）は、信号の誤り検出と訂正に利用される符号体系です。この符号の名称は数学者ジャック・アダマールに由来しています。アダマール符号は特に、[2n, n + 1, 2n − 1] 符号の一種として知られており、nが大きいほど転送レートは低下しますが、誤り訂正能力は高まります。

構築方法

アダマール符号はアダマール行列に基づいています。この行列Hを次数2nのアダマール行列とした場合、符号語はHと−Hの行から生成されます。符号語を定義する際には、−1を0に置き換え使用することで、長さ2nの符号語が2n + 1個得られます。アダマール行列の行は互いに直交しており、そのため最小ハミング距離は2n - 1に設定されています。この手法により、[2n, n + 1, 2n − 1]の形式を持つ符号が生成されるのです。

それに加えて、2n - 1個のベクトルがすべて奇数の1を含むパリティ検査行列を作成することでも、アダマール符号の構築が可能です。また、再帰的な符号化処理を利用することでも、この符号を生成できます。

復号のプロセス

アダマール符号の最小ハミング距離は2n - 1であるため、最大t = 2n - 2 - 1個の誤りを訂正することができます。復号は次の手順で行われます。最初に、受信した符号語内のすべての0を−1に置き換え、1または−1のベクトルvに変換します。次に、vとその転置行列HTとの積(v HT)を計算します。この際、最大の絶対値を持つエントリが符号語となります。もし結果が正であれば、これはHにあり、負であれば−Hに位置します。

このアルゴリズムの証明では、誤りがない場合に(v HT)の結果は一つのエントリだけが+/−2nとなり、その他は0になります。誤りが含まれている場合、その影響で本来0だったエントリが大きくなり、最大エントリが若干小さくなるのです。特定の誤りによる変化は、元の値に対し2ずつ変わります。そのため、最大限の誤りが生じても、正しい行の値は他の行の値に比べて相対的に大きくなるという性質があります。

歴史的背景

アダマール符号は、1971年に行われたマリナー9号のミッションで画像データの転送中に誤り訂正が求められた際に利用されました。このミッションでは、符号の語長が6ビットで、64階調のグレースケールを表現していました。通信機の制限から、最大データ長は30ビットに設定されていましたが、その際に反復符号の代替として[32, 6, 16]のアダマール符号が採用されました。この符号は、ワードあたり最大7ビットの誤りを訂正できる特性を有しています。

アダマール符号の誤り訂正能力は、5-反復符号と比較しても著しく優れており、データ転送レートは同じままで維持されます。また、この符号が選ばれた理由の一つは、その復号アルゴリズムの効率性です。このプロジェクトにおいて使用された回路は「Green Machine」と呼ばれ、高速フーリエ変換を活用することで復号速度が3倍にも強化されました。

最適性

特筆すべき点は、n <= 6 のアダマール符号が最適であることが証明されていることです。この特性により、アダマール符号は誤り訂正の領域で重要な役割を果たしています。

もう一度検索