符号多項式

例題で学ぶ符号理論入門の勉強メモ

符号長nの符号語

$$
\boldsymbol{w}=a_0a_1\cdots a_{n-1}
$$

に多項式

$$
w(x) = a_0 + a_1x + \cdots + a_{n-1}x^{n-1}
$$

を対応させる時、多項式を符号多項式という。

巡回符号 符号語を右に1つシフトした(折り返しは左端へ戻す)数字列も符号語になるときに巡回符号という。
$${C = {000, 100, 010, 110, 001, 101, 011, 111}}$$

符号多項式での巡回符号におけるシフトは、$${x}$$をかけて$${x^n-1}$$で割った余りをとることに相当する。

$$
xw(x) = a_0x + a_1x^2 +\cdots + a_{n-1}x^n \\
= a_{n-1} + a_0x + a_1x^2 +\cdots + a_{n-1}(x^n - 1) \\
\equiv a_{n-1} + a_0x + a_1x^2 +\cdots + a_{n-2} (mod (x^n -1))
$$

今後巡回符号の符号多項式の演算においては特に必要がなければ$${mod (x^n -1)}$$は省略し、$${\equiv}$$の代わりに$${=}$$を用いる。

符号多項式の性質1
巡回符号Cの任意の符号多項式を$${w_i(x)}$$と$${w_j(x)}$$とすると次が成り立つ。
(i) $${w_i(x) + w_j(x)}$$はCの符号多項式。巡回符号は線形符号だから。
(ii)$${x^lw_i(x)}$$はCの符号多項式。巡回符号だから。

符号多項式の性質2
符号多項式に任意の多項式$${a(x)}$$をかけてもCの符号多項式になる。

符号多項式の性質3
$${g(x)}$$を0でないCの最小次数の符号多項式とするとき、Cの任意の符号多項式$${w(x)}$$は$${g(x)}$$で割り切れる。

証明 余り$${r(x), deg r(x) < deg g(x)}$$とおくと$${w(x) = a(x)g(x) + r(x)}$$で$${w(x) - a(x)g(x) = r(x)}$$とおけるから、$${r(x)}$$もCの符号多項式どうしの和なのでCの符号多項式となる。しかし$${deg r(x) < deg g(x)}$$であり$${r(x)}$$が0でないと$${g(x)}$$が最小次数であることに矛盾する。

$${g(x)}$$を生成多項式といい、$${a(x)}$$を情報多項式という。

符号多項式の性質4
符号長nの巡回符号Cの生成多項式g(x)は、$${x^n-1}$$を割り切る。

証明 $${deg g(x) = n-k}$$として、$${g(x) = g_0 + g_1x + \cdots + g_{n-k}x^{n-k}, g_{n-k} = 1}$$とおく。$${x^k}$$をかけると

$$
g(x)x^k = g_0x^k + g_1x^{k+1} + \cdots + g_{n-k}x^{n} \\
g(x)x^k = g_{n-k} + g_0x^k + g_1x^{k+1} + \cdots + g_{n-k}(x^{n}-1) \\
g(x)x^k + (x^n-1) = g_{n-k} + g_0x^k + g_1x^{k+1} + \cdots g_{n-k-1}x^{n-1}\\
$$

右辺は巡回した形になってるので符号多項式。したがって$${g(x)}$$で割り切れる。

$$
g(x)x^k + (x^n-1) = q(x)g(x)  \\
(x^n-1) = q(x)g(x) + g(x)x^k  \\
(x^n-1) = (q(x) - x^k)g(x)
$$