復号手法

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

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

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

以降の記述において、 は長さ 符号 の元、 間のハミング距離を表す。なお、線型符号とは限らない。

最適復号[編集]

メッセージ を受信したとき、最適復号(Ideal Observer Decoding)では、

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

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

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

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

最尤復号[編集]

メッセージ を受信したとき、最尤復号(Maximum Likelihood Decoding)では、

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

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

最小距離復号[編集]

メッセージ を受信したとき、最小距離復号(Minimum Distance Decoding)ではハミング距離

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

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

としたとき、

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

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

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

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

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

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

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

長さ で最小ハミング距離 の線型符号 パリティ検査行列 とする。すると、 は明らかに

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

符号語 が送られ、誤りパターン が発生したとする。すると受信されるメッセージは となる。通常の最小距離復号では、ベクトル を大きさ のテーブル上で検索し、最もよく一致するものを選ぶ。すなわち、全ての について

となる を選択する(ユニークとは限らない)。シンドローム復号では、パリティ検査行列の持つ、全ての について

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

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

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

であるときのみ

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

関連項目[編集]

参考文献[編集]

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