復号手法

復号手法について

復号手法とは、符号理論において、通信路を介して受信したメッセージを、送信された可能性のある元の符号語の並びへと変換する技術の総称です。本稿では、代表的な復号手法について詳しく解説します。これらの手法は、特に2元対称通信路のような、ノイズやエラーが発生しやすい通信環境下でのメッセージ復号に不可欠です。

記号の定義

本稿では、以下の記号を定義して説明を進めます。

$C \subset \mathbb{F}_{2}^{n}$: 長さ$n$の符号
$x, y$: $\mathbb{F}_{2}^{n}$の要素
$d(x, y)$: $x$と$y$間のハミング距離

ここで、$C$は必ずしも線形符号である必要はありません。

最適復号

最適復号（Ideal Observer Decoding）は、受信したメッセージ$x \in \mathbb{F}_{2}^{n}$に対し、条件付き確率

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

を最大にする符号語 $y \in C$ を選択する手法です。これは、受信したメッセージ $x$ の解釈として、最も尤もらしい符号語 $y$ を選ぶという考え方に基づいています。

復号における規定

復号の際、複数の符号語が同じ確率を持つ場合があります。このような場合、送信側と受信側であらかじめ復号に関する規定を定めておく必要があります。一般的な規定としては、以下の2つが挙げられます。

1. 符号語の再送を要求する
2. 最も確率の高い符号語群からランダムに1つを選択する

最尤復号

最尤復号（Maximum Likelihood Decoding）は、受信したメッセージ$x \in \mathbb{F}_{2}^{n}$に対して、条件付き確率

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

を最大にする符号語 $y \in C$ を選択する手法です。これは、受信したメッセージ $x$ を受け取ったという条件の下で、最も起こりうる符号語 $y$ を選択するという考え方です。

全ての符号語の出現確率が同じである場合、最尤復号は最適復号と等価になります。

最尤復号と最適復号の関係

以下の式が示すように、最尤復号は最適復号と密接な関係があります。

$$\begin{aligned} \mathbb{P}(x\text{ received} \mid y\text{ sent}) &= \frac{\mathbb{P}(x\text{ received}, y\text{ sent})}{\mathbb{P}(y\text{ sent})} \\ &= \mathbb{P}(y\text{ sent} \mid x\text{ received}) \cdot \frac{\mathbb{P}(x\text{ received})}{\mathbb{P}(y\text{ sent})} \\ &\propto \mathbb{P}(y\text{ sent} \mid x\text{ received}) \end{aligned}$$

最終行では、$x\text{ received}$ が固定されていることと、$\mathbb{P}(y\text{ sent})$ が $y\text{ sent}$ に依存しないことを利用しています。最適復号と同様に、確率が同じ符号語がある場合には、事前に規定を決めておく必要があります。

最小距離復号

最小距離復号（Minimum Distance Decoding）は、受信したメッセージ$x \in \mathbb{F}_{2}^{n}$に対し、ハミング距離

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

が最小となる符号語 $y \in C$ を選択する手法です。これは、受信したメッセージ $x$ に最も近い符号語 $y$ を選ぶという考え方に基づいています。

最小距離復号と最尤復号の関係

離散通信路において誤り発生確率 $p$ が1/2未満の場合、最小距離復号は最尤復号と等価です。なぜなら、$d(x, y) = d$ とした場合、

$$\begin{aligned} \mathbb{P}(y\text{ received} \mid x\text{ sent}) &= (1-p)^{n-d} \cdot p^d \\ &= (1-p)^n \cdot \left(\frac{p}{1-p}\right)^d \end{aligned}$$

となり、$p < 1/2$ の条件下では、$d$ を最小化することでこの値が最大となるからです。

最小距離復号は、「最近傍復号（Nearest Neighbour Decoding）」とも呼ばれます。標準配列を用いることで、容易または自動的に実行できます。

最小距離復号の適用条件

最小距離復号は、以下の条件が満たされる場合に有効です。

誤り発生確率 $p$ が、シンボルの位置とは無関係であること
誤りが互いに独立して発生すること（ある位置での誤り発生が他の位置での誤り発生に影響しないこと）

これらの条件は、2元対称通信路においては妥当です。しかし、DVDのように、ある箇所に傷が付くと周辺のシンボルや符号語で誤りが発生する確率が高くなるような状況では、これらの条件は成り立ちません。

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

シンドローム復号

長さ $n$ で最小ハミング距離 $d$ の符号 $C \subset \mathbb{F}_{2}^{n}$ は、最小距離復号により、$t = \lfloor \frac{d-1}{2} \rfloor$ 個以下の通信路で発生した誤りを訂正できます。シンドローム復号（Syndrome Decoding）は、線形符号に対して最小距離復号を効率的に行う手法です。シンドローム復号は、符号の線形性を利用し、小さなルックアップテーブルを使用することで復号を実現します。

シンドローム復号の仕組み

符号語 $y \in \mathbb{F}_{2}^{n}$ を送信する際、誤りパターン $e \in \mathbb{F}_{2}^{n}$ が発生すると、受信されるメッセージは $x = y + e$ となります。

シンドローム復号では、与えられた符号のパリティ検査行列 $H \in \mathbb{F}_{2}^{(n-k) \times n}$ を用いて、受信したメッセージ $x$ のシンドローム $Hx$ を計算します。ここで、$k$ は符号語のなす部分空間の次元です。パリティ検査行列 $H$ は、全ての $x \in C$ について $Hx = 0$ となる性質を持っています。

したがって、

$$Hx = H(y + e) = Hy + He = 0 + He = He$$

が成立します。

$t$ 個を超える誤りが発生しないという前提の下で、全ての誤りパターン $e \in \mathbb{F}_{2}^{n}$ について $He$ の値を事前に計算し、ルックアップテーブルを作成しておけば、$x$ のシンドロームから誤りパターン $e$ を特定することができます。誤りパターン $e$ が特定できれば、送信されたメッセージは $x = z - e$ の関係から容易に求められます。

MATLABには、シンドローム復号に使用するルックアップテーブルを生成するための関数 `syndtable` が用意されています。

シンドローム復号の効率性

全ての符号語に対してハミング距離を直接計算する場合、$|C| = 2^k$ 個のハミング距離を計算する必要があります。一方、シンドローム復号で使用するルックアップテーブルのサイズは、

$$\sum_{i=0}^{\left\lfloor \frac{d-1}{2} \right\rfloor} {n \choose i}$$

となります。これにより、シンドローム復号は効率的な復号処理を実現します。

関連項目

誤り検出訂正

参考文献

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

もう一度検索