ここから先の議論の大まかな流れを説明する. 最終的にいいたいのは後で説明する シンドローム復号が最尤復号であることだが,直接いうのが難しいので 中間にスタンダードアレイを使った復号法をはさむ.スタンダードアレイ を使った復号法が最尤復号であることは比較的簡単に示せるので先に これを示し,シンドローム復号がスタンダードアレイを使った復号法と 同じものを求めることができることを示し,シンドローム復号が 最尤復号であることを示す.つまり,これから説明する スタンダードアレイを使った復号法は証明のために導入したもので, 実際に現実に使おうとしているわけではないことに注意する.
ここからスタンダードアレイによる復号法の説明を始める. これを理解するためには受信語を誤りベクトルを使って 表現することが重要である.受信語が $\vec{y}$ であるとして, それをある符号語 $\vec{x}$ とベクトル $\vec{e}$ の和である と考える($\vec{y} = \vec{x} + \vec{e}$).これは $\vec{x}$ を送信して $\vec{e}$ の誤りが起こって $\vec{y}$ が受信されたと考えることができる. このとき $\vec{e}$ は誤りベクトルである.
例 8.1
例 7.1
の符号を例にとると受信語 $\vec{y} = 0101$
だとすると $\vec{x} = 0111, \vec{e} = 0010$ や
$\vec{x} = 1101, \vec{e} = 1000$ などの
「符号語」+「誤り」の形でかける.
(例終わり)
全てのコセットの和は全空間 $V$ だから,どんな 受信語 $\vec{y}$ であってもそれが含まれるコセットがある. そしてそのコセットは符号語 $\vec{x}$ と誤り $\vec{e}$ の和の形 $\vec{y} = \vec{x} + \vec{e}$ に書くことができる 全ての $\vec{e}$ からなる集合である.理由は $\vec{y}$ が含まれるコセットは $\vec{y} + C$ であり, $\vec{y}$ に各符号語 $\vec{x}$ を加えた $\vec{y}+\vec{x}$ からなる集合である. 2元符号では加算と減算は同一なのでこのコセットは 各符号語 $\vec{x}$ についての $\vec{y}-\vec{x}$ からなる集合で,すなわち誤りベクトルの集合であるためである.
例 8.2
例 7.1 の例の全てのコセットは
\begin{eqnarray}
\{0011, 1001, 0100, 1110\}\nonumber \\
\{0000, 1010, 0111, 1101\}\nonumber \\
\{0001, 1011, 0110, 1100\}\nonumber \\
\{0010, 1000, 0101, 1111\}\nonumber \\
\end{eqnarray}
であった.
受信語 $\vec{y} = 0101$ とすると $\vec{y}$
が含まれるコセットは $\{0010, 1000, 0101, 1111\}$ である.
「受信語$\vec{y}$」=「符号語$\vec{x}$」+「誤りベクトル$\vec{e}$」
の形で書くと
\begin{eqnarray}
0101 = 0111 + 0010\nonumber \\
0101 = 1101 + 1000\nonumber \\
0101 = 0000 + 0101\nonumber \\
0101 = 1010 + 1111\nonumber
\end{eqnarray}
となり,$0101$ を受信したときの全ての可能性のある誤りベクトル
$\vec{e}$ の集合になっていることがわかる.
(例終わり)
ここまででわかったことは,$\vec{y}$ を受信したとき, 可能性のある誤りベクトルは $\vec{y}$ が含まれるコセット の要素だということである.誤りベクトルとして可能性が あるのはコセットの要素全てであるが,その中で重みの最も 小さいものを誤りベクトル $\vec{e}$ として選べば最尤復号になる. 重み最小のものが複数あればどれかを選べば最尤復号になる. 誤りベクトルが最小になる符号語 $\vec{x} = \vec{y} - \vec{e}$ に復号すれば最尤復号になることは 第 5 回授業で説明した.
例 8.3
受信語 $\vec{y} = 0101$ のとき,$\vec{y}$
が含まれるコセットは $\{0010, 1000, 0101, 1111\}$ である.
このうち重み最小なものは $0010$ と $1000$ の 2 つである.
どちらかを誤りベクトル $\vec{e}$ として選べば最尤復号になる.
$0010$ を選んだ場合は $0101-0010=0111$,
$1000$ を選んだ場合は $0101-1000=1101$
に復号する.どちらも符号語であって,誤りベクトルが最小の
重み(重み $1$)のものである.
(例終わり)
コセットの中で重み最小のものを $\vec{e}$ に選ぶわけだから, あらかじめコセットの中で重み最小のものを選んでおくことを考える. コセットの中で重みが最小のものをそのコセットの コセットリーダという.重み最小のものが 複数あればどちらをコセットリーダとしてもいい.
例 8.4
例 7.1 のコセットは 4 つで,コセットリーダーと
並べて書くと,
$\{0011, 1001, 0100, 1110\}$,コセットリーダーは $0100$
$\{0000, 1010, 0111, 1101\}$,コセットリーダーは $0000$
$\{0001, 1011, 0110, 1100\}$,コセットリーダーは $0001$
$\{0010, 1000, 0101, 1111\}$,コセットリーダーは $1000$ ($0010$も可)
である.
(例終わり)
ここまでの説明により最尤復号の手続きを以下のように 行えることがわかる.
この手続きはスタンダードアレイを使うことで 明確化できる.スタンダードアレイは符号 $C$ の各コセットを 行とする表で,以下のように並べられている.
例 8.5
例 8.4 にあるコセットの一覧をスタンダードアレイの規則で並べたものが
以下の図 表8.1 である.
表 8.1 $C$ のスタンダードアレイ
コセット リーダ |
||||
---|---|---|---|---|
符号 | 0000 | 1010 | 0111 | 1101 |
他のコセット | 1000 | 0010 | 1111 | 0101 |
0100 | 1110 | 0011 | 1001 | |
0001 | 1011 | 0110 | 1100 |
スタンダードアレイの具体的な作り方を符号 $C$ を例として説明する.
第 1 行 (0000, 1010, 0111, 1101) は符号語の集合で, 第 1 行にゼロベクトルを置いている.他の符号語はどの順序でもよい.
第 2 行を作るにはコセットリーダとして何を選べばいいか を最初に考える.既にに出ているベクトルは選んでも 既に出ているコセットになってしまうのでまだ出ていない ベクトルを選ぶ必要がある.さらにコセットリーダーは コセットの中で重み最小のベクトルだから,まだ出ていない 重み 1 のベクトルの一つ,1000 をコセットリーダーに選び, 第 1 列に置く.第 2 行の残りの列はコセットリーダーと その行の一番上にある符号語の和のベクトルを置く. これでコセットが 2 つ出た状態である.
残りの行も同様に,まだ出てきていない重み 1 のベクトル をコセットリーダーとして選んで第 1 列に置き, 残りの列にはコセットリーダーとその列の一番上にある 符号語の和のベクトルを置く.
この例の符号 $C$ の場合は重み 1 のコセットリーダーだけで 全空間 $V$ のベクトル全てが出現するが,そうでない符号の場合, 重み 2, 重み 3 のコセットリーダーを順に追加し, $V$ の要素全てが出るまで続ける.
(例終わり)
スタンダードアレイを使った復号手続きは以下の通りである.
この復号法では $\vec{y}$ が含まれているコセットの コセットリーダーを誤りベクトル $\vec{e}$ としていることになる. コセットリーダーはそのコセット(可能な誤りベクトル) のうち重み最小のものなので,重み最小の誤りベクトルを 選ぶことであり,最も受信語に近い符号語を 選ぶことであるから最尤復号であるといえる.
\[ G =\left( \begin{array}{cccc} 1 & 0 & 1 & 1\\ 0 & 1 & 0 & 1 \end{array} \right) \] を生成行列とする符号のスタンダードアレイを書け.
授業の6日後までにメールで提出せよ. メールの件名(サブジェクト)は CT08 とせよ.