【情報理論】生成多項式を用いた生成行列の作成。誤り符号の訂正

生成行列の作成方法

以前の記事では、検査行列から生成行列を求める方法を説明しました。今回は、巡回符号における生成多項式から求める場合を解説します。

まずこれが基本方針です。(1)を実際に解いてみて身につけましょう。

解答例(1)

$n=7$、$n-k=4$より、$k=3$

よって、$x^0,x^1,x^2$の次数まで$G(x)$を乗算すればよく

$$\begin{array}{}\text{(1)}& \{\begin{array}{l}G(x)=x^4+x^2+x+1\\ xG(x)=x^5+x^3+x^2+x\\ x^{2}G(x)=x^6+x^4+x^3+x^2\end{array}\end{array}$$

これを行列表示すると、求める生成行列は

$$\begin{array}{}\text{(2)}& \begin{array}{r}{\mathit{G}}^{\mathbf{\ast }}(c)=\left(\begin{array}{ccccccc}1& 1& 1& 0& 1& 0& 0\\ 0& 1& 1& 1& 0& 1& 0\\ 0& 0& 1& 1& 1& 0& 1\end{array}\right)\end{array}\end{array}$$

検査行列の求め方

符号多項式から求めた生成行列も、単位行列と情報・検査ビット関連行列$\mathit{P}$に分解できます。

よって、以前の記事で説明したように、$\mathit{P}$を介して検査行列を求めることができます。

ただし、下記2点に注意する必要があります。

線形符号の場合は$$\begin{array}{}\text{(4)}& \begin{array}{r}\mathit{G}=[\mathit{I}\mathit{P}]\end{array}\end{array}$$

と左に単位行列成分がありましたが、今回(巡回符号)は逆です。

同じく、検査行列に関しても線形符号と逆になります。(巡回符号の場合は以下です。)

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

解答例(2)

(2)式を行基本変形する。3行目に1行目を足し

$$\begin{array}{}\text{(6)}& \begin{array}{r}{\mathit{G}}^{\mathbf{\ast }}(c)=\left(\begin{array}{ccccccc}1& 1& 1& 0& 1& 0& 0\\ 0& 1& 1& 1& 0& 1& 0\\ 1& 1& 0& 1& 0& 0& 1\end{array}\right)\end{array}\end{array}$$

転置も考慮すると、情報・検査ビット関連行列は

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

(4)式より、求める検査行列は

$$\begin{array}{}\text{(8)}& \begin{array}{r}{\mathit{H}}^{\mathbf{\ast }}(c)=\left(\begin{array}{ccccccc}1& 0& 0& 0& 1& 0& 1\\ 0& 1& 0& 0& 1& 1& 1\\ 0& 0& 1& 0& 1& 1& 0\\ 0& 0& 0& 1& 0& 1& 1\end{array}\right)\end{array}\end{array}$$

誤り符号の訂正

これは、線形符号の場合のシンドロームの使い方と同じです。出力符号を$\mathit{y}$として

$$\begin{array}{}\text{(9)}& \begin{array}{r}\mathit{s}=\mathit{y}{H}^t\end{array}\end{array}$$

に基づいて計算していけば良いです。誤っている成分の判定方法も同じです。

解答例(3)

$$\begin{array}{}\text{(10)}& \begin{array}{rl}\mathit{s}& =(1010010)\left(\begin{array}{cccc}1& 0& 0& 0\\ 0& 1& 0& 0\\ 0& 0& 1& 0\\ 0& 0& 0& 1\\ 1& 1& 1& 0\\ 0& 1& 1& 1\\ 1& 1& 0& 1\end{array}\right)\\ & =(1101)\end{array}\end{array}$$

7行目と一致するので、出力符号の7番目が誤り。

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