デコード方法

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

${\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}$

各コードワードには予想される可能性はありません。受信メッセージに変化する可能性が等しいコードワードが複数ある可能性があります。このような場合、送信者と受信者は事前にデコード規則に同意する必要があります。一般的な規則には次のものがあります。

1. コードワードの再送信を要求します – 自動繰り返し要求。
2. 最も可能性の高いコードワードのセットから、それに最も近い任意のランダムなコードワードを選択します。
3. 別のコードが続く場合は、コードワードの曖昧な部分を消去としてマークし、外側のコードがそれらを曖昧さなくすることを期待します。
4. システムにデコード失敗を報告する

受信ベクトルが与えられた場合、最大尤度復号は、最大となる符号語を選択する。${\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{ 送信された}})}$${\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}$

${\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 は半分未満なので）d を最小化することによって最大化されます。

最小距離デコードは、最近傍デコードとも呼ばれます。標準配列を使用して支援または自動化できます。最小距離デコードは、次の条件が満たされている場合に適切なデコード方法です。

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

これらの仮定は、バイナリ対称チャネルを介した送信では妥当である可能性があります。ただし、ディスク上の 1 つの傷が隣接する多数のシンボルまたはコードワードでエラーを引き起こす可能性がある 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}$

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

しかし、送信中にエラーが1000件以上発生しなかったと仮定すると、受信側はさらにサイズが縮小されたテーブルで 値を検索することができる。${\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}}}$

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

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

ビタビ デコーダは、畳み込みコードに基づく前方誤り訂正を使用してエンコードされたビットストリームをデコードするためにビタビ アルゴリズムを使用します。ハミング距離は、ハード決定ビタビ デコーダのメトリックとして使用されます。2乗 ユークリッド距離は、ソフト決定デコーダのメトリックとして使用されます。

非対称TWRCシステムのための最適決定復号アルゴリズム（ODDA）。^{[説明が必要] [6]}

• 気にしないアラーム
• エラー検出と修正
• 禁止された入力

• ヒル、レイモンド (1986)。符号理論入門。オックスフォード応用数学および計算科学シリーズ。オックスフォード大学出版局。ISBN 978-0-19-853803-5。
• Pless, Vera (1982)。誤り訂正符号理論入門。Wiley-Interscience 離散数学シリーズ。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。