復号手法(ふくごうしゅほう、英: Decoding methods)は、符号理論における復号の手法であり、受信したメッセージを所定の符号の符号語の並びに変換する手法である。本項目では、主な復号手法を解説する。これらの手法は2元対称通信路などの通信路上を転送されるメッセージの復号に使われる。 以降の記述において、 C ⊂ F 2 n {\displaystyle C\subset \mathbb {F} _{2}^{n}} は長さ n {\displaystyle n} の符号、 x , y {\displaystyle x,y} は F 2 n {\displaystyle \mathbb {F} _{2}^{n}} の元、 d ( x , y ) {\displaystyle d(x,y)} は x , y {\displaystyle x,y} 間のハミング距離を表す。なお、 C {\displaystyle C} は線型符号とは限らない。 メッセージ x ∈ F 2 n {\displaystyle x\in \mathbb {F} _{2}^{n}} を受信したとき、最適復号(Ideal Observer Decoding)では、 P ( y sent ∣ x received ) {\displaystyle \mathbb {P} (y{\mbox{ sent}}\mid x{\mbox{ received}})} が最大となるような符号語 y ∈ C {\displaystyle y\in C} を選択する。すなわち、メッセージ x {\displaystyle x} の解釈として最適と考えられる符号語 y {\displaystyle y} を選択する。 各符号語の確率はユニークではない。受信メッセージの解釈として複数の符号語が同じ確率となる場合もある。その場合、送信側と受信側の間で復号に関する規定を定めておく。一般的な規定は次のどちらかである。 メッセージ x ∈ F 2 n {\displaystyle x\in \mathbb {F} _{2}^{n}} を受信したとき、最尤復号(Maximum Likelihood Decoding)では、 P ( x received ∣ y sent ) {\displaystyle \mathbb {P} (x{\mbox{ received}}\mid y{\mbox{ sent}})} が最大となるような符号語 y ∈ C {\displaystyle y\in C} を選択する。すなわち、 x {\displaystyle x} を受信したときの条件付き確率の最も高い符号語 y {\displaystyle y} を選択する。なお、全ての符号語の出現確率が同じである場合、これは「最適復号」と等価である。 P ( x received ∣ y sent ) = P ( x received , y sent ) P ( y sent ) = P ( y sent ∣ x received ) ⋅ P ( x received ) P ( y sent ) ∝ P ( y sent ∣ x received ) {\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}})}}\\&{}\propto \mathbb {P} (y{\mbox{ sent}}\mid x{\mbox{ received}})\end{aligned}}} 最終行では x received {\displaystyle x{\mbox{ received}}} が固定されていることと、 P ( y sent ) {\displaystyle \mathbb {P} (y{\mbox{ sent}})} が y sent {\displaystyle y{\mbox{ sent}}} 依存性を持たないことを使っている。なお「最適復号」と同様、確率が同じ符号語がある場合の規定をしておく必要がある。 メッセージ x ∈ F 2 n {\displaystyle x\in \mathbb {F} _{2}^{n}} を受信したとき、最小距離復号(Minimum Distance Decoding)ではハミング距離 d ( x , y ) = # { i : x i ≠ y i } {\displaystyle d(x,y)=\#\{i:x_{i}\not =y_{i}\}} が最小となる符号語 y ∈ C {\displaystyle y\in C} を選択する。すなわち、なるべく x {\displaystyle x} に近い符号語 y {\displaystyle y} を選択する。 (履歴記憶のない)離散通信路における誤り発生確率 p {\displaystyle p} が2分の1未満の場合、「最小距離復号」と「最尤復号」は同じである。なぜなら d ( x , y ) = d {\displaystyle d(x,y)=d\,} としたとき、 P ( y received ∣ x sent ) = ( 1 − p ) n − d ⋅ p d = ( 1 − p ) n ⋅ ( p 1 − p ) 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 が2分の1未満なので)、d を最小化することで値が最大になる。 最小距離復号は「最近傍復号(Nearest Neighbour Decoding)」とも呼ぶ。標準配列 これらの条件は2元対称通信路では妥当である。しかし例えばDVDの場合、ある箇所に傷が付くと、その周辺のシンボルや符号語で誤りが発生する確率が高くなり、誤り同士が相互に関係し、かつシンボルの位置が関係してくる。 他の復号手法と同様、復号が一意に定まらない場合の規定を予め決めておく必要がある。 長さ n {\displaystyle n} で最小ハミング距離 d {\displaystyle d} の符号 C ⊂ F 2 n {\displaystyle C\subset \mathbb {F} _{2}^{n}} は、最小距離復号により t = ⌊ d − 1 2 ⌋ {\displaystyle t=\left\lfloor {\frac {d-1}{2}}\right\rfloor } 個以下の通信路で発生した誤りを訂正できる。シンドローム復号(Syndrome Decoding)は、線型符号のために最小距離復号を高効率に行う復号手法である。シンドローム復号は符号の線型性を利用して小さなルックアップテーブルを使うことで復号を可能にする。以下ではその方法を説明する。 符号語 y ∈ F 2 n {\displaystyle y\in \mathbb {F} _{2}^{n}} を通信する際、誤りパターン e ∈ F 2 n {\displaystyle e\in \mathbb {F} _{2}^{n}} が発生したとする。すると受信されるメッセージは x = y + e {\displaystyle x=y+e} となる。
本項目における記号
最適復号
復号における規定
符号語の再送を要求する。
最も確率の高い符号語群から無作為に1つを選択する。
最尤復号
最小距離復号
誤り発生確率 p が、シンボルの位置とは無関係である。
誤り同士も無関係に独立して生じる(メッセージ内のある位置で誤りが発生したという事実が、他の位置での誤り発生に影響しない)。
シンドローム復号
Size:18 KB
出典: フリー百科事典『ウィキペディア(Wikipedia)』
担当:undef