デコード方法

Algorithms to decode messages

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

表記

${\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{ sent}}\mid x{\mbox{ received}})}$

たとえば、送信後にメッセージとして受信される可能性が最も高いコードワードを人が選択できます。 ${\displaystyle y}$ ${\displaystyle x}$

デコード規則

各コードワードには期待される可能性はありません。受信メッセージに変化する可能性が等しいコードワードが複数存在する可能性があります。このような場合、送信者と受信者は事前に復号規則について合意しておく必要があります。一般的な規則には以下のものがあります。

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

最大尤度復号法

受信ベクトルが与えられた場合、最大尤度復号法は、最大となる符号語を選択する。 ${\displaystyle x\in \mathbb {F} _{2}^{n}}$ ${\displaystyle y\in C}$

${\displaystyle \mathbb {P} (x{\mbox{ received}}\mid y{\mbox{ sent}})}$、

つまり、送信された符号語が与えられた場合に、受信された確率を最大化する符号語です。すべての符号語が等しく送信される確率であれば、この方式は理想的な観測者復号法と同等です。実際、ベイズの定理によれば、 ${\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{ received}})}$ ${\displaystyle x}$ ${\displaystyle \mathbb {P} (y{\mbox{ sent}})}$ ${\displaystyle \mathbb {P} (x{\mbox{ received}}\mid y{\mbox{ sent}})}$ ${\displaystyle y}$ ${\displaystyle \mathbb {P} (y{\mbox{ sent}}\mid x{\mbox{ received}})}$

理想的な観察者デコードと同様に、非一意のデコードについても規則に同意する必要があります。

最大尤度復号問題は整数計画問題としてモデル化することもできる。^[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)^{n-d}\cdot p^{d}\\&{}=(1-p)^{n}\cdot \left({\frac {p}{1-p}}\right)^{d}\\\end{aligned}}}$

これは（pは半分より小さいので）d を最小化することによって最大化されます。

最小距離復号法は、最近傍復号法とも呼ばれます。標準配列を用いることで、補助的に処理したり自動化したりすることができます。最小距離復号法は、以下の条件を満たす場合に有効な復号法です。

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

これらの仮定は、2元対称チャネルを介した伝送においては妥当であるかもしれない。しかし、DVDのような他のメディアでは、ディスク上の1つの傷が隣接する多くのシンボルやコードワードにエラーを引き起こす可能性があるため、妥当ではないかもしれない。

他のデコード方法と同様に、一意でないデコードについては規則に同意する必要があります。

症候群の解読

シンドローム復号法は、ノイズの多い通信路、つまり誤りが発生する通信路において線形符号を復号する非常に効率的な手法です。本質的には、シンドローム復号法は縮小されたルックアップテーブルを用いた最小距離復号法です。これは、符号の線形性によって可能になります。^[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}$

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

しかし、送信中にエラーが1つも発生しなかったという仮定の下では、受信側はさらに縮小されたサイズのテーブルで値を検索することができる。 ${\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 ) は、磁気ディスクまたはテープ ドライブのヘッドからの弱いアナログ信号をデジタル信号に変換する方法です。

ビタビデコーダ

ビタビ復号器は、畳み込み符号に基づく前方誤り訂正符号化されたビットストリームを復号するためにビタビアルゴリズムを使用します。硬判定ビタビ復号器ではハミング距離が、軟判定ビタビ復号器では2乗 ユークリッド距離が、それぞれ指標として使用されます。

最適決定復号アルゴリズム（ODDA）

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

参照

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

参考文献

1. Feldman, Jon; Wainwright, Martin J.; Karger, David R. (2005年3月). 「線形計画法を用いたバイナリ線形符号の復号法」. IEEE Transactions on Information Theory . 51 (3): 954– 972. CiteSeerX  10.1.1.111.6585 . doi :10.1109/TIT.2004.842696. S2CID  3120399.
2. Aji, Srinivas M.; McEliece, Robert J. (2000年3月). 「一般化分配法則」(PDF) . IEEE Transactions on Information Theory . 46 (2): 325– 343. doi :10.1109/18.825794.
3. ボイテルスパッハー、アルブレヒト;ユテ州ローゼンバウム (1998)。射影幾何学。ケンブリッジ大学出版局。 p. 190.ISBN​ 0-521-48277-1。
4. スターン、ジャック (1989). 「小さな重みのコードワードを見つける方法」.符号化理論と応用. コンピュータサイエンス講義ノート. 第388巻.シュプリンガー・フェアラーク. pp.  106– 113. doi :10.1007/BFb0019850. ISBN 978-3-540-51643-9。
5. 太田一夫、ペイ・ディンイー編 (1998).暗号学の進歩 — ASIACRYPT'98 . コンピュータサイエンス講義ノート. 第1514巻. pp.  187– 199. doi :10.1007/3-540-49649-1. ISBN 978-3-540-65109-3. S2CID  37257901。
6. Siamack Ghadimi (2020)、非対称TWRCシステムのための最適決定復号アルゴリズム（ODDA）、Universal Journal of Electrical and Electronic Engineering

さらに読む

• ヒル、レイモンド (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。
• ヴァン・リント、ヤコブス・H. (1992).符号理論入門.大学院数学テキスト(GTM). 第86巻 (第2版).シュプリンガー・フェアラーク. ISBN 978-3-540-54894-2。

Retrieved from "https://en.wikipedia.org/w/index.php?title=Decoding_methods&oldid=1313928558"