下記の検査行列\(\boldsymbol{H}\)を考える。次の問いに答えよ。
\begin{aligned}\boldsymbol{H}=\begin{pmatrix} 1 & 0 & 1 & 1 & 1 & 0 & 0 \\ 1 & 1 & 1 & 0 & 0 & 1 & 0 \\ 0 & 1 & 1 & 1 & 0 & 0 & 1 \end{pmatrix}\end{aligned}
(1)生成行列\(\boldsymbol{G}\)を求めよ。
(2)\(\boldsymbol{G}\)により生成する符号語を全て求めよ。
(3)[1 1 1 1 1 1 0]を受信したときの誤り訂正を実施せよ。
生成行列とは
情報ビットから符号を生成するための行列です。
大前提として、本記事では情報理論の内、符号の誤りを検出する方法の一つを紹介します。
符号とは、情報を表す情報ビットと検査部分を表す検査ビットで分かれています。
検査行列を活用し、誤りを訂正する方法もありますが、本記事では生成行列から誤りを確認する方法を紹介します。
入力符号に生成行列を積算すると、取り得る出力を網羅的に入手できます。取り得る出力どれにも該当しない出力を検出する=誤りであることが分かる大方針の元、説明していきます。
生成行列の求め方
手順1：検査行列\(\boldsymbol{H}\)を成分分解する
下記のように分解できます。
\begin{aligned}\boldsymbol{H}=[\boldsymbol{P^{t}}\boldsymbol{I}]\end{aligned}
\(\boldsymbol{P}\)は情報・検査ビット関連行列と言います。検査行列から生成行列を求める。またはその逆を行うために必ず出てくる行列です。キーになりますので覚えておきましょう。
検査行列は正方行列ではなく、列の数が行の数より多い行列です。
そのため、行の個数分を単位行列\(I\)で表しても、単位行列に属さない列が出てきます。その分を情報・検査ビット関連行列で表せば良いです。
手順2：\(\boldsymbol{P^{t}}\)を転置する
生成行列\(\boldsymbol{G}\)は、下記のように表すことができます。
\begin{aligned}\boldsymbol{G}=[\boldsymbol{I}\boldsymbol{P}]\end{aligned}
手順1で求めた情報・検査ビット関連行列(転置)をもう一度転置し、行の成分の数だけ単位行列を追加します。
生成する符号の組み合わせを生成行列を用いて求める
入力する符号ベクトルを\(\boldsymbol{c}\)とすれば、下記の計算で生成する符号の候補を求めることができます。
\begin{aligned}\boldsymbol{c}G\end{aligned}
求め方の例
例)3行1列ベクトル \(\boldsymbol{c}=(c_{0},c_{1},c_{2})\)と
生成行列\(\boldsymbol{G}=\begin{pmatrix} 1 & 0 & 0 & 0 & 1 \\ 0 & 1 & 0 & 1 & 1 \\ 0 & 0 & 1 & 1 & 1 \end{pmatrix}\)を考える。
このとき、(4)式を計算すると
\begin{aligned}(c_{0},c_{1},c_{2},c_{1} \oplus c_{2},c_{0} \oplus c_{1} \oplus c_{2})\end{aligned}になる。
\(c_{0}~c_{2}\)は0,1しか取らないのだから、\(2^{3}=8\)通りの入力に対し(5)式は下記の出力しか取りえないです。
| \(c_{0}\) | \(c_{1}\) | \(c_{2}\) | \(c_{1}\oplus c_{2}\) | \(c_{0}\oplus c_{1}\oplus c_{2}\) |
| 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 | 1 |
| 0 | 1 | 0 | 1 | 1 |
| 0 | 1 | 1 | 0 | 0 |
| 1 | 0 | 0 | 0 | 0 |
| 1 | 0 | 1 | 1 | 0 |
| 1 | 1 | 0 | 1 | 0 |
| 1 | 1 | 1 | 0 | 1 |
もし、上記の出力以外が出てきたら、それは誤りであることが分かります。
注意点
本問は線形符号であることが前提です。そのため、\(c_{i}\)の和は排他的論理和で表すことが必要です。
線形関数についての詳しい記事は、こちらで説明しています。
解答例
(1)生成行列の求め方
行の個数は3つのため、単位行列は3*3成分である。
\(\boldsymbol{H}\)は(7,3)成分のため、後半の5列目~7列目が単位行列成分
一方で、前半の1~4列目の部分は情報・検査ビット関連行列成分。
(2)式より
\begin{aligned}\boldsymbol{P^{t}}=\begin{pmatrix} 1 & 0 & 1 & 1 \\ 1 & 1 & 1 & 0\\ 0 & 1 & 1 & 1 \end{pmatrix}\end{aligned}
が得られる。(3)式により、\(\boldsymbol{G}\)を求める。
\begin{aligned}\boldsymbol{P}=\begin{pmatrix} 1 & 1 & 0 \\ 0 & 1 & 1 \\ 1 & 1 & 1 \\ 1 & 0 & 1\end{pmatrix}\end{aligned}
行の個数が4つのため、単位行列は4*4成分。
\begin{aligned}\boldsymbol{G}&=[\boldsymbol{I},\boldsymbol{P}] \\ &=\begin{pmatrix} 1 & 0 & 0 & 0 & 1 & 1 & 0 \\ 0 & 1 & 0 & 0 & 0 & 1 & 1 \\ 0 & 0 & 1 & 0 & 1 & 1 & 1 \\ 0 & 0 & 0 & 1 & 1 & 0 & 1 \end{pmatrix}\end{aligned}
(2)符号語の生成
(1)より、行の成分は4つ。よって、入力符号\(\boldsymbol{c}\)を
\begin{aligned}\boldsymbol{c}=(c_{0},c_{1},c_{2},c_{3})\end{aligned}で4成分定義する。
この時の生成符号は
\begin{aligned}\boldsymbol{c}\boldsymbol{G} &=(c_{0},c_{1},c_{2},c_{3},c_{0}\oplus c_{2}\oplus c_{3},c_{0}\oplus c_{1}\oplus c_{2}, c_{1}\oplus c_{2}\oplus c_{3})\end{aligned}
\(c_{i} ∊(0,1)\)のため、考えられる生成符号は下記のパターンになる。
| \(c_{0}\) | \(c_{1}\) | \(c_{2}\) | \(c_{3}\) | \(c_{0}\oplus c_{2}\oplus c_{3}\) | \(c_{0}\oplus c_{1}\oplus c_{2}\) | \(c_{1}\oplus c_{2}\oplus c_{3}\) |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 0 | 1 | 1 | 0 | 1 |
| 0 | 0 | 1 | 0 | 1 | 1 | 1 |
| 0 | 0 | 1 | 1 | 0 | 1 | 0 |
| 0 | 1 | 0 | 0 | 0 | 1 | 1 |
| 0 | 1 | 0 | 1 | 1 | 1 | 0 |
| 0 | 1 | 1 | 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 1 | 0 | 0 | 1 |
| 1 | 0 | 0 | 0 | 1 | 1 | 0 |
| 1 | 0 | 0 | 1 | 0 | 1 | 1 |
| 1 | 0 | 1 | 0 | 0 | 0 | 1 |
| 1 | 0 | 1 | 1 | 1 | 0 | 0 |
| 1 | 1 | 0 | 0 | 1 | 0 | 1 |
| 1 | 1 | 0 | 1 | 0 | 0 | 0 |
| 1 | 1 | 1 | 0 | 0 | 1 | 0 |
| 1 | 1 | 1 | 1 | 1 | 1 | 1 |
(3)誤り訂正
[1 1 1 1 1 1 0]は、(2)の符号語の一覧表に無いため、誤りである。
最もハミング距離が小さい符号は、[1 1 1 1 1 1 1]のため、これに訂正する。
