情報理論 - ガロア体

概要

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

体

有理数の全体を$\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)のことを、Z/2Zで表すこともある。

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}\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})$と因数分解できるため、既約多項式ではない。

GF(2)の既約多項式の求め方

m次の既約多項式を求めるには、まず、m次の次数が存在する必要がある。(例. 3次既約多項式ではx³、5次既約多項式ではx⁵等)

$GF(2)=\{0,1\}$ のため、係数は0、 1のいずれかである。
もし、係数が2以上の値の時は、係数に${\bmod {2}}$を用いて計算する。

• 1次既約多項式

GF(2)上の1次既約多項式を求めるには、$f(x)=ax+b$において、因数分解できないため、1次既約多項式は、$x,\quad x+1$の2つである。

2次以降の既約多項式では、必ず定数項を含むことに注意する。
なぜなら、定数項が存在しない場合、$f(0)=0$となり、また、f(x)は1次既約多項式xで可約だから(因数分解できるから)である。

• 2次既約多項式

2次既約多項式を求めるには、$f(x)=x^{2}+ax+1$とする時、$\left\lfloor {\frac {m}{2}}\right\rfloor =1$ (床関数)だから、
f(x)が1次既約多項式で因数分解できなければよく、かつ、剰余定理から$f(0)\neq 0,\quad f(1)\neq 0$ならばよい。
(床関数とは、$n\leq x<n+1$を満たす整数nのことを$\lfloor x\rfloor$と記述する。$\lfloor x\rfloor$は、xを超えない最大の整数とも言える。)

$f(0)=1\neq 0$
$f(1)=1+a+1=a\neq 0\quad {\mbox{す な わ ち}}\quad a=1$
したがって、2次既約多項式は、$f(x)=x^{2}+x+1$となる。

• 3次既約多項式

3次既約多項式を求めるには、$f(x)=x^{3}+ax^{2}+bx+1$とする時、$\left\lfloor {\frac {m}{2}}\right\rfloor =1$だから、
f(x)が1次既約多項式で因数分解できなければよく、かつ、剰余定理から$f(0)\neq 0,\quad f(1)\neq 0$ならばよい。
$f(0)=1\neq 0$
$f(1)=1+a+b+1=a+b\neq 0\quad {\mbox{す な わ ち}}\quad (a,b)=(1,0)\quad {\mbox{ま た は}}\quad (0,1)$
したがって、3次既約多項式は、$f(x)=x^{3}+x^{2}+1,\quad f(x)=x^{3}+x+1$ の2つとなる。

• 4次既約多項式

4次既約多項式を求めるには、$f(x)=x^{4}+ax^{3}+bx^{2}+cx+1$とする時、$\left\lfloor {\frac {m}{2}}\right\rfloor =2$だから、
f(x)が2次以下の既約多項式で因数分解できなければよく、かつ、剰余定理から$f(0)\neq 0,\quad f(1)\neq 0$ならばよい。
$f(0)=1\neq 0$
$f(1)=1+a+b+c+1=a+b+c\neq 0\quad {\mbox{し た が っ て}}\quad a+b+c=1$

f(x)を2次の既約多項式$x^{2}+x+1$で割った剰余は、$x(b+c+1)+(a+b+1)$

$b+c+1,\quad a+b+1$が同時に0になってはならないため、$b+c=0\quad {\mbox{ま た は}}\quad a+b=0$
$a+b=0\quad {\mbox{の 時 、}}\quad a+b+c=c=1\quad {\mbox{し た が っ て}}\quad (a,b)=(0,0),(1,1)\quad {\mbox{よ り}}\quad (a,b,c)=(0,0,1),(1,1,1)$
$b+c=0\quad {\mbox{の 時 、}}\quad a+b+c=a=1\quad {\mbox{し た が っ て}}\quad (b,c)=(0,0),(1,1)\quad {\mbox{よ り}}\quad (a,b,c)=(1,0,0),(1,1,1)$

${\mbox{上 記 よ り}}\quad (a,b,c)=(1,1,1),(1,0,0),(0,0,1)$
したがって、4次既約多項式は、$f(x)=x^{4}+x^{3}+x^{2}+x+1,\quad x^{4}+x^{3}+1,\quad x^{4}+x+1$ の3つとなる。

5次既約多項式を、以下に示す。

• x
• 1 + x

  
  

• 1 + x + x²

  
  

• 1 + x + x³
• 1 + x + x³

  
  

• 1 + x³ + x⁴
• 1 + x + x² + x³ + x⁴
• 1 + x + x⁴

  
  

• 1 + x³ + x⁵
• 1 + x² + x⁵
• 1 + x + x² + x³ + x⁵
• 1 + x + x³ + x⁴ + x⁵
• 1 + x² + x³ + x⁴ + x⁵
• 1 + x + x² + x⁴ + x⁵