情報理論 - ガロア体

概要

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

体

有理数の全体を構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \Q} とする時、構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \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次既約多項式を求めるには、構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle f(x) = ax + b} において、因数分解できないため、1次既約多項式は、構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle x, \quad x + 1} の2つである。

2次以降の既約多項式では、必ず定数項を含むことに注意する。
なぜなら、定数項が存在しない場合、構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle f(0) = 0} となり、また、f(x)は1次既約多項式xで可約(因数分解)できるからである。

• 2次既約多項式

2次既約多項式を求めるには、構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle f(x) = x^2 + ax + 1} とする時、構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle [\frac{m}{2}] = 1} ([]はガウスの記号)だから、
f(x)が1次既約多項式で因数分解できなければよく、かつ、剰余定理から構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle f(0) \ne 0, \quad f(1) \ne 0} ならばよい。
構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle f(0) = 1 \ne 0}
構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle f(1) = 1 + a + 1 = a \ne 0 \quad \mbox{す な わ ち} \quad a = 1}
したがって、2次既約多項式は、構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle f(x) = x^2 + x + 1} となる。

• 3次既約多項式

3次既約多項式を求めるには、構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle f(x) = x^3 + ax^2 + bx + 1} とする時、構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle [\frac{m}{2}] = 1} だから、
f(x)が1次既約多項式で因数分解できなければよく、かつ、剰余定理から構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle f(0) \ne 0, \quad f(1) \ne 0} ならばよい。
構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle f(0) = 1 \ne 0}
構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle f(1) = 1 + a + b + 1 = a + b \ne 0 \quad \mbox{す な わ ち} \quad (a, b) = (1, 0) \quad \mbox{ま た は} \quad (0, 1)}
したがって、3次既約多項式は、構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle f(x) = x^3 + x^2 + 1, \quad f(x) = x^3 + x + 1} の2つとなる。