BCH符号を作ろう3

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

例題5.2(4) 前の記事について、(15,7,5)原始BCH符号において、"1010011"を組織符号化せよ。

解答 生成多項式は前と同じ$${g(x)=M_1(x)M_3(x) = 1 + x^4 + x^6 + x^7 + x^8}$$。情報多項式は$${a(x) = 1 + x^2 + x^5 + x^6}$$。組織符号化では、$${a(x)x^{8}}$$を$${g(x)}$$で割った余り$${r(x)}$$を計算し、$${a(x)x^{8} + r(x)}$$を符号とする。$${r(x) = x^7 + x^5 + x^3 + x + 1}$$であり、符号語は$${1 + x + x^3 + x^5 + x^7 + x^8 + x^{10} + x^{13} + x^{14} }$$。

例題5.3 原始多項式$${x^5 + x^2 + 1}$$の根を$${\alpha}$$とする。
(1) $${\alpha}$$によって生成される$${GF(2)}$$のガロア拡大体を求めよ。
(2) $${x^31 - 1}$$を$${GF(2)}$$上の多項式の積に因数分解すると
$${x^31 - 1 = (x +1)(x^5 + x^2 +1)(x^5 + x^3 +1)(x^5 + x^3 + x^2 + x+1)(x^5 + x^4 + x^2 + x+1)(x^5 + x^4 + x^3 + x+1)(x^5 + x^4 + x^3 + x^2+1) }$$となる。各因数の根を求めよ。

解答 (1) $${GF(2^5)}$$が生成される。元は

$$
\alpha^{5} = \alpha^2 + 1 \\
\alpha^{6} = \alpha^3 + \alpha \\
\alpha^{7} = \alpha^4 + \alpha^2 \\
\alpha^{8} = \alpha^5 + \alpha^3 =  \alpha^3 + \alpha^2 + 1\\
\alpha^{9} = \alpha^4 + \alpha^3 + \alpha \\
\alpha^{10} = \alpha^5 + \alpha^4 + \alpha^2 = \alpha^4 + 1 \\
\alpha^{11} = \alpha^5 + \alpha = \alpha^2 + \alpha + 1 \\
\alpha^{12} = \alpha^3 + \alpha^2 + \alpha \\
\alpha^{13} = \alpha^4 + \alpha^3 + \alpha^2 \\
\alpha^{14} = \alpha^5 + \alpha^4 + \alpha^3 = \alpha^4 + \alpha^3 + \alpha^2 + 1 \\
\alpha^{15} = \alpha^5 + \alpha^4 + \alpha^3 + \alpha = \alpha^4 + \alpha^3 + \alpha^2 + \alpha + 1 \\
\alpha^{16} = \alpha^5 + \alpha^4 + \alpha^3 + \alpha^2 + \alpha = \alpha^4 + \alpha^3 + \alpha + 1 \\
\alpha^{17} = \alpha^5 + \alpha^4 + \alpha^2 + \alpha = \alpha^4 + \alpha + 1 \\
\alpha^{18} = \alpha^5 + \alpha^2 + \alpha = \alpha + 1 \\
\alpha^{19} = \alpha^2 + \alpha \\
\alpha^{20} = \alpha^3 + \alpha^2 \\
\alpha^{21} = \alpha^4 + \alpha^3 \\
\alpha^{22} = \alpha^5 + \alpha^4 = \alpha^4 + \alpha^2 + 1 \\
\alpha^{23} = \alpha^5 + \alpha^3 + \alpha = \alpha^3 + \alpha^2 + \alpha + 1 \\
\alpha^{24} = \alpha^4 + \alpha^3 + \alpha^2 + \alpha \\
\alpha^{25} = \alpha^5 + \alpha^4 + \alpha^3 + \alpha^2 = \alpha^4 + \alpha^3 + 1  \\
\alpha^{26} = \alpha^5 + \alpha^4 + \alpha = \alpha^4 + \alpha^2 + \alpha + 1  \\
\alpha^{27} = \alpha^5 + \alpha^3 + \alpha^2 + \alpha = \alpha^3 + \alpha + 1  \\
\alpha^{28} = \alpha^4 + \alpha^2 + \alpha  \\
\alpha^{29} = \alpha^5 + \alpha^3 + \alpha^2 = \alpha^3 + 1\\
\alpha^{30} = \alpha^4 + \alpha \\
\alpha^{31} = \alpha^5 + \alpha^2 = 1 \\
$$

(2) 根を代入して確認する。共役元は同じ最小多項式を持つので無駄を減らすためにまず明らかにする。
$${\alpha}$$の指数について以下の組が共役元である(2, 4, 8, …をかけて、31の余りを取る)
(1,2,4,8,16), (3,6,12,24,17), (5,10,20,9,18), (7,14,28,25,19), (11,22,13,26,21), (15,30,29,27,23) 

$${(x +1)}$$の根は1

$${(x^5 + x^2 +1)}$$の根は$${\alpha, \alpha^2, \alpha^4, \alpha^8, \alpha^{16}}$$

$${(x^5 + x^3 +1)}$$の根は：
$${\alpha^3}$$を代入：$${\alpha^{15} + \alpha^{9} +1 = \alpha^{2}}$$。
$${\alpha^5}$$を代入：$${\alpha^{25} + \alpha^{15} +1 = \alpha^{2} + \alpha + 1}$$
$${\alpha^7}$$を代入：$${\alpha^{35} + \alpha^{21} +1 = \alpha^{4} + \alpha^4 + \alpha^3 + 1}$$
$${\alpha^11}$$を代入：$${\alpha^{55} + \alpha^{33} +1 = \alpha^{24} + \alpha^2 + 1 = \alpha^4 + \alpha^3 + \alpha + 1}$$
$${\alpha^{15}}$$を代入：$${\alpha^{75} + \alpha^{45} +1 = \alpha^{13} + \alpha^{14} + 1 = 0}$$より、根は$${\alpha^{15}}$$と共役元