下記の生成行列\begin{aligned}\boldsymbol{G}=\begin{pmatrix} 1 & 0 & 0 & 0 & 1 & 1 \\ 0 & 1 & 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 1 & 1 & 0 \end{pmatrix}\end{aligned}
について下記の問いに答えよ。
(1)検査行列\(\boldsymbol{H}\)を求めよ。
(2)[1 1 1 0 0 1]を受信したときの誤り訂正をシンドロームを用いて行え。
検査行列とは
入力符号に対する出力符号の一致性を確認するための行列です。(パリティ検査行列とも言われます。)
よく\(\boldsymbol{H}\)で表されます。
入力符号ベクトルを\(\boldsymbol{c}\)とすると、下記の関係を満たす行列。
\begin{aligned}\boldsymbol{H}\boldsymbol{c^{t}}=\boldsymbol{c}\boldsymbol{H^{t}}=\boldsymbol{0}\end{aligned}
入力符号と同じ信号を与えた時に出力0を返す行列です。
もし、出力符号\(\boldsymbol{y}\)が入力符号\(\boldsymbol{c}\)と等しければ同じく0を返します。逆に、不一致の場合は非0値を返すため、通信路のどこかでノイズが混じり、正しい値を受信できなかったことが分かります。
検査行列の求め方
以前の記事では、検査行列から生成行列\(\boldsymbol{G}\)を求める方法について説明しました。
と言うことは、当然逆もできるはずです。
本節では、生成行列から検査行列を求める方法について説明します。
手順1：生成行列\(\boldsymbol{G}\)を成分分解する
そうです。検査行列が最初から与えられた場合と同じく、生成行列の場合でも単位行列と情報・検査ビット関連行列に分解するところから始めれば良いです。
以前の記事で説明した手順2から逆の手順で検査行列を辿っていけば良いわけですね。
下記の式のように、行列\(\boldsymbol{G}\)の左側の列が単位行列に対応し、右側の列が情報・検査ビット関連行列にあたります。
\begin{aligned}\boldsymbol{G}=[\boldsymbol{I}\boldsymbol{P}]\end{aligned}
手順2：情報・検査ビット関連行列を転置する
\(\boldsymbol{P}\)を転置し、行の成分の数だけ右に単位行列をくっつけて検査行列\(\boldsymbol{H}\)が完成します。
\begin{aligned}\boldsymbol{H}=[\boldsymbol{P^{t}}\boldsymbol{I}]\end{aligned}
シンドロームとは
出力符号\(\boldsymbol{y}\)のエラー発生有無を調べるためのベクトル\(\boldsymbol{s}\)です。
出力符号ベクトル\(\boldsymbol{y}\)と検査行列\(\boldsymbol{H}\)の転置の積を用いて表される。
\begin{aligned}\boldsymbol{s}=\boldsymbol{y}\boldsymbol{H^{t}}\end{aligned}
- \(\boldsymbol{s}=0\)のとき、出力符号にエラービットは無く、入力符号と等しい。
- \(\boldsymbol{s}≠0\)のとき、出力符号にエラービットがある。
出力した\(\boldsymbol{s}\)と同じ成分を持つ列が誤っているビットである。
生成符号を利用した誤り符号の抽出方法では、予め考えられる出力パターンを網羅しておき、それに当てはまらない出力が出た時にエラーとしていました。
しかし、シンドロームを使えば、結果を総当たりで検索せずとも、ピンポイントで調査することで誤りに気付くことができます。
証明
なぜ、\(\boldsymbol{s}≠0\)が成立している時、誤りが発生しているとみなせるのでしょうか。本節では、端的に証明します。
入力符号\(\boldsymbol{c}\)に対し、通信路中にエラーが発生したとする。エラー内容をエラーベクトル\(\boldsymbol{e}\)で表現すると、出力符号\(\boldsymbol{y}\)は
\begin{aligned}\boldsymbol{y}=\boldsymbol{c}+\boldsymbol{e}\end{aligned}
で表すことができる。これを(5)式に代入すると
\begin{aligned}\boldsymbol{s}=\boldsymbol{y}\boldsymbol{H^{t}}=(\boldsymbol{c}+\boldsymbol{e})\boldsymbol{H^{t}}=\boldsymbol{c}\boldsymbol{H^{t}}+\boldsymbol{e}\boldsymbol{H^{t}}=\boldsymbol{e}\boldsymbol{H^{t}}\end{aligned}
になる。もしエラーが発生していなければ、エラーベクトルは0。エラーが発生しているときは非0になります。
この結果が、左辺\(\boldsymbol{s}\)に波及するため、定義欄で記載した確認方法がとれるというわけですね。
解答例
(1)検査行列
行の数が3つなので、3列目までは単位行列である。
よって、4列目～6列目の成分を情報・検査ビット関連行列として取り出せばよく
\begin{aligned}\boldsymbol{P^{t}}=\begin{pmatrix} 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \end{pmatrix}\end{aligned}
\(\boldsymbol{P}^{t}\)の転置行列\(P\)は、\(\boldsymbol{P^{t}}\)と等しい。
よって、求める検査行列は
\begin{aligned}\boldsymbol{G}&=[\boldsymbol{I}\boldsymbol{P}] \\ &=\begin{pmatrix} 0 & 1 & 1 & 1 & 0 & 0 \\ 1 & 0 & 1 & 0 & 1 & 0 \\ 1 & 1 & 0 & 0 & 0 & 1 \end{pmatrix}\end{aligned}\end{aligned}
(2)シンドロームを用いた符号訂正
（5）式を用いてシンドロームを計算する
\begin{aligned}\boldsymbol{s}&=(1 1 1 0 0 1)\begin{pmatrix} 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{pmatrix} \\ &=(0 0 1)\end{aligned}
(0 0 1)と一致する\(\boldsymbol{H}\)の成分は6列目
よって、受信符号の6番目の値が誤っている。
正しい受信符号は、[1 1 1 0 0 0]
