復号方法

符号理論 において、復号とは、受信したメッセージを特定の符号の符号語に変換するプロセスである。メッセージを符号語にマッピングする一般的な方法は数多く存在する。これらは、二値対称チャネルなどのノイズの多いチャネルを介して送信されたメッセージを復元するためによく用いられる。

$\displaystyle C\subset \mathbb {F} _{2}^{n}}$長さのバイナリコードとみなされる${\displaystyle n}$;${\displaystyle x,y}$要素となる$\displaystyle \mathbb {F} _{2}^{n}}$; そして${\displaystyle d(x,y)}$それは、それらの要素間の距離です。

メッセージを受け取ることができる${\displaystyle x\in \mathbb {F} _{2}^{n}}$すると、理想的な観測者復号によってコードワードが生成される。${\displaystyle y\in C}$このプロセスを経て、以下の解決策が得られます。

${\displaystyle \mathbb {P} (y{\mbox{ 送信}}\mid x{\mbox{ 受信}})}$

例えば、人はコードワードを選ぶことができる${\displaystyle y}$それはメッセージとして最も受け取られる可能性が高い${\displaystyle x}$送信後。

受信ベクトルが与えられた場合${\displaystyle x\in \mathbb {F} _{2}^{n}}$最尤復号法はコードワードを選択する${\displaystyle y\in C}$最大化する

${\displaystyle \mathbb {P} (x{\mbox{受信}}\mid y{\mbox{送信}})}$、

つまり、コードワード${\displaystyle y}$それは、${\displaystyle x}$受け取ったのは、${\displaystyle y}$が送信されました。すべてのコードワードが等しく送信される場合、この方式は理想的な観測者復号と同等です。実際、ベイズの定理により、

${\displaystyle {\begin{aligned}\mathbb {P} (x{\mbox{ received}}\mid y{\mbox{ sent}})&{}={\frac {\mathbb {P} (x{\mbox{ received}},y{\mbox{ sent}})}{\mathbb {P} (y{\mbox{ sent}})}}\\&{}=\mathbb {P} (y{\mbox{ sent}}\mid x{\mbox{ received}})\cdot {\frac {\mathbb {P} (x{\mbox{ received}})}{\mathbb {P} (y{\mbox{ sent}})}}.\end{aligned}}}$

修正後${\displaystyle \mathbb {P} (x{\mbox{ 受信}})}$、${\displaystyle x}$再編され、 ${\displaystyle \mathbb {P} (y{\mbox{ sent}})}$すべての符号語が等しく送信される可能性が高いため、は一定です。したがって、 ${\displaystyle \mathbb {P} (x{\mbox{受信}}\mid y{\mbox{送信}})}$ 変数の関数として最大化される${\displaystyle y}$まさにその時 ${\displaystyle \mathbb {P} (y{\mbox{ 送信}}\mid x{\mbox{ 受信}})}$ が最大化され、主張が続く。

理想的な観測者による復号と同様に、一意でない復号についても、合意された規約が必要である。

最尤復号問題は、整数計画問題としてモデル化することもできる。^{[ 1 ]}

最尤復号アルゴリズムは、「積関数を周辺化する」問題の一例であり、一般化された分配法則を適用することで解決される。^{[ 2 ]}

受信ベクトルが与えられた場合${\displaystyle x\in \mathbb {F} _{2}^{n}}$最小距離復号ではコードワードを選択する${\displaystyle y\in C}$ハミング距離を最小化する：

${\displaystyle d(x,y)=|\{i:x_{i}\not =y_{i}\}|}$

つまり、コードワードを選択する${\displaystyle y}$それは可能な限り${\displaystyle x}$。

離散的なメモリレスチャネルにおけるエラーの確率は${\displaystyle p}$が厳密に 1/2 より小さい場合、最小距離復号は最大尤度復号と等価である。

${\displaystyle d(x,y)=d,\,}$

それから：

${\displaystyle {\begin{aligned}\mathbb {P} (y{\mbox{ received}}\mid x{\mbox{ sent}})&{}=(1-p)^{nd}\cdot p^{d}\\&{}=(1-p)^{n}\cdot \left({\frac {p}{1-p}}\right)^{d}\\\end{aligned}}}$

これは（pが1/2未満であるため）dを最小化することによって最大化されます。

最小距離復号は最近傍復号とも呼ばれます。標準アレイを使用することで、補助または自動化できます。最小距離復号は、以下の条件が満たされる場合に妥当な復号方法です。

1. 確率${\displaystyle p}$エラーが発生するかどうかは、シンボルの位置とは無関係である。
2. エラーは独立した事象であり、メッセージのある位置でのエラーは他の位置に影響を与えません。 

これらの仮定は、バイナリ対称チャネルを介した伝送においては妥当であるかもしれない。しかし、 DVDなどの他の媒体においては、ディスク上のわずかな傷が隣接する多くのシンボルや符号語にエラーを引き起こす可能性があるため、これらの仮定は不適切である可能性がある。

他の復号方法と同様に、一意でない復号についても、合意された規則が必要である。

