生成多項式\(G(x)=x^{4}+x+1\)の巡回符号について下記の問いに答えよ。
(1)多項式表現\(x^{9}+x^{7}+x^{6}+x^{5}+x^{3}+x+1\)で表される符号語は、符号Cの符号語であるか判定せよ。
(2)この生成多項式を用いて符号長\(n=15\)の巡回符号を構成したい。検査ビット長および情報ビット長を答えよ。
(3)検査多項式\(H(x)\)を求めよ。
生成多項式\(G(x)\)について
任意のn次符号多項式\(F(x)\)に対し、下記の計算を満たすものです。
\begin{cases}F(x) mod G(x)=0 \\ (x^{n}-1) mod G(x)=0\end{cases}
符号多項式および\(x^{n}-1\)を余り無しで割り切れることを示しています。
簡易的な証明
符号多項式を下記のように置く。
\begin{aligned}F(x)=a_{0}+a_{1}x+\cdots+a_{n-2}x^{n-2}+a_{n-1}x^{n-1}\end{aligned}
これにxをかけて、式変形すると
\begin{aligned}xF(x)&=a_{n-1}(x^{n}-1)+a_{n-1}+a_{0}x+\cdots+a_{n-3}x^{n-2}+a_{n-2}x^{n-1} \\ &=a_{n-1}(x^{n}-1)+F^{(1)}(x)\end{aligned}
\(xF(x)\)を\(x^{n}-1\)で割った時、余りが\(F^{(1)}(x)\)であることを示している。
これは、\(x^{i}F(x)\)など、任意の\(i=1,2,\cdots,n\)で成立する。
線形符号語\(\boldsymbol{c}=(c_{1},c_{2},\cdots,c_{n})\)を考慮すると
\begin{aligned}\sum ^{N}_{i=1}c_{i}\left( x^{i}F\left( x\right) \right) mod\left( x^{n}-1\right) =\sum ^{N}_{i=1}c_{i}f^{\left( i\right) }\left( x\right) \end{aligned}
と置ける。
\begin{aligned}\sum ^{N}_{i=1}c_{i}x^{i}=C\left( x\right)\end{aligned}
とすると、任意の多項式\(C(x)\)に対して
\begin{aligned}C(x)F(x) mod (x^{n}-1)=\sum ^{N}_{i=1}c_{i}f^{\left( i\right) }\left( x\right)\end{aligned}
\(\sum ^{N}_{i=1}c_{i}f^{\left( i\right) }\left( x\right)\)は符号多項式であるので、命題は示された。
生成多項式と符号長の関係
符号長が\(n\)、情報ビットが\(k\)とすると生成多項式は\(n-k\)次になります。
検査ビット長と同じ数値になりますね。
検査多項式\(H(x)\)について
下記の性質を満たす多項式を言います。
\begin{cases}x^{n}-1=H(x)G(x) \\ F(x)H(x) mod(x^{n}-1)=0\end{cases}
入力符号\(F(x)\)と出力符号\(Y(x)\)が一致していれば、第2式が0になります。
もし、エラービット\(E(x)\)が混じっていれば\(Y(x)≠F(x)\)で非0になります。
以前の記事で説明したシンドロームも多項式表現\(S(x)\)でき、
\begin{aligned}S(x)=E(x)mod G(x)\end{aligned}
で表すことができます。
解答例
(1)符号語の判定
\(x^{9}+x^{7}+x^{6}+x^{5}+x^{3}+x+1\)を\(G(x)=x^{4}+x+1\)で割ると
\begin{aligned}(x^{9}+x^{7}+x^{6}+x^{5}+x^{3}+x+1)=(x^{5}+x^{3}+1)(x^{3}+x+1)\end{aligned}
で割り切れる。よって、与えられた多項式は符号語の一部である。
(2)検査ビット長および情報ビット長
\begin{cases}n=15 \\ n-k=4\end{cases}
を解いて、\(k=11\)
以上より、検査ビット長は4。情報ビット長は11。
(3)検査多項式
問(1)の(9)式より
\begin{aligned}H(x)=x^{5}+x^{3}+1\end{aligned}
