生成多項式\(G(x)=x^{4}+x^{2}+x+1\)を示す巡回符号について下記の問いに答えよ。なお、符号長は7とする。
(1)生成行列\(\boldsymbol{G^{*}}(c)\)を求めよ。
(2)検査行列\(\boldsymbol{H^{*}}(c)\)を求めよ。
(3)誤り符号[1010010]を受信した。シンドローム\(\boldsymbol{s}\)を利用して、これを訂正せよ。
生成行列の作成方法
以前の記事では、検査行列から生成行列を求める方法を説明しました。今回は、巡回符号における生成多項式から求める場合を解説します。
- 符号長\(n\)に対する生成多項式の次数\(n-k\)の差、\(k\)個分\(x^{0}\) から \(x^{k-1}\)を順番に乗算する
- \(G(x),xG(x),\cdots,x^{k}G(x)\)を上から順に行列表示する。
まずこれが基本方針です。(1)を実際に解いてみて身につけましょう。
解答例(1)
\(n=7\)、\(n-k=4\)より、\(k=3\)
よって、\(x^{0},x^{1},x^{2}\)の次数まで\(G(x)\)を乗算すればよく
\begin{cases}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{cases}
これを行列表示すると、求める生成行列は
\begin{aligned}\boldsymbol{G^{*}}(c)=\begin{pmatrix} 1 & 1 & 1 & 0 & 1 & 0 & 0 \\ 0 & 1 & 1 & 1 & 0 & 1 & 0 \\ 0 & 0 & 1 & 1 & 1 & 0 & 1 \end{pmatrix}\end{aligned}
検査行列の求め方
符号多項式から求めた生成行列も、単位行列と情報・検査ビット関連行列\(\boldsymbol{P}\)に分解できます。
よって、以前の記事で説明したように、\(\boldsymbol{P}\)を介して検査行列を求めることができます。
ただし、下記2点に注意する必要があります。
- (1)で求めた生成行列は単位行列成分になっていないので、行基本変形を用いて単位行列成分を掃き出す必要がある。(既約台形正準系変換)
- \begin{aligned}\boldsymbol{G^{*}}(c)=[\boldsymbol{P^{t}}\boldsymbol{I}]\end{aligned}のように、単位行列成分を右に掃き出す。
線形符号の場合は\begin{aligned}\boldsymbol{G}=[\boldsymbol{I}\boldsymbol{P}]\end{aligned}
と左に単位行列成分がありましたが、今回(巡回符号)は逆です。
同じく、検査行列に関しても線形符号と逆になります。(巡回符号の場合は以下です。)
\begin{aligned}\boldsymbol{H^{*}}(c)=[\boldsymbol{I}\boldsymbol{P^{t}}]\end{aligned}
解答例(2)
(2)式を行基本変形する。3行目に1行目を足し
\begin{aligned}\boldsymbol{G^{*}}(c)=\begin{pmatrix} 1 & 1 & 1 & 0 & 1 & 0 & 0 \\ 0 & 1 & 1 & 1 & 0 & 1 & 0 \\ 1 & 1 & 0 & 1 & 0 & 0 & 1 \end{pmatrix}\end{aligned}
転置も考慮すると、情報・検査ビット関連行列は
\begin{aligned}\boldsymbol{P}=\begin{pmatrix} 1 & 0 & 1 \\ 1 & 1 & 1 \\ 1 & 1 & 0 \\ 0 & 1 & 1\end{pmatrix}\end{aligned}
(4)式より、求める検査行列は
\begin{aligned}\boldsymbol{H^{*}}(c)=\begin{pmatrix} 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{pmatrix}\end{aligned}
誤り符号の訂正
これは、線形符号の場合のシンドロームの使い方と同じです。出力符号を\(\boldsymbol{y}\)として
\begin{aligned}\boldsymbol{s}=\boldsymbol{y}H^{t}\end{aligned}
に基づいて計算していけば良いです。誤っている成分の判定方法も同じです。
解答例(3)
\begin{aligned}\boldsymbol{s}&=(1 0 1 0 0 1 0)\begin{pmatrix} 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{pmatrix} \\ &=(1 1 0 1)\end{aligned}
7行目と一致するので、出力符号の7番目が誤り。
正しい符号は、[1 0 1 0 0 1 1]
