アダマールコード

アダマールコード
名前の由来	ジャック・アダマール
分類
タイプ	線形 ブロックコード
ブロック長	${\displaystyle n=2^{k}}$
メッセージの長さ	${\displaystyle k}$
レート	${\displaystyle k/2^{k}}$
距離	${\displaystyle d=2^{k-1}}$
アルファベットのサイズ	${\displaystyle 2}$
表記	${\displaystyle [2^{k},k,2^{k-1}]_{2}}$-コード
ヴ t e

拡張アダマール符号
名前の由来	ジャック・アダマール
分類
タイプ	線形 ブロックコード
ブロック長	${\displaystyle n=2^{k}}$
メッセージの長さ	${\displaystyle k+1}$
レート	${\displaystyle (k+1)/2^{k}}$
距離	${\displaystyle d=2^{k-1}}$
アルファベットのサイズ	${\displaystyle 2}$
表記	${\displaystyle [2^{k},k+1,2^{k-1}]_{2}}$-コード
ヴ t e

アダマール符号は、フランスの数学者ジャック・アダマールにちなんで名付けられた誤り訂正符号であり、非常にノイズが多い、または信頼性の低いチャネルを介してメッセージを送信するときにエラー検出と訂正のために使用されます。 1971年に、このコードはNASAの宇宙探査機マリナー9号から地球に火星の写真を送信するために使用されました。^[1]アダマール符号は、そのユニークな数学的特性のため、エンジニアによって使用されるだけでなく、符号理論、数学、理論計算機科学の分野でも熱心に研究されています。 アダマール符号は、アメリカの数学者ジョセフ・レナード・ウォルシュにちなんで、ウォルシュ符号、ウォルシュファミリー、^[2]、ウォルシュ-アダマール符号^[3]という名前でも知られています。

アダマール符号は、 2進アルファベットの長さの線形符号の例です。残念ながら、この用語はやや曖昧で、参考文献によってはメッセージ長を と想定しているものもあれば、メッセージ長を と想定しているものもあります。この記事では、前者をアダマール符号、後者を拡張アダマール符号と呼んでいます。 ${\displaystyle 2^{m}}$${\displaystyle k=m}$${\displaystyle k=m+1}$

アダマール符号は、ゼロでない各符号語のハミング重みがちょうど である点で独特であり、これは符号の距離も であることを意味します。ブロック符号の標準的な符号化理論表記では、アダマール符号は-符号、つまりバイナリアルファベット上の線形符号であり、ブロック長、メッセージ長（または次元）、最小距離 を持ちます。ブロック長はメッセージ長に比べて非常に大きいですが、その一方で、非常にノイズの多い状況でもエラーを訂正できます。 ${\displaystyle 2^{k-1}}$${\displaystyle 2^{k-1}}$${\displaystyle [2^{k},k,2^{k-1}]_{2}}$ ${\displaystyle 2^{k}}$${\displaystyle k}$ ${\displaystyle 2^{k}/2}$

拡張アダマール符号は、アダマール符号をわずかに改良したバージョンです。これは -符号であるため、相対距離を維持しながらわずかに優れたレートを持ち、そのため実際のアプリケーションで好まれています。通信理論では、これは単にアダマール符号と呼ばれ、バイナリアルファベット上の1次リード・ミュラー符号と同じです。^[4]${\displaystyle [2^{k},k+1,2^{k-1}]_{2}}$${\displaystyle 1/2}$

通常、アダマール符号はシルベスターのアダマール行列 の構築に基づいていますが、「アダマール符号」という用語は、必ずしもシルベスター型ではない任意のアダマール行列から構築された符号を指す場合にも使用されます。一般に、このような符号は線形ではありません。このような符号は、1959 年にRaj Chandra BoseとSharadchandra Shankar Shrikhandeによって初めて構築されました。 ^[5] nがアダマール行列のサイズである 場合、符号にはパラメーター があり、これは、ブロック長nで最小距離n /2 の 2 n個のコードワードを持つ、必ずしも線形ではないバイナリ符号であることを意味します。以下で説明する構築と復号化方式は一般的なnに適用されますが、線形性の特性とリード・ミュラー符号との同一視により、n は2 の累乗であり、アダマール行列はシルベスター法で構築された行列と同等である必要があります。 ${\displaystyle (n,2n,n/2)_{2}}$

