Error-correcting code
アダマールコード 名前の由来 ジャック・アダマール タイプ 線形 ブロックコード ブロック長 n = 2 k {\displaystyle n=2^{k}} メッセージの長さ k {\displaystyle k} レート k / 2 k {\displaystyle k/2^{k}} 距離 d = 2 k − 1 {\displaystyle d=2^{k-1}} アルファベットのサイズ 2 {\displaystyle 2} 表記 [ 2 k , k , 2 k − 1 ] 2 {\displaystyle [2^{k},k,2^{k-1}]_{2}} -コード
拡張アダマール符号 名前の由来 ジャック・アダマール タイプ 線形 ブロックコード ブロック長 n = 2 k {\displaystyle n=2^{k}} メッセージの長さ k + 1 {\displaystyle k+1} レート ( k + 1 ) / 2 k {\displaystyle (k+1)/2^{k}} 距離 d = 2 k − 1 {\displaystyle d=2^{k-1}} アルファベットのサイズ 2 {\displaystyle 2} 表記 [ 2 k , k + 1 , 2 k − 1 ] 2 {\displaystyle [2^{k},k+1,2^{k-1}]_{2}} -コード
NASA宇宙探査機 マリナー9号の リード・ミュラーコード （1, 5）に対する拡張アダマールコード[32, 6, 16]の行列 XOR 演算 ここで白いフィールドは0 、赤いフィールドは1を表します アダマール 符号は フランスの数学者 ジャック・アダマールにちなんで名付けられた 誤り訂正符号 であり 、ノイズの多いまたは信頼性の低いチャネルでメッセージを送信するときに エラー検出と訂正 に使用されます。1971 年には、この符号を使用して、NASA の宇宙探査機 マリナー 9 号 から地球に火星の写真が送信されました。 [1] アダマール符号は、そのユニークな数学的特性のため、エンジニアによって使用されるだけでなく、 符号理論 、 数学 、 理論計算機科学の 分野でも熱心に研究されています。アダマール符号は、 アメリカの数学者 ジョセフ・レナード・ウォルシュにちなんで、 ウォルシュ符号 、 ウォルシュファミリー 、 [2] 、 ウォルシュ・アダマール符号 [3] とも呼ばれています。
アダマール符号は、長さ の 線形符号を 2進アルファベット で 表す例です 。残念ながら、この用語はやや曖昧で、参考文献によってはメッセージ長 を仮定している ものもあれば、 を仮定しているものもあります 。この記事では、前者を アダマール符号 、後者を 拡大アダマール符号 と呼びます。 2 m {\displaystyle 2^{m}} k = m {\displaystyle k=m} k = m + 1 {\displaystyle k=m+1}
アダマール符号は、各非ゼロ符号語の ハミング重み がちょうど である点で独特であり 、これは 符号の 距離 も であることを意味する。 ブロック符号 の標準的な 符号化理論表記法 では、アダマール符号は -符号、つまり 2進アルファベット 上の 線形符号 であり、 ブロック長 、 メッセージ長 （または次元） 、 最小距離 を 持つ。ブロック長はメッセージ長に比べて非常に大きいが、一方で、極めてノイズの多い状況でも誤りを訂正できる。 2 k − 1 {\displaystyle 2^{k-1}} 2 k − 1 {\displaystyle 2^{k-1}} [ 2 k , k , 2 k − 1 ] 2 {\displaystyle [2^{k},k,2^{k-1}]_{2}} 2 k {\displaystyle 2^{k}} k {\displaystyle k} 2 k / 2 {\displaystyle 2^{k}/2}
拡張アダマール符号は、アダマール符号の若干改良版である。これは -符号であるため、 相対距離を維持しながら わずかに優れた レートを 持ち、実用化において好まれる。通信理論では、これは単にアダマール符号と呼ばれ、 2進アルファベット上の1次 リード・ミュラー符号 と同じである。 [4] [ 2 k , k + 1 , 2 k − 1 ] 2 {\displaystyle [2^{k},k+1,2^{k-1}]_{2}} 1 / 2 {\displaystyle 1/2}
通常、アダマール符号はシルベスターによるアダマール行列の構築 に基づいています が、「アダマール符号」という用語は、必ずしもシルベスター型ではない任意の アダマール行列 から構築された符号を指す場合にも使用されます。一般に、このような符号は線形ではありません。このような符号は、 1959 年に Raj Chandra Bose と Sharadchandra Shankar Shrikhandeによって初めて構築されました 。[5] n がアダマール行列のサイズである
場合 、符号にはパラメータ があり、これは 、ブロック長 n で最小距離 n /2 の 2 n 符号語を持つ、必ずしも線形ではない 2 進符号であることを意味します 。以下で説明する構築および復号化方式は一般的な n に適用されますが、線形性の特性およびリード・ミュラー符号との同一視により、 n は 2 の累乗であり、アダマール行列はシルベスター法によって構築された行列と等価である必要があります。 ( n , 2 n , n / 2 ) 2 {\displaystyle (n,2n,n/2)_{2}}
アダマール符号は 局所的に復号可能な 符号であり、受信語のごく一部を見るだけで、元のメッセージの一部を高い確率で復元する方法を提供します。これは 計算複雑性理論、特に 確率的に検証可能な証明 の設計に応用されています 。アダマール符号の相対距離は1/2であるため、通常は最大でも1/4の誤りしか復元できません。しかし、 リスト復号法 を用いることで、受信語のビット数よりも少ないビット数が破損している限り、候補メッセージの短いリストを計算することが可能です 。 1 2 − ϵ {\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メートルを超えるアンテナではこの誤り訂正方式をサポートしていません。
建設 すべてのアダマール符号はアダマール行列に基づいていますが、その構成は科学分野、著者、用途によって微妙に異なります。データ伝送に符号を使用するエンジニアや、符号の極限特性を分析する 符号理論家は 、たとえ構成が数学的に多少洗練されなくなるとしても、符号の レートを 可能な限り高くすることを一般的に望んでいます。
一方、 理論計算機科学 におけるアダマール符号の多くの応用では、最適なレートを達成することはそれほど重要ではないため、より簡潔なアダマール符号の構成の方が、よりエレガントに分析できるため好まれます。
内積を用いた構成 長さ の バイナリ メッセージが与えられると、アダマール コードは エンコード関数 を使用して メッセージをコードワードにエンコードします。この関数は 、次のように定義される 2 つのベクトルの 内積 を使用します。 x ∈ { 0 , 1 } k {\displaystyle x\in \{0,1\}^{k}} k {\displaystyle k} Had ( x ) {\displaystyle {\text{Had}}(x)} Had : { 0 , 1 } k → { 0 , 1 } 2 k . {\displaystyle {\text{Had}}:\{0,1\}^{k}\to \{0,1\}^{2^{k}}.} ⟨ x , y ⟩ {\displaystyle \langle x,y\rangle } x , y ∈ { 0 , 1 } k {\displaystyle x,y\in \{0,1\}^{k}}
⟨ x , y ⟩ = ∑ i = 1 k x i y i mod 2 . {\displaystyle \langle x,y\rangle =\sum _{i=1}^{k}x_{i}y_{i}\ {\bmod {\ }}2\,.} のアダマール符号化は、 のすべての 内積 の列として定義されます 。 x {\displaystyle x} x {\displaystyle x}
Had ( x ) = ( ⟨ x , y ⟩ ) y ∈ { 0 , 1 } k {\displaystyle {\text{Had}}(x)={\Big (}\langle x,y\rangle {\Big )}_{y\in \{0,1\}^{k}}} 前述のように、 アダマール符号自体に多少の無駄があるため、実際には 拡張 アダマール符号が使用されます。これは、 の最初のビットがゼロの場合 、内積には に関する情報が全く含まれず 、したがって、 符号語のこれらの位置のみから完全に復号することは不可能だからです。一方、符号語が の位置に制約されている場合でも 、 を完全に復号することは可能です。したがって、アダマール符号をこれらの位置に制約することは理にかなっています。これにより、 の 拡張 アダマール符号化、 つまり が生成されます 。 y {\displaystyle y} y 1 = 0 {\displaystyle y_{1}=0} x 1 {\displaystyle x_{1}} x {\displaystyle x} y 1 = 1 {\displaystyle y_{1}=1} x {\displaystyle x} x {\displaystyle x} pHad ( x ) = ( ⟨ x , y ⟩ ) y ∈ { 1 } × { 0 , 1 } k − 1 {\displaystyle {\text{pHad}}(x)={\Big (}\langle x,y\rangle {\Big )}_{y\in \{1\}\times \{0,1\}^{k-1}}}
生成行列を用いた構築 アダマール符号は線型符号であり、すべての線型符号は生成行列 によって生成できる 。これは、 すべての に対して が成り立つような行列で あり、メッセージは 行ベクトルとみなされ、ベクトル行列積は 有限体 上の ベクトル空間で理解される。特に、アダマール符号の内積定義を記述する同等の方法は、 すべての 列が長さ の文字 列 で構成される生成行列 を用いることで得られる。 すなわち、 G {\displaystyle G} Had ( x ) = x ⋅ G {\displaystyle {\text{Had}}(x)=x\cdot G} x ∈ { 0 , 1 } k {\displaystyle x\in \{0,1\}^{k}} x {\displaystyle x} F 2 {\displaystyle \mathbb {F} _{2}} y {\displaystyle y} k {\displaystyle k}
G = ( ↑ ↑ ↑ y 1 y 2 … y 2 k ↓ ↓ ↓ ) . {\displaystyle G={\begin{pmatrix}\uparrow &\uparrow &&\uparrow \\y_{1}&y_{2}&\dots &y_{2^{k}}\\\downarrow &\downarrow &&\downarrow \end{pmatrix}}\,.} ここで 、 は 辞書式順序 で 番目の2進ベクトルです 。例えば、次元 のアダマール符号の生成行列は次の ようになります。 y i ∈ { 0 , 1 } k {\displaystyle y_{i}\in \{0,1\}^{k}} i {\displaystyle i} k = 3 {\displaystyle k=3}
G = [ 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 ] . {\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}}.} 行列は-行列 であり、 線形演算子 を生成します 。 G {\displaystyle G} ( k × 2 k ) {\displaystyle (k\times 2^{k})} Had : { 0 , 1 } k → { 0 , 1 } 2 k {\displaystyle {\text{Had}}:\{0,1\}^{k}\to \{0,1\}^{2^{k}}}
拡張 アダマール符号の生成行列は、行列の最初の要素が1である列のみに 制限することによって得られる 。例えば、次元の拡張アダマール符号の生成行列は次 のようになる。 G {\displaystyle G} k = 3 {\displaystyle k=3}
G ′ = [ 1 1 1 1 0 0 1 1 0 1 0 1 ] . {\displaystyle G'={\begin{bmatrix}1&1&1&1\\0&0&1&1\\0&1&0&1\end{bmatrix}}.} は との線形マッピングです 。 pHad : { 0 , 1 } k → { 0 , 1 } 2 k − 1 {\displaystyle {\text{pHad}}:\{0,1\}^{k}\to \{0,1\}^{2^{k-1}}} pHad ( x ) = x ⋅ G ′ {\displaystyle {\text{pHad}}(x)=x\cdot G'}
一般に 、拡大アダマール符号の生成行列は、 長 さ 、次元の 拡張ハミング符号 の パリティ検査行列 であり、これにより拡大アダマール符号は拡張ハミング符号の 双対符号 となる。したがって、アダマール符号を定義する別の方法は、そのパリティ検査行列を用いて定義することである。すなわち、アダマール符号のパリティ検査行列は、ハミング符号の生成行列に等しい。 k {\displaystyle k} 2 k − 1 {\displaystyle 2^{k-1}} 2 k − 1 − k {\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 が シルベスター型である必要があり、これによりメッセージ長が になります 。 n = 2 k − 1 {\displaystyle n=2^{k-1}} log 2 ( 2 n ) = k {\displaystyle \log _{2}(2n)=k}
距離 符号の距離とは、 任意の2つの異なる符号語間の最小 ハミング距離、すなわち、2つの異なる符号語が異なる位置の最小数です。ウォルシュ・アダマール符号は 線形符号であるため、この距離は、その符号語に含まれるすべての非ゼロ符号語の ハミング重み の最小値に等しくなります 。ウォルシュ・アダマール符号のすべての非ゼロ符号語の ハミング重み は、次の式によって 正確に となります。 2 k − 1 {\displaystyle 2^{k-1}}
を非ゼロのメッセージとし ます。すると、次の値は、コードワード内の1に等しい位置の割合と正確に等しくなります。 x ∈ { 0 , 1 } k {\displaystyle x\in \{0,1\}^{k}}
Pr y ∈ { 0 , 1 } k [ ( Had ( x ) ) y = 1 ] = Pr y ∈ { 0 , 1 } k [ ⟨ x , y ⟩ = 1 ] . {\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 ]}\,.} 後者の値がちょうど であるという事実は、 ランダムサブサム原理 と呼ばれます 。これが真であることを確認するために、一般性を失うことなく と仮定します 。すると、 の値を条件とすると、 および に 依存する いくつかの に対して、イベントは と等しくなります 。 が発生する確率 はちょうど です 。したがって、実際には、アダマール符号の すべての 非ゼロ符号語は相対ハミング重み を持ち 、したがって、その相対距離は です 。 1 / 2 {\displaystyle 1/2} x 1 = 1 {\displaystyle x_{1}=1} y 2 , … , y k {\displaystyle y_{2},\dots ,y_{k}} y 1 ⋅ x 1 = b {\displaystyle y_{1}\cdot x_{1}=b} b ∈ { 0 , 1 } {\displaystyle b\in \{0,1\}} x 2 , … , x k {\displaystyle x_{2},\dots ,x_{k}} y 2 , … , y k {\displaystyle y_{2},\dots ,y_{k}} y 1 = b {\displaystyle y_{1}=b} 1 / 2 {\displaystyle 1/2} 1 / 2 {\displaystyle 1/2} 1 / 2 {\displaystyle 1/2}
拡大 アダマール符号 の相対距離も同様ですが、すべての s ベクトル が拡大アダマール符号の符号語となる ため、 すべての非ゼロ符号語の重みがちょうど になるという性質はもはやありません。これは、ベクトル が にエンコードされるためです 。さらに、 が非ゼロでベクトル でない場合は常に 、ランダム和原理が再び適用され、 の相対重みは ちょうど になります 。 1 / 2 {\displaystyle 1/2} 1 / 2 {\displaystyle 1/2} 1 {\displaystyle 1} 1 2 k − 1 {\displaystyle 1^{2^{k-1}}} x = 10 k − 1 {\displaystyle x=10^{k-1}} pHad ( 10 k − 1 ) = 1 2 k − 1 {\displaystyle {\text{pHad}}(10^{k-1})=1^{2^{k-1}}} x {\displaystyle x} 10 k − 1 {\displaystyle 10^{k-1}} Had ( x ) {\displaystyle {\text{Had}}(x)} 1 / 2 {\displaystyle 1/2}
ローカルデコード可能性 ローカル にデコード可能な コードとは、受信したワードの小さな部分を見るだけで、元のメッセージの 1 ビットを高い確率で復元できるコードです。
符号 が -クエリ 局所復号 可能とは、メッセージビット が受信語のビット を調べることで復元できる場合である 。より正式には、符号 が-クエリ局所復号可能とは 、 確率的復号器 が存在し、 （ 注： は ベクトル との間の ハミング距離 を表す ） を満たす場合である。 q {\displaystyle q} x i {\displaystyle x_{i}} q {\displaystyle q} C : { 0 , 1 } k → { 0 , 1 } n {\displaystyle C:\{0,1\}^{k}\rightarrow \{0,1\}^{n}} ( q , δ ≥ 0 , ϵ ≥ 0 ) {\displaystyle (q,\delta \geq 0,\epsilon \geq 0)} D : { 0 , 1 } n → { 0 , 1 } k {\displaystyle D:\{0,1\}^{n}\rightarrow \{0,1\}^{k}} Δ ( x , y ) {\displaystyle \Delta (x,y)} x {\displaystyle x} y {\displaystyle y}
∀ x ∈ { 0 , 1 } k , ∀ y ∈ { 0 , 1 } n {\displaystyle \forall x\in \{0,1\}^{k},\forall y\in \{0,1\}^{n}} は 、 Δ ( y , C ( x ) ) ≤ δ n {\displaystyle \Delta (y,C(x))\leq \delta n} P r [ D ( y ) i = x i ] ≥ 1 2 + ϵ , ∀ i ∈ [ k ] {\displaystyle Pr[D(y)_{i}=x_{i}]\geq {\frac {1}{2}}+\epsilon ,\forall i\in [k]}
定理1: ウォルシュ・アダマール符号は すべての に対して -局所的にデコード可能である 。 ( 2 , δ , 1 2 − 2 δ ) {\displaystyle (2,\delta ,{\frac {1}{2}}-2\delta )} 0 ≤ δ ≤ 1 4 {\displaystyle 0\leq \delta \leq {\frac {1}{4}}}
補題 1: すべてのコードワードについて、 ウォルシュ・アダマール コードでは、 、 はそれぞれ 位置 および の ビットを表し 、 は 位置 のビットを表します 。 c {\displaystyle c} C {\displaystyle C} c i + c j = c i + j {\displaystyle c_{i}+c_{j}=c_{i+j}} c i , c j {\displaystyle c_{i},c_{j}} c {\displaystyle c} i {\displaystyle i} j {\displaystyle j} c i + j {\displaystyle c_{i+j}} ( i + j ) {\displaystyle (i+j)}
補題1の証明 をメッセージ に対応する のコードワードとし ます 。 C ( x ) = c = ( c 0 , … , c 2 n − 1 ) {\displaystyle C(x)=c=(c_{0},\dots ,c_{2^{n}-1})} C {\displaystyle C} x {\displaystyle x}
を の生成行列とし ます 。 G = ( ↑ ↑ ↑ g 0 g 1 … g 2 n − 1 ↓ ↓ ↓ ) {\displaystyle G={\begin{pmatrix}\uparrow &\uparrow &&\uparrow \\g_{0}&g_{1}&\dots &g_{2^{n}-1}\\\downarrow &\downarrow &&\downarrow \end{pmatrix}}} C {\displaystyle C}
定義により、 。このことから、 。 の構築により 、 。したがって、置き換えにより、 。 c i = x ⋅ g i {\displaystyle c_{i}=x\cdot g_{i}} c i + c j = x ⋅ g i + x ⋅ g j = x ⋅ ( g i + g j ) {\displaystyle c_{i}+c_{j}=x\cdot g_{i}+x\cdot g_{j}=x\cdot (g_{i}+g_{j})} G {\displaystyle G} g i + g j = g i + j {\displaystyle g_{i}+g_{j}=g_{i+j}} c i + c j = x ⋅ g i + j = c i + j {\displaystyle c_{i}+c_{j}=x\cdot g_{i+j}=c_{i+j}}
定理1の証明 定理 1 を証明するために、復号化アルゴリズムを構築し、その正しさを証明します。
アルゴリズム 入力: 受信した単語 y = ( y 0 , … , y 2 n − 1 ) {\displaystyle y=(y_{0},\dots ,y_{2^{n}-1})}
それぞれについて ： i ∈ { 1 , … , n } {\displaystyle i\in \{1,\dots ,n\}}
均一にランダムに選択します 。 j ∈ { 0 , … , 2 n − 1 } {\displaystyle j\in \{0,\dots ,2^{n}-1\}} となるもの を選択します。 ここで、 は - 番目の 標準基底ベクトル であり、は との ビット単位 の XOR です。 k ∈ { 0 , … , 2 n − 1 } {\displaystyle k\in \{0,\dots ,2^{n}-1\}} j + k = e i {\displaystyle j+k=e_{i}} e i {\displaystyle e_{i}} i {\displaystyle i} j + k {\displaystyle j+k} j {\displaystyle j} k {\displaystyle k} x i ← y j + y k {\displaystyle x_{i}\gets y_{j}+y_{k}} 。 出力: メッセージ x = ( x 1 , … , x n ) {\displaystyle x=(x_{1},\dots ,x_{n})}
正しさの証明 任意のメッセージ、および と 最大 ビットの割合 で異なる 受信 語は、 少なくとも の確率でデコードできます 。 x {\displaystyle x} y {\displaystyle y} y {\displaystyle y} c = C ( x ) {\displaystyle c=C(x)} δ {\displaystyle \delta } x i {\displaystyle x_{i}} 1 2 + ( 1 2 − 2 δ ) {\displaystyle {\frac {1}{2}}+({\frac {1}{2}}-2\delta )}
補題1により、 となります 。 と は 一様に選択されるため、 の確率は 最大で となります 。同様に、 の確率は 最大で となります。 の 和集合境界 により、 または のいずれ か が の対応するビット と一致しない確率は 最大で となります 。 と の両方が に対応する場合 、 補題 1が適用され、 の適切な値が 計算されます。したがって、 が正しく復号される確率 は少なくとも となります 。したがって、 および が 正であるためには、 となります 。 c j + c k = c j + k = x ⋅ g j + k = x ⋅ e i = x i {\displaystyle c_{j}+c_{k}=c_{j+k}=x\cdot g_{j+k}=x\cdot e_{i}=x_{i}} j {\displaystyle j} k {\displaystyle k} y j ≠ c j {\displaystyle y_{j}\not =c_{j}} δ {\displaystyle \delta } y k ≠ c k {\displaystyle y_{k}\not =c_{k}} δ {\displaystyle \delta } y j {\displaystyle y_{j}} y k {\displaystyle y_{k}} c {\displaystyle c} 2 δ {\displaystyle 2\delta } y j {\displaystyle y_{j}} y k {\displaystyle y_{k}} c {\displaystyle c} x i {\displaystyle x_{i}} x i {\displaystyle x_{i}} 1 − 2 δ {\displaystyle 1-2\delta } ϵ = 1 2 − 2 δ {\displaystyle \epsilon ={\frac {1}{2}}-2\delta } ϵ {\displaystyle \epsilon } 0 ≤ δ ≤ 1 4 {\displaystyle 0\leq \delta \leq {\frac {1}{4}}}
したがって、ウォルシュ・アダマール符号は に対して局所的にデコード可能です 。 ( 2 , δ , 1 2 − 2 δ ) {\displaystyle (2,\delta ,{\frac {1}{2}}-2\delta )} 0 ≤ δ ≤ 1 4 {\displaystyle 0\leq \delta \leq {\frac {1}{4}}}
最適性 k≤7 の場合、 線形アダマール符号は最小距離の意味で最適であることが証明されている。 [7]
参照
参考文献 ^ Malek, Massoud (2006). 「アダマール符号」. 符号理論 (PDF) . 2020年1月9日時点のオリジナル (PDF) からのアーカイブ。 ^ Amadei, M.; Manzoli, Umberto; Merani, Maria Luisa (2002-11-17). 「複数クラスのユーザを持つマルチキャリアDS-CDMAシステムにおけるウォルシュ符号と準直交符号の割り当てについて」. Global Telecommunications Conference, 2002. GLOBECOM'02. IEEE. 第1巻. IEEE . pp. 841– 845. doi :10.1109/GLOCOM.2002.1188196. ISBN 0-7803-7632-3 。 ^ Arora, Sanjeev ; Barak, Boaz (2009). 「Section 19.2.2. 計算複雑性：現代的アプローチ」 ケンブリッジ大学出版局 . ISBN 978-0-521-42426-4 。 ^ Guruswami, Venkatesan (2009). バイナリコードのリストデコード (PDF) . p. 3. ^ Bose, Raj Chandra ; Shrikhande, Sharadchandra Shankar (1959年6月). 「コード構築理論における結果に関するノート」. Information and Control . 2 (2): 183– 194. CiteSeerX 10.1.1.154.2879 . doi :10.1016/S0019-9958(59)90376-6. ^ Langton, Charan [Wikidataにて] (2002). 「CDMAチュートリアル：通信原理の直感的なガイド」 （PDF） . 複素数から実数へ. 2011年7月20日時点のオリジナルよりアーカイブ （PDF） 。 2017年11月10日 閲覧 。 ^ Jaffe, David B.; Bouyukliev, Iliya. 「最大7次元の最適2進線形符号」。2007年8月8日時点のオリジナルよりアーカイブ。 2007年8月21日 閲覧 。
さらに読む Rudra, Atri. 「ハミング符号とハミング境界」 （PDF） . 講義ノート . Rudolph, Dietmar; Rudolph, Matthias (2011-04-12). "46.4. Hadamard– oder Walsh–Codes". Modulationsverfahren (PDF) (ドイツ語). コトブス, ドイツ: ブランデンブルク工科大学 (BTU). p. 214. 2021年6月16日時点のオリジナルよりアーカイブ (PDF) . 2021年6月 14日閲覧 。 （14+225ページ）
データ圧縮 エラー訂正 テレメトリコマンドアップリンク テレメトリダウンリンク テレメトリ全般 テレメトリ変調システム 周波数 ネットワーク、相互運用性、監視
![{\displaystyle [2^{k},k,2^{k-1}]_{2}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4c61084e4ec593311b8d2e834afabf4d432a1916)
![{\displaystyle [2^{k},k+1,2^{k-1}]_{2}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/33dd8f1c5efa897cd15747ab8be5b594038db3af)
![{\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 ]}\,.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/06608d6f4e85e02437feadfee966819b06cefd0b)
![{\displaystyle Pr[D(y)_{i}=x_{i}]\geq {\frac {1}{2}}+\epsilon ,\forall i\in [k]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e32fc2f85a3ba5f7a3583457ef5ebf38830a2d00)
