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

$${GF(2)}$$上の多項式$${g(x)}$$が根$${\beta}$$を持つならば、共役元$${\beta^{2^i}}$$も$${g(x)}$$の根である。

l個からなる共役元すべてを根にもつl次のモニックな多項式

$$
f(x) = (x-\beta)(x-\beta^2)(x-\beta^4)\cdots(x-\beta^{2^{l-1}})
$$

は$${GF(2)}$$上の多項式である。(係数が0か1)
また、$${GF(2)}$$上で既約でモニックなのでこれらの根の最小多項式でもある。

例題3.17 $${GF(2^3)}$$の元$${\alpha}$$の最小多項式を$${f(x) = x^3 + x^2 + 1}$$とする。$${f(x)}$$を$${GF(2^3)}$$上の一次式の積に因数分解せよ

解答 $${\alpha^2, \alpha^4}$$も根であるから、$${f(x) = (x - \alpha)(x - \alpha^2)(x - \alpha^4)}$$

例題3.18  $${GF(2^4)}$$の原始元$${\alpha}$$の$${GF(2)}$$上の最小多項式を$${M_1(x) = x^4 + x + 1}$$とする。$${GF(2^4)}$$の各元の$${GF(2)}$$上の最小多項式を求めよ

解答 $${\alpha^2, \alpha^4, \alpha^8}$$は$${\alpha}$$の共役元なので$${M_1(x)}$$を最小多項式にもつ。

$${\alpha^3, \alpha^6, \alpha^{12}, \alpha^{24}=\alpha^9, \alpha^{18} = \alpha^3}$$よりこれら共役元の最小多項式は$${M_2(x) = (x - \alpha^3)(x - \alpha^6)(x - \alpha^{12})(x - \alpha^9)}$$

$${\alpha^5, \alpha^{10}, \alpha^{20} = \alpha^5}$$よりこれら共役元の最小多項式は$${M_3(x) = (x - \alpha^5)(x - \alpha^{10})}$$

$${\alpha^7, \alpha^{14}, \alpha^{28} = \alpha^{13}, \alpha^{26} = \alpha^{11}}$$よりこれら共役元の最小多項式は$${M_4(x) = (x - \alpha^7)(x - \alpha^{11})(x - \alpha^{13})(x - \alpha^{14})}$$

0,1の最小多項式はそれぞれ$${x, x+1}$$である。

以下は展開計算

$$
\alpha^4 = \alpha + 1 \\
\alpha^5 = \alpha^2+\alpha \\
\alpha^6 = \alpha^3+\alpha^2 \\
\alpha^7 = \alpha^3+\alpha + 1 \\
\alpha^8 = \alpha^2+1 \\
\alpha^9 = \alpha^3+\alpha \\
\alpha^{10} = \alpha^2+\alpha +1 \\
\alpha^{11} = \alpha^3+\alpha^2 +\alpha \\
\alpha^{12} = \alpha^3+\alpha^2 +\alpha + 1\\
\alpha^{13} = \alpha^3+\alpha^2 + 1\\
\alpha^{14} = \alpha^3 + 1\\
\alpha^{15} = 1\\
$$