アダマール符号は、ローカルにデコード可能な符号であり、受信したワードのごく一部だけを見て、元のメッセージの一部を高い確率で復元する方法を提供します。これにより、計算複雑性理論、特に確率的に検証可能な証明の設計に応用されます。アダマール符号の相対距離は 1/2 なので、通常は最大で 1/4 のエラーの割合からしか復元できません。ただし、リスト デコードを使用すると、受信したワードのビットの 未満が破損している限り、可能性のある候補メッセージの短いリストを計算することができます。 ${\displaystyle {\frac {1}{2}}-\epsilon }$

符号分割多重接続（CDMA）通信では、アダマール符号はウォルシュ符号と呼ばれ、個々の通信チャネルを定義するために使用されます。CDMAの文献では、コードワードを「コード」と呼ぶのが一般的です。各ユーザーは、異なるコードワード、つまり「コード」を使用して信号を変調します。ウォルシュ符号ワードは数学的に直交しているため、ウォルシュ符号化された信号は、端末が着信信号を符号化するために使用されたものと同じコードワードを使用しない限り、CDMA対応のモバイル端末にはランダムノイズとして表示されます。^[6]

文献では、このコードに対して最も一般的に使用されている名前は アダマール コードです。ただし、現代の使用では、これらのエラー訂正コードはウォルシュ アダマール コードと呼ばれています。

これには理由があります:

ジャック・アダマールは自分でコードを発明したわけではないが、1940年代に 最初の誤り訂正コードであるハミングコードが開発されるよりずっと前の1893年頃にアダマール行列を定義した。

アダマール コードはアダマール行列に基づいており、ここで使用できるさまざまなアダマール行列がありますが、通常、アダマール コードのコードワードを取得するには、 シルベスターのアダマール行列の構築のみが使用されます。

ジェームズ・ジョセフ・シルベスターは1867年にアダマール行列の構築法を考案したが、これは実際にはアダマールのアダマール行列に関する研究よりも古い。そのため、アダマール符号という名称は議論の的となっており、この符号はアメリカの数学者ジョセフ・レナード・ウォルシュに敬意を表してウォルシュ符号と呼ばれることもある。

1971 年のマリナー 9 号ミッションでは、画像伝送エラーを修正するために拡張アダマール コードが使用されました。このミッションで使用されたバイナリ値は 6 ビット長で、64 のグレースケール値を表します。

当時の送信機の調整品質の制限（ドップラー追跡ループの問題による）により、最大有効データ長は約 30 ビットでした。繰り返しコードの代わりに、[32、6、16] アダマール コードが使用されました。

この方式を使用すると、32 ビット ワードあたり最大 7 ビットのエラーを訂正できます。5 回の繰り返しコードと比較すると、このアダマール コードのエラー訂正特性ははるかに優れていますが、その速度は同等です。効率的なデコード アルゴリズムは、このコードを使用する決定の重要な要素でした。

使用された回路は「グリーン マシン」と呼ばれていました。高速フーリエ変換を採用しており、デコード速度を 3 倍に高めることができます。1990 年代以降、宇宙プログラムによるこのコードの使用はほぼ停止しており、NASA 深宇宙ネットワークは26 m を超えるアンテナに対してこのエラー訂正方式をサポートしていません。

すべてのアダマール符号はアダマール行列に基づいていますが、その構成は科学分野、著者、および用途によって微妙に異なります。データ転送に符号を使用するエンジニアや、符号の極限特性を分析する符号理論家は、通常、たとえ構成が数学的に多少洗練されなくなるとしても、符号のレートが可能な限り高くなることを望んでいます。

一方、理論計算機科学におけるアダマール符号の多くの応用では、最適なレートを達成することはそれほど重要ではないため、より簡潔なアダマール符号の構成の方が、よりエレガントに分析できるため好まれます。

長さ のバイナリ メッセージが与えられると、アダマール コードはエンコード関数 を使用してメッセージをコードワードにエンコードします。この関数は、次のように定義される 2 つのベクトルの内積 を利用します。${\displaystyle x\in \{0,1\}^{k}}$${\displaystyle k}$${\displaystyle {\text{Had}}(x)}$${\displaystyle {\text{Had}}:\{0,1\}^{k}\to \{0,1\}^{2^{k}}.}$ ${\displaystyle \langle x,y\rangle }$${\displaystyle x,y\in \{0,1\}^{k}}$

${\displaystyle \langle x,y\rangle =\sum _{i=1}^{k}x_{i}y_{i}\ {\bmod {\ }}2\,.}$

のアダマール符号化は、のすべての内積のシーケンスとして定義されます。 ${\displaystyle x}$${\displaystyle x}$

${\displaystyle {\text{Had}}(x)={\Big (}\langle x,y\rangle {\Big )}_{y\in \{0,1\}^{k}}}$

