復号手法

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動: 案内検索

復号手法(ふくごうしゅほう、: Decoding methods)は、符号理論における復号の手法であり、受信したメッセージを所定の符号符号語の並びに変換する手法である。本項目では、主な復号手法を解説する。これらの手法は2元対称通信路などの通信路上を転送されるメッセージの復号に使われる。

本項目における記号[編集]

以降の記述において、C \subset \mathbb{F}_2^n は長さ n符号x,y\mathbb{F}_2^n の元、d(x,y)x,y 間のハミング距離を表す。なお、C線型符号とは限らない。

最適復号[編集]

メッセージ x \in \mathbb{F}_2^n を受信したとき、最適復号(Ideal Observer Decoding)では、

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

が最大となるような符号語 y \in C を選択する。すなわち、メッセージ x の解釈として最適と考えられる符号語 y を選択する。

復号における規定[編集]

各符号語の確率はユニークではない。受信メッセージの解釈として複数の符号語が同じ確率となる場合もある。その場合、送信側と受信側の間で復号に関する規定を定めておく。一般的な規定は次のどちらかである。

  1. 符号語の再送を要求する。
  2. 最も確率の高い符号語群から無作為に1つを選択する。

最尤復号[編集]

メッセージ x \in \mathbb{F}_2^n を受信したとき、最尤復号(Maximum Likelihood Decoding)では、

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

が最大となるような符号語 y \in C を選択する。すなわち、x を受信したときの条件付き確率の最も高い符号語 y を選択する。なお、全ての符号語の出現確率が同じである場合、これは「最適復号」と等価である。


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

最終行ではx \mbox{ received} が固定されていることと、 \mathbb{P}(y \mbox{ sent}) y \mbox{ sent} 依存性を持たないことを使っている。なお「最適復号」と同様、確率が同じ符号語がある場合の規定をしておく必要がある。

最小距離復号[編集]

メッセージ x \in \mathbb{F}_2^n を受信したとき、最小距離復号(Minimum Distance Decoding)ではハミング距離

d(x,y) = \# \{i : x_i \not = y_i \}

が最小となる符号語 y \in C を選択する。すなわち、なるべく x に近い符号語 y を選択する。

(履歴記憶のない)離散通信路における誤り発生確率 p が2分の1未満の場合、「最小距離復号」と「最尤復号」は同じである。なぜなら

d(x,y) = d\,

としたとき、


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

となり(p が2分の1未満なので)、d を最小化することで値が最大になる。

最小距離復号は「最近傍復号(Nearest Neighbour Decoding)」とも呼ぶ。標準配列を使うと容易または自動的に行える。最小距離復号は、以下の条件が成り立つ場合に使いやすい。

  1. 誤り発生確率 p が、シンボルの位置とは無関係である。
  2. 誤り同士も無関係に独立して生じる(メッセージ内のある位置で誤りが発生したという事実が、他の位置での誤り発生に影響しない)。

これらの条件は2元対称通信路では妥当である。しかし例えばDVDの場合、ある箇所に傷が付くと、その周辺のシンボルや符号語で誤りが発生する確率が高くなり、誤り同士が相互に関係し、かつシンボルの位置が関係してくる。

他の復号手法と同様、復号が一意に定まらない場合の規定を予め決めておく必要がある。

シンドローム復号[編集]

シンドローム復号(Syndrome Decoding)は、ノイズのある(誤りが発生する)通信路での線型符号の高効率な復号手法である。シンドローム復号は基本的には「最小距離復号」だが、小さな参照テーブルを使う。参照テーブルは符号の線型性を利用して小さくできる。

長さ n で最小ハミング距離 d の線型符号 C\subset \mathbb{F}_2^nパリティチェック行列H とする。すると、C は明らかに

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

までの通信路で発生した誤りを訂正できる(t 個以下の誤りであれば、最小距離復号で問題なく復号可能である)。

符号語 x \in \mathbb{F}_2^n が送られ、誤りパターン e \in \mathbb{F}_2^n が発生したとする。すると受信されるメッセージは z=x+e となる。通常の最小距離復号では、ベクトル z を大きさ |C| のテーブル上で検索し、最もよく一致するものを選ぶ。すなわち、全ての y \in C について

d(c,z) \leq d(y,z)

となる c \in C を選択する(ユニークとは限らない)。シンドローム復号では、パリティチェック行列の持つ、全ての x \in C について

Hx = 0

となる性質を利用する。受信した z=x+e のシンドロームは次のように定義される。

Hz = H(x+e) =Hx + He = 0 + He = He

t 個を越える誤りが発生しない前提で、受信側にサイズ


\begin{matrix}
\sum_{i=0}^t \binom{n}{i} < |C| \\
\end{matrix}

の(2元符号の)テーブルを用意しておき、全ての誤りパターン e \in \mathbb{F}_2^n について値 He を事前に求めておく。そこから値 He を参照して誤りパターン e が得られるので、x は以下のように簡単に求められる。

x = z - e\quad

x=y であるときのみ

Hx = Hy\quad

となるので、この方法で常に一意な復号が得られる(ただし、正確とは限らない)。これは、パリティチェック行列 H が双対符号 C^\perp生成行列になっているためであり、その階数はフルである(正方行列)。

関連項目[編集]

参考文献[編集]

  • Hill, Raymond. (1988). A First Course In Coding Theory, New York: Oxford University Press.