符号多項式と生成多項式、検査多項式の関係

生成多項式$G(x)$について

任意のn次符号多項式$F(x)$に対し、下記の計算を満たすものです。

符号多項式および$x^n-1$を余り無しで割り切れることを示しています。

簡易的な証明

符号多項式を下記のように置く。

$$\begin{array}{}\text{(2)}& \begin{array}{r}F(x)=a_0+a_{1}x+\cdots +a_{n-2}{x}^{n-2}+a_{n-1}{x}^{n-1}\end{array}\end{array}$$

これにxをかけて、式変形すると

$$\begin{array}{}\text{(3)}& \begin{array}{rl}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{array}\end{array}$$

$xF(x)$を$x^n-1$で割った時、余りが$F^{(1)}(x)$であることを示している。

これは、$x^{i}F(x)$など、任意の$i=1,2,\cdots ,n$で成立する。

線形符号語$\mathit{c}=(c_1,c_2,\cdots ,c_n)$を考慮すると

$$\begin{array}{}\text{(4)}& \begin{array}{r}\sum _{i=1}^N{c}_i\left(x^{i}F\left(x\right)\right)mod(x^n-1)=\sum _{i=1}^N{c}_i{f}^{\left(i\right)}\left(x\right)\end{array}\end{array}$$

と置ける。

$$\begin{array}{}\text{(5)}& \begin{array}{r}\sum _{i=1}^N{c}_i{x}^i=C\left(x\right)\end{array}\end{array}$$

とすると、任意の多項式$C(x)$に対して

$$\begin{array}{}\text{(6)}& \begin{array}{r}C(x)F(x)mod(x^n-1)=\sum _{i=1}^N{c}_i{f}^{\left(i\right)}\left(x\right)\end{array}\end{array}$$

$\sum _{i=1}^N{c}_i{f}^{\left(i\right)}\left(x\right)$は符号多項式であるので、命題は示された。

生成多項式と符号長の関係

符号長が$n$、情報ビットが$k$とすると生成多項式は$n-k$次になります。

検査ビット長と同じ数値になりますね。

検査多項式$H(x)$について

下記の性質を満たす多項式を言います。

入力符号$F(x)$と出力符号$Y(x)$が一致していれば、第2式が0になります。

もし、エラービット$E(x)$が混じっていれば$Y(x)\ne F(x)$で非0になります。

以前の記事で説明したシンドロームも多項式表現$S(x)$でき、

$$\begin{array}{}\text{(8)}& \begin{array}{r}S(x)=E(x)modG(x)\end{array}\end{array}$$

で表すことができます。

解答例

(1)符号語の判定

$x^9+x^7+x^6+x^5+x^3+x+1$を$G(x)=x^4+x+1$で割ると

$$\begin{array}{}\text{(9)}& \begin{array}{r}(x^9+x^7+x^6+x^5+x^3+x+1)=(x^5+x^3+1)(x^3+x+1)\end{array}\end{array}$$

で割り切れる。よって、与えられた多項式は符号語の一部である。

(2)検査ビット長および情報ビット長

$$\begin{array}{}\text{(10)}& \{\begin{array}{l}n=15\\ n-k=4\end{array}\end{array}$$

を解いて、$k=11$

以上より、検査ビット長は4。情報ビット長は11。

(3)検査多項式

問(1)の(9)式より

$$\begin{array}{}\text{(11)}& \begin{array}{r}H(x)=x^5+x^3+1\end{array}\end{array}$$