シンドローム復号は、ノイズのあるチャネル、つまりエラーが発生するチャネル上で線形コードを復号する非常に効率的な方法です。本質的に、シンドローム復号は、縮小ルックアップテーブルを使用した最小距離復号です。これは、コードの線形性によって可能になります。^{[ 3 ]}

仮に$\displaystyle C\subset \mathbb {F} _{2}^{n}}$長さの線形コードです${\displaystyle n}$最小距離${\displaystyle d}$パリティチェック行列付き${\displaystyle H}$すると明らかに${\displaystyle C}$最大で修正可能

${\displaystyle t=\left\lfloor {\frac {d-1}{2}}\right\rfloor }$

チャネルによって発生したエラー (もし以下であれば)${\displaystyle t}$エラーが発生した場合でも、最小距離復号法は誤って送信された符号語を正しく復号します。

ここで、コードワードが${\displaystyle x\in \mathbb {F} _{2}^{n}}$チャネルを介して送信され、エラーパターン${\displaystyle e\in \mathbb {F} _{2}^{n}}$発生します。${\displaystyle z=x+e}$が受信されます。通常の最小距離復号では、ベクトルを検索します。${\displaystyle z}$サイズの表で${\displaystyle |C|}$最も近い一致、つまり要素（必ずしも一意である必要はない）${\displaystyle c\in C}$と

${\displaystyle d(c,z)\leq d(y,z)}$

すべての人々のために${\displaystyle y\in C}$シンドローム復号は、パリティ行列の以下の特性を利用します。

${\displaystyle Hx=0}$

すべての人々のために${\displaystyle x\in C}$受けた症候群${\displaystyle z=x+e}$は次のように定義されます。

${\displaystyle Hz=H(x+e)=Hx+He=0+He=He}$

バイナリ対称チャネルでML復号を実行するには、事前に計算されたサイズのテーブルを参照する必要があります。${\displaystyle 2^{n-k}}$、 マッピング${\displaystyle He}$に${\displaystyle e}$。

これは、標準的な配列デコードよりも既に大幅に複雑さが低いことに注意してください。

ただし、${\displaystyle t}$送信中にエラーが発生した場合、受信側で値を調べることができます${\displaystyle He}$さらに縮小されたサイズの表

${\displaystyle {\begin{matrix}\sum _{i=0}^{t}{\binom {n}{i}}\\\end{matrix}}}$

これはラスベガスの確率的手法の一種で、すべて「すべての誤りのある局面を推測するよりも、十分な数の誤りのない局面を推測する方が容易である」という観察に基づいています。

最も単純な形式はプランゲによるものである。${\displaystyle G}$になる${\displaystyle k\times n}$ジェネレーターマトリックス${\displaystyle C}$エンコードに使用されます。選択${\displaystyle k}$列${\displaystyle G}$ランダムに、そして、${\displaystyle G'}$対応するサブマトリックス${\displaystyle G}$合理的な確率で${\displaystyle G'}$完全なランクを持つことになります。つまり、${\displaystyle c'}$任意のコードワードの対応する位置のサブベクトルとする${\displaystyle c=mG}$の${\displaystyle C}$メッセージ${\displaystyle m}$回復できる${\displaystyle m}$として${\displaystyle m=c'G'^{-1}}$したがって、もし私たちが幸運にもこれら${\displaystyle k}$受信した単語の位置${\displaystyle y}$エラーが含まれていないため、送信されたコードワードの位置と一致する場合、復号することができます。

もし${\displaystyle t}$エラーが発生した場合、このような幸運な列の選択の確率は次のように与えられます。${\displaystyle \textstyle {\binom {n-t}{k}}/{\binom {n}{k}}\approx \exp(-tk/n)}$。

この方法は、例えば Stern ^{[ 4 ]}やCanteautと Sendrier ^{[ 5 ]によって様々な方法で改良されてきた。}

部分応答最大尤度法（PRML ）は、磁気ディスクまたはテープドライブのヘッドからの微弱なアナログ信号をデジタル信号に変換する方法です。

ビタビ復号器は、畳み込み符号に基づく前方誤り訂正を用いて符号化されたビットストリームを復号するために、ビタビアルゴリズムを使用します。ハードデシジョン型のビタビ復号器では、ハミング距離が評価指標として用いられます。ソフトデシジョン型のビタビ復号器では、ユークリッド距離の二乗が評価指標として用いられます。

非対称 TWRC システム用の最適な決定復号化アルゴリズム (ODDA)。 ^{[ 6 ]}

• アラームを気にしない
• エラー検出と訂正
• 入力禁止

• ヒル、レイモンド（1986）。『符号理論入門』。オックスフォード応用数学・計算機科学シリーズ。オックスフォード大学出版局。ISBN 978-0-19-853803-5。
• Pless, Vera (1982).誤り訂正符号理論入門. Wiley-Interscience Series in Discrete Mathematics. John Wiley & Sons . ISBN 978-0-471-08684-0。
• van Lint, Jacobus H. (1992).符号理論入門.大学院数学テキスト(GTM). 第 86 巻 (第 2 版). Springer-Verlag . ISBN 978-3-540-54894-2。