情報理論 - ガロア体

概要

誤り検出能力や誤り訂正能力を高めるための基礎的な理論には、体と拡大体の考え方が用いられる。
ここでは、体と拡大体の基本的な考え方を記載する。

体

有理数の全体を$\mathbb {Q}$とする時、$\mathbb {Q}$は四則で閉じている。
すなわち、$a,b\in \mathbb {Q}$ とすると、以下が成り立つ。
$a+b,\quad a-b,\quad ab,\quad b\neq 0{\mbox{ の と き }}{\frac {a}{b}}$

同様に、実数の全体を$\mathbb {R}$とする時、$\mathbb {R}$も四則で閉じている。

集合$\mathbb {Q} ,\mathbb {R}$に限らず、四則で閉じている集合を体という。
特に、集合$\mathbb {Q}$を有理数体、集合$\mathbb {R}$を実数体という。

下図に、群環体の定義を示す。

ガロア体

体には、要素数が有限のものもあり、これをガロア体(有限体)といい、要素数がq個であるガロア体をGF(q)で表す。
特に、GF(2)は0と1の要素から成り、加法と乗法の演算は下表のようになる。

GF(2)の加法演算では、1 + 1 = 0となることに注意すること。

また、加法についての単位元は0、乗法についての単位元は1である。

GF(2)の加法演算

+	0	1
0	0	1
1	1	0

GF(2)の乗法演算

×	0	1
0	0	0
1	0	1

多項式

体F上の多項式

体Fの要素を係数とする多項式を、体F上の多項式と呼ぶ。
そして、体F上の多項式間の演算は、実数体上の多項式と同様に行う。

既約多項式

体F上の多項式で、それよりも次数の低い体F上多項式に因数分解できない多項式を既約多項式という。
特に、次数がmである時、m次既約多項式という。

例.1
多項式$1+x^{2},1+x+x^{2},1+x+x^{3}$は、全ての係数がGF(2)の要素0、1であるから、GF(2)上の多項式である。
${\begin{aligned}(1+x+x^{2})+(1+x+x^{3})&=(1+1)+(x+x)+x^{2}+x^{3}\\&=(1+1)+x(1+1)+x^{2}+x^{3}\\&=0+x\times 0+x^{2}+x^{3}\\&=x^{2}+x^{3}\end{aligned}}$

${\begin{aligned}(1+x^{2})(1+x+x^{3})&=1+x+x^{3}+x^{2}+x^{3}+x^{5}\\&=1+x+x^{2}+(x^{3}+x^{3})+x^{5}\\&=1+x+x^{2}+x^{5}\\&=x^{2}+x^{3}\end{aligned}}$

例.2
多項式$1+x+x^{3}$ と $1+x^{2}+x^{3}$ は、GF(2)上の3次の既約多項式である。

例.3
5次多項式$1+x+x^{2}+x^{5}$ は、$(1+x^{2})(1+x+x^{3})$と因数分解できるため、既約多項式ではない。