復号手法
復号手法（ふくごうしゅほう、英: Decoding methods）は、符号理論における復号の手法であり、受信したメッセージを所定の符号の符号語の並びに変換する手法である。本項目では、主な復号手法を解説する。これらの手法は2元対称通信路などの通信路上を転送されるメッセージの復号に使われる。
本項目における記号
以降の記述において、[math]C \subset \mathbb{F}_2^n[/math] は長さ [math]n[/math] の符号、[math]x,y[/math] は [math]\mathbb{F}_2^n[/math] の元、[math]d(x,y)[/math] は [math]x,y[/math] 間のハミング距離を表す。なお、[math]C[/math] は線型符号とは限らない。
最適復号
メッセージ [math]x \in \mathbb{F}_2^n[/math] を受信したとき、最適復号（Ideal Observer Decoding）では、
- [math]\mathbb{P}(y \mbox{ sent} \mid x \mbox{ received})[/math]
が最大となるような符号語 [math]y \in C[/math] を選択する。すなわち、メッセージ [math]x[/math] の解釈として最適と考えられる符号語 [math]y[/math] を選択する。
復号における規定
各符号語の確率はユニークではない。受信メッセージの解釈として複数の符号語が同じ確率となる場合もある。その場合、送信側と受信側の間で復号に関する規定を定めておく。一般的な規定は次のどちらかである。
- 符号語の再送を要求する。
- 最も確率の高い符号語群から無作為に1つを選択する。
最尤復号
メッセージ [math]x \in \mathbb{F}_2^n[/math] を受信したとき、最尤復号（Maximum Likelihood Decoding）では、
- [math]\mathbb{P}(x \mbox{ received} \mid y \mbox{ sent})[/math]
が最大となるような符号語 [math]y \in C[/math] を選択する。すなわち、[math]x[/math] を受信したときの条件付き確率の最も高い符号語 [math]y[/math] を選択する。なお、全ての符号語の出現確率が同じである場合、これは「最適復号」と等価である。
- [math] \begin{align} \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{align} [/math]
最終行では[math]x \mbox{ received}[/math] が固定されていることと、 [math]\mathbb{P}(y \mbox{ sent}) [/math]が[math]y \mbox{ sent}[/math] 依存性を持たないことを使っている。なお「最適復号」と同様、確率が同じ符号語がある場合の規定をしておく必要がある。
最小距離復号
メッセージ [math]x \in \mathbb{F}_2^n[/math] を受信したとき、最小距離復号（Minimum Distance Decoding）ではハミング距離
- [math]d(x,y) = \# \{i : x_i \not = y_i \}[/math]
が最小となる符号語 [math]y \in C[/math] を選択する。すなわち、なるべく [math]x[/math] に近い符号語 [math]y[/math] を選択する。
（履歴記憶のない）離散通信路における誤り発生確率 [math]p[/math] が2分の1未満の場合、「最小距離復号」と「最尤復号」は同じである。なぜなら
- [math]d(x,y) = d\,[/math]
としたとき、
- [math] \begin{align} \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{align} [/math]
となり（p が2分の1未満なので）、d を最小化することで値が最大になる。
最小距離復号は「最近傍復号（Nearest Neighbour Decoding）」とも呼ぶ。標準配列を使うと容易または自動的に行える。最小距離復号は、以下の条件が成り立つ場合に使いやすい。
- 誤り発生確率 p が、シンボルの位置とは無関係である。
- 誤り同士も無関係に独立して生じる（メッセージ内のある位置で誤りが発生したという事実が、他の位置での誤り発生に影響しない）。
これらの条件は2元対称通信路では妥当である。しかし例えばDVDの場合、ある箇所に傷が付くと、その周辺のシンボルや符号語で誤りが発生する確率が高くなり、誤り同士が相互に関係し、かつシンボルの位置が関係してくる。
他の復号手法と同様、復号が一意に定まらない場合の規定を予め決めておく必要がある。
シンドローム復号
シンドローム復号（Syndrome Decoding）は、ノイズのある（誤りが発生する）通信路での線型符号の高効率な復号手法である。シンドローム復号は基本的には「最小距離復号」だが、小さな参照テーブルを使う。参照テーブルは符号の線型性を利用して小さくできる。
長さ [math]n[/math] で最小ハミング距離 [math]d[/math] の線型符号 [math]C\subset \mathbb{F}_2^n[/math] のパリティ検査行列を [math]H[/math] とする。すると、[math]C[/math] は明らかに
- [math]t = \left\lfloor\frac{d-1}{2}\right\rfloor[/math]
までの通信路で発生した誤りを訂正できる（[math]t[/math] 個以下の誤りであれば、最小距離復号で問題なく復号可能である）。
符号語 [math]x \in \mathbb{F}_2^n[/math] が送られ、誤りパターン [math]e \in \mathbb{F}_2^n[/math] が発生したとする。すると受信されるメッセージは [math]z=x+e[/math] となる。通常の最小距離復号では、ベクトル [math]z[/math] を大きさ [math]|C|[/math] のテーブル上で検索し、最もよく一致するものを選ぶ。すなわち、全ての [math]y \in C[/math] について
- [math]d(c,z) \leq d(y,z)[/math]
となる [math]c \in C[/math] を選択する（ユニークとは限らない）。シンドローム復号では、パリティ検査行列の持つ、全ての [math]x \in C[/math] について
- [math]Hx = 0[/math]
となる性質を利用する。受信した [math]z=x+e[/math] のシンドロームは次のように定義される。
- [math]Hz = H(x+e) =Hx + He = 0 + He = He[/math]
[math]t[/math] 個を越える誤りが発生しない前提で、受信側にサイズ
- [math] \begin{matrix} \sum_{i=0}^t \binom{n}{i} \lt |C| \\ \end{matrix} [/math]
の（2元符号の）テーブルを用意しておき、全ての誤りパターン [math]e \in \mathbb{F}_2^n[/math] について値 [math]He[/math] を事前に求めておく。そこから値 [math]He[/math] を参照して誤りパターン [math]e[/math] が得られるので、[math]x[/math] は以下のように簡単に求められる。
- [math]x = z - e\quad[/math]
[math]x=y[/math] であるときのみ
- [math]Hx = Hy\quad[/math]
となるので、この方法で常に一意な復号が得られる（ただし、正確とは限らない）。これは、パリティ検査行列 [math]H[/math] が双対符号 [math]C^\perp[/math] の生成行列になっているためであり、その階数はフルである（正方行列）。
関連項目
参考文献
- Hill, Raymond. (1988). A First Course In Coding Theory, New York: Oxford University Press.