上で述べたように、アダマール符号自体はいくぶん無駄が多いため、実際には拡張アダマール符号が使用されます。これは、 の最初のビットがゼロの場合、内積には に関する情報がまったく含まれず、したがって、コードワードのこれらの位置のみから完全に復号化することは不可能だからです。一方、コードワードが の位置に制約されている場合でも、 を完全に復号化することは可能です。したがって、アダマール符号をこれらの位置に制約することは理にかなっており、 の拡張アダマール符号化、つまりが生成されます。 ${\displaystyle y}$${\displaystyle y_{1}=0}$${\displaystyle x_{1}}$${\displaystyle x}$${\displaystyle y_{1}=1}$${\displaystyle x}$${\displaystyle x}$${\displaystyle {\text{pHad}}(x)={\Big (}\langle x,y\rangle {\Big )}_{y\in \{1\}\times \{0,1\}^{k-1}}}$

アダマール符号は線形符号であり、すべての線形符号は生成行列 によって生成できます。これは、すべての に対して が成り立つような行列です。ここで、メッセージは行ベクトルとみなされ、ベクトル行列積は有限体上のベクトル空間で理解されます。特に、アダマール符号の内積定義を記述する同等の方法は、すべての列が長さ の文字列で構成される生成行列 を使用することです。つまり、 ${\displaystyle G}$${\displaystyle {\text{Had}}(x)=x\cdot G}$${\displaystyle x\in \{0,1\}^{k}}$${\displaystyle x}$ ${\displaystyle \mathbb {F} _{2}}$${\displaystyle y}$${\displaystyle k}$

${\displaystyle G={\begin{pmatrix}\uparrow &\uparrow &&\uparrow \\y_{1}&y_{2}&\dots &y_{2^{k}}\\\downarrow &\downarrow &&\downarrow \end{pmatrix}}\,.}$

ここで、 は辞書式順序で 番目のバイナリベクトルです。たとえば、 次元のアダマール符号の生成行列は次のようになります。 ${\displaystyle y_{i}\in \{0,1\}^{k}}$${\displaystyle i}$${\displaystyle k=3}$

${\displaystyle G={\begin{bmatrix}0&0&0&0&1&1&1&1\\0&0&1&1&0&0&1&1\\0&1&0&1&0&1&0&1\end{bmatrix}}.}$

行列は-行列であり、線形演算子を生成します。 ${\displaystyle G}$${\displaystyle (k\times 2^{k})}$ ${\displaystyle {\text{Had}}:\{0,1\}^{k}\to \{0,1\}^{2^{k}}}$

拡張アダマール符号の生成行列は、最初のエントリが 1 である列に行列を制限することによって得られます。たとえば、次元の拡張アダマール符号の生成行列は次のようになります。 ${\displaystyle G}$${\displaystyle k=3}$

