検査行列、シンドロームを用いた誤り符号訂正の例題

検査行列とは

入力符号に対する出力符号の一致性を確認するための行列です。(パリティ検査行列とも言われます。)

よく$\mathit{H}$で表されます。

入力符号と同じ信号を与えた時に出力0を返す行列です。

もし、出力符号$\mathit{y}$が入力符号$\mathit{c}$と等しければ同じく0を返します。逆に、不一致の場合は非0値を返すため、通信路のどこかでノイズが混じり、正しい値を受信できなかったことが分かります。

検査行列の求め方

以前の記事では、検査行列から生成行列$\mathit{G}$を求める方法について説明しました。

と言うことは、当然逆もできるはずです。

本節では、生成行列から検査行列を求める方法について説明します。

手順1：生成行列$\mathit{G}$を成分分解する

そうです。検査行列が最初から与えられた場合と同じく、生成行列の場合でも単位行列と情報・検査ビット関連行列に分解するところから始めれば良いです。

以前の記事で説明した手順2から逆の手順で検査行列を辿っていけば良いわけですね。

下記の式のように、行列$\mathit{G}$の左側の列が単位行列に対応し、右側の列が情報・検査ビット関連行列にあたります。

$$\begin{array}{}\text{(3)}& \begin{array}{r}\mathit{G}=[\mathit{I}\mathit{P}]\end{array}\end{array}$$

手順2：情報・検査ビット関連行列を転置する

$\mathit{P}$を転置し、行の成分の数だけ右に単位行列をくっつけて検査行列$\mathit{H}$が完成します。

$$\begin{array}{}\text{(4)}& \begin{array}{r}\mathit{H}=[{\mathit{P}}^{\mathit{t}}\mathit{I}]\end{array}\end{array}$$

シンドロームとは

出力符号$\mathit{y}$のエラー発生有無を調べるためのベクトル$\mathit{s}$です。

生成符号を利用した誤り符号の抽出方法では、予め考えられる出力パターンを網羅しておき、それに当てはまらない出力が出た時にエラーとしていました。

しかし、シンドロームを使えば、結果を総当たりで検索せずとも、ピンポイントで調査することで誤りに気付くことができます。

証明

なぜ、$\mathit{s}\ne 0$が成立している時、誤りが発生しているとみなせるのでしょうか。本節では、端的に証明します。

入力符号$\mathit{c}$に対し、通信路中にエラーが発生したとする。エラー内容をエラーベクトル$\mathit{e}$で表現すると、出力符号$\mathit{y}$は

$$\begin{array}{}\text{(6)}& \begin{array}{r}\mathit{y}=\mathit{c}+\mathit{e}\end{array}\end{array}$$

で表すことができる。これを(5)式に代入すると

$$\begin{array}{}\text{(7)}& \begin{array}{r}\mathit{s}=\mathit{y}{\mathit{H}}^{\mathit{t}}=(\mathit{c}+\mathit{e}){\mathit{H}}^{\mathit{t}}=\mathit{c}{\mathit{H}}^{\mathit{t}}+\mathit{e}{\mathit{H}}^{\mathit{t}}=\mathit{e}{\mathit{H}}^{\mathit{t}}\end{array}\end{array}$$

になる。もしエラーが発生していなければ、エラーベクトルは0。エラーが発生しているときは非0になります。

この結果が、左辺$\mathit{s}$に波及するため、定義欄で記載した確認方法がとれるというわけですね。

解答例

(1)検査行列

行の数が3つなので、3列目までは単位行列である。

よって、4列目～6列目の成分を情報・検査ビット関連行列として取り出せばよく

$$\begin{array}{}\text{(8)}& \begin{array}{r}{\mathit{P}}^{\mathit{t}}=\left(\begin{array}{ccc}0& 1& 1\\ 1& 0& 1\\ 1& 1& 0\end{array}\right)\end{array}\end{array}$$

${\mathit{P}}^t$の転置行列$P$は、${\mathit{P}}^{\mathit{t}}$と等しい。

よって、求める検査行列は

$$\begin{array}{}\text{(9)}& \begin{array}{rl}\mathit{H}& =[{\mathit{P}}^{\mathit{t}}\mathit{I}]\\ & =\left(\begin{array}{cccccc}0& 1& 1& 1& 0& 0\\ 1& 0& 1& 0& 1& 0\\ 1& 1& 0& 0& 0& 1\end{array}\right)\end{array}\end{array}$$

(2)シンドロームを用いた符号訂正

（5）式を用いてシンドロームを計算する

$$\begin{array}{}\text{(10)}& \begin{array}{rl}\mathit{s}& =(111001)\left(\begin{array}{ccc}0& 1& 1\\ 1& 0& 1\\ 1& 1& 0\\ 1& 0& 0\\ 0& 1& 0\\ 0& 0& 1\end{array}\right)\\ & =(001)\end{array}\end{array}$$

(0 0 1)と一致する$\mathit{H}$の成分は6列目

よって、受信符号の6番目の値が誤っている。

正しい受信符号は、[1 1 1 0 0 0]