シンドローム復号

ウィキペディア

復号手法

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2023/05/24 02:34 UTC 版)

復号手法（ふくごうしゅほう、英: 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{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{\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{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）」とも呼ぶ。標準配列を使うと容易または自動的に行える。最小距離復号は、以下の条件が成り立つ場合に使いやすい。

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

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

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

シンドローム復号

長さ $n$ で最小ハミング距離 $d$ の符号 $C\subset \mathbb {F} _{2}^{n}$は、最小距離復号により $t=\left\lfloor {\frac {d-1}{2}}\right\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が用意されている

MATLABによる例：

H = hammgen(3) % Hはパリティ検査行列
%% H = [ 1 0 0 1 1 0 1;  
%%       0 1 0 1 1 1 0;
%%       0 0 1 0 1 1 1]
G = gen2par(H) % Gは生成行列
%% G = [ 1 1 0 1 0 0 0;
%%       0 1 1 0 1 0 0;
%%       1 1 1 0 0 1 0;
%%       0 0 1 0 0 0 1]
t = syndtable(H) % tはシンドローム復号のためのルックアップテーブルである
%% t = [ 0 0 0 0 0 0 0   %1行目は He = [0 0 0] に対応する e
%%       0 0 1 0 0 0 0   %2行目は He = [0 0 1] に対応する e
%%       0 1 0 0 0 0 0   %3行目は He = [0 1 0] に対応する e
%%       0 0 0 0 1 0 0   %4行目は He = [0 1 1] に対応する e
%%       1 0 0 0 0 0 0                    .
%%       0 0 0 0 0 0 1                    .
%%       0 0 0 1 0 0 0                    .
%%       0 0 0 0 0 1 0 ] %8行目は He = [1 1 1] に対応する e
y = mod([0 1 0 1] * G, 2) % yは送信するメッセージ
%% y = [1 1 0 0 1 0 1] 
e = [0 0 0 1 0 0 0]; x = mod (y + e, 2) % xは受信するメッセージ
%% x = [1 1 0 1 1 0 1]
Hx = mod(parmat2 * x',2)'
%%シンドロームを計算 Hx = [1 1 0] →7行目を'ルックアップ'するとeがわかる →x-eでyを求める
y_decoded = mod(x + t(7,:), 2)
%% y_decoded = [1 1 0 0 1 0 1]

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

$\sum _{i=0}^{\left\lfloor {\frac {d-1}{2}}\right\rfloor }{\binom {n}{i}}$

となる。

関連項目

• 誤り検出訂正

参考文献

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

ウィキペディア小見出し辞書

シンドローム復号

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/02/25 07:36 UTC 版)

「線型符号」の記事における「シンドローム復号」の解説

(n, k) 線型符号を C 、 そのパリティ検査行列を H とする。受信語 y ∈ Fn に対して yHt をシンドロームという。剰余空間 Fn/C の完全代表系 {v1, …, vqn − k} は各 vi が剰余類 vi + C のなかで最小の重みをもつとき、コセット・リーダという。このとき受信語 y ∈ Fn は yHt = vHt となるコセット・リーダ v をとると、符号語 y − v ∈ C に復号される。これをシンドローム復号という。