${\displaystyle G'={\begin{bmatrix}1&1&1&1\\0&0&1&1\\0&1&0&1\end{bmatrix}}.}$

すると、 はとの線形マッピングになります。 ${\displaystyle {\text{pHad}}:\{0,1\}^{k}\to \{0,1\}^{2^{k-1}}}$${\displaystyle {\text{pHad}}(x)=x\cdot G'}$

一般に、拡大アダマール符号の生成行列は、長さおよび次元の拡張ハミング符号のパリティ チェック行列であり、これにより拡大アダマール符号は拡張ハミング符号のデュアル符号になります。したがって、アダマール符号を定義する別の方法は、そのパリティ チェック行列を使用することです。つまり、アダマール符号のパリティ チェック行列は、ハミング符号の生成行列に等しくなります。 ${\displaystyle k}$${\displaystyle 2^{k-1}}$${\displaystyle 2^{k-1}-k}$

アダマール符号は、 n行n列の アダマール行列 Hから得られます。特に、符号の2 n 個の符号語は、 Hの行と − Hの行です。アルファベット {0,1} 上の符号を得るために、マッピング −1 ↦ 1, 1 ↦ 0、または同等のx  ↦ (1 −  x )/2 が行列要素に適用されます。符号の最小距離がn /2 であることは、アダマール行列の定義特性、つまり行が相互に直交していることから生じます。これは、アダマール行列の 2 つの異なる行が正確にn /2 の位置で異なることを意味し、行の否定は直交性に影響を与えないため、Hの任意の行は − Hの任意の行とn /2 の位置でも異なります。ただし、行が対応する場合はn の位置で異なります。

上記の拡張アダマール符号を で得るには、選択されたアダマール行列H がシルベスター型である必要があり、これによりメッセージ長が になります。 ${\displaystyle n=2^{k-1}}$${\displaystyle \log _{2}(2n)=k}$

コードの距離は、任意の 2 つの異なるコードワード間の最小ハミング距離、つまり 2 つの異なるコードワードが異なる位置の最小数です。ウォルシュ・アダマール コードは線形コードであるため、距離はすべての非ゼロ コードワード間の最小ハミング重みに等しくなります。ウォルシュ・アダマール コードのすべての非ゼロ コードワードのハミング重みは、次の議論により 正確に になります。${\displaystyle 2^{k-1}}$

をゼロ以外のメッセージとします。次の値は、コードワード内の 1 に等しい位置の割合と正確に等しくなります。 ${\displaystyle x\in \{0,1\}^{k}}$

${\displaystyle \Pr _{y\in \{0,1\}^{k}}{\big [}({\text{Had}}(x))_{y}=1{\big ]}=\Pr _{y\in \{0,1\}^{k}}{\big [}\langle x,y\rangle =1{\big ]}\,.}$

後者の値がちょうど であるという事実は、ランダム サブサム原理と呼ばれます。これが正しいことを確認するには、一般性を失うことなく と仮定します。次に、 の値を条件とすると、イベントは、 およびに依存するいくつかの に対してと同等になります。 が発生する確率はちょうど です。したがって、実際には、アダマール コードの非ゼロのコードワードはすべて相対ハミング重み を持ち、したがってその相対距離は です。 ${\displaystyle 1/2}$${\displaystyle x_{1}=1}$${\displaystyle y_{2},\dots ,y_{k}}$${\displaystyle y_{1}\cdot x_{1}=b}$${\displaystyle b\in \{0,1\}}$${\displaystyle x_{2},\dots ,x_{k}}$${\displaystyle y_{2},\dots ,y_{k}}$${\displaystyle y_{1}=b}$${\displaystyle 1/2}$${\displaystyle 1/2}$${\displaystyle 1/2}$

拡大アダマール符号の相対距離も同様ですが、すべてのs ベクトルは拡大アダマール符号の符号語であるため、すべての非ゼロ符号語がちょうど の重みを持つという特性はもはやありません。これは、ベクトルがにエンコードされるためです。さらに、が非ゼロでベクトル でない場合は、ランダム和原理が再び適用され、 の相対重みはちょうど になります。 ${\displaystyle 1/2}$${\displaystyle 1/2}$${\displaystyle 1}$${\displaystyle 1^{2^{k-1}}}$${\displaystyle x=10^{k-1}}$${\displaystyle {\text{pHad}}(10^{k-1})=1^{2^{k-1}}}$${\displaystyle x}$${\displaystyle 10^{k-1}}$${\displaystyle {\text{Had}}(x)}$${\displaystyle 1/2}$

ローカルにデコード可能なコードとは、受信した単語のごく一部を見るだけで、元のメッセージの 1 ビットを高い確率で復元できるコードです。

受信したワードのビットをチェックすることでメッセージ ビットを復元できる場合、コードは-クエリ ローカルデコード可能となります。より正式には、確率的デコーダ が存在し、(注: はベクトル と の間のハミング距離を表します)となる場合、コード は-ローカル デコード可能となります。${\displaystyle q}$${\displaystyle x_{i}}$${\displaystyle q}$${\displaystyle C:\{0,1\}^{k}\rightarrow \{0,1\}^{n}}$${\displaystyle (q,\delta \geq 0,\epsilon \geq 0)}$${\displaystyle D:\{0,1\}^{n}\rightarrow \{0,1\}^{k}}$${\displaystyle \Delta (x,y)}$${\displaystyle x}$${\displaystyle y}$

${\displaystyle \forall x\in \{0,1\}^{k},\forall y\in \{0,1\}^{n}}$は、${\displaystyle \Delta (y,C(x))\leq \delta n}$${\displaystyle Pr[D(y)_{i}=x_{i}]\geq {\frac {1}{2}}+\epsilon ,\forall i\in [k]}$

定理1:ウォルシュ・アダマール符号はすべての に対して -局所的に復号可能である。 ${\displaystyle (2,\delta ,{\frac {1}{2}}-2\delta )}$${\displaystyle 0\leq \delta \leq {\frac {1}{4}}}$

補題 1:すべてのコードワードについて、ウォルシュ・アダマール符号では、、が成り立ちます。ここで、 はそれぞれ位置とのビットを表し、 は位置 のビットを表します。 ${\displaystyle c}$${\displaystyle C}$${\displaystyle c_{i}+c_{j}=c_{i+j}}$${\displaystyle c_{i},c_{j}}$${\displaystyle c}$${\displaystyle i}$${\displaystyle j}$${\displaystyle c_{i+j}}$${\displaystyle (i+j)}$

をメッセージに対応するのコードワードとします。 ${\displaystyle C(x)=c=(c_{0},\dots ,c_{2^{n}-1})}$${\displaystyle C}$${\displaystyle x}$

を の生成行列とします。 ${\displaystyle G={\begin{pmatrix}\uparrow &\uparrow &&\uparrow \\g_{0}&g_{1}&\dots &g_{2^{n}-1}\\\downarrow &\downarrow &&\downarrow \end{pmatrix}}}$${\displaystyle C}$

定義により、。このことから、。 の構築により、。したがって、代入により、。 ${\displaystyle c_{i}=x\cdot g_{i}}$${\displaystyle c_{i}+c_{j}=x\cdot g_{i}+x\cdot g_{j}=x\cdot (g_{i}+g_{j})}$${\displaystyle G}$${\displaystyle g_{i}+g_{j}=g_{i+j}}$${\displaystyle c_{i}+c_{j}=x\cdot g_{i+j}=c_{i+j}}$

定理 1 を証明するために、復号アルゴリズムを構築し、その正しさを証明します。

入力:受信した単語${\displaystyle y=(y_{0},\dots ,y_{2^{n}-1})}$

それぞれについて: ${\displaystyle i\in \{1,\dots ,n\}}$

1. 均一にランダムに選択します。${\displaystyle j\in \{0,\dots ,2^{n}-1\}}$
2. となるものを選択します。ここで、 は- 番目の標準基底ベクトルであり、 はとのビット単位の排他的論理和です。${\displaystyle k\in \{0,\dots ,2^{n}-1\}}$${\displaystyle j+k=e_{i}}$${\displaystyle e_{i}}$${\displaystyle i}$${\displaystyle j+k}$${\displaystyle j}$${\displaystyle k}$
3. ${\displaystyle x_{i}\gets y_{j}+y_{k}}$。

出力:メッセージ${\displaystyle x=(x_{1},\dots ,x_{n})}$

任意のメッセージ、および と最大ビットの割合で異なる受信語は、少なくとも の確率でデコードできます。 ${\displaystyle x}$${\displaystyle y}$${\displaystyle y}$${\displaystyle c=C(x)}$${\displaystyle \delta }$${\displaystyle x_{i}}$${\displaystyle {\frac {1}{2}}+({\frac {1}{2}}-2\delta )}$

補題 1 により、となります。および は一様に選択されるため、 の確率は最大で です。同様に、 の確率は最大でです。和集合により、またはのいずれかが の対応するビットと一致しない確率は最大で です。と の両方が に対応する場合、補題 1 が適用され、したがって の適切な値が計算されます。したがって、 が適切に復号化される確率は少なくとも です。したがって、 のおよび が正であるためには です。 ${\displaystyle c_{j}+c_{k}=c_{j+k}=x\cdot g_{j+k}=x\cdot e_{i}=x_{i}}$${\displaystyle j}$${\displaystyle k}$${\displaystyle y_{j}\not =c_{j}}$${\displaystyle \delta }$${\displaystyle y_{k}\not =c_{k}}$${\displaystyle \delta }$${\displaystyle y_{j}}$${\displaystyle y_{k}}$${\displaystyle c}$${\displaystyle 2\delta }$${\displaystyle y_{j}}$${\displaystyle y_{k}}$${\displaystyle c}$${\displaystyle x_{i}}$${\displaystyle x_{i}}$${\displaystyle 1-2\delta }$${\displaystyle \epsilon ={\frac {1}{2}}-2\delta }$${\displaystyle \epsilon }$${\displaystyle 0\leq \delta \leq {\frac {1}{4}}}$

したがって、ウォルシュ・アダマール符号はに対して局所的にデコード可能です。 ${\displaystyle (2,\delta ,{\frac {1}{2}}-2\delta )}$${\displaystyle 0\leq \delta \leq {\frac {1}{4}}}$

k ≤ 7の場合、 線形アダマール符号は最小距離の意味で最適であることが証明されている。^[7]

• ザドフ・チューシーケンス— ウォルシュ・アダマールコードの改良

• Rudra, Atri. 「ハミング符号とハミング境界」(PDF)。講義ノート。
• Rudolph, Dietmar; Rudolph, Matthias (2011-04-12). 「46.4. Hadamard– oder Walsh–Codes」. Modulationsverfahren (PDF) (ドイツ語). コトブス、ドイツ:ブランデンブルク工科大学(BTU). p. 214. 2021-06-16 にオリジナルからアーカイブ(PDF)されました。2021-06-14に取得。（14+225ページ）