概要
誤り検出能力や誤り訂正能力を高めるための基礎的な理論には、体と拡大体の考え方が用いられる。
ここでは、体と拡大体の基本的な考え方を記載する。
体
有理数の全体を とする時、 は四則で閉じている。
すなわち、 とすると、以下が成り立つ。
構文解析に失敗 (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle a+b,\quad a-b,\quad ab,\quad b\neq 0{\mbox{ の と き }}{\frac {a}{b}}}
同様に、実数の全体を構文解析に失敗 (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \mathbb {R} }
とする時、 も四則で閉じている。
集合構文解析に失敗 (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \mathbb {Q} ,\mathbb {R} }
に限らず、四則で閉じている集合を体という。
特に、集合 を有理数体、集合 を実数体という。
下図に、群環体の定義を示す。
ガロア体
体には、要素数が有限のものもあり、これをガロア体(有限体)といい、要素数がq個であるガロア体をGF(q)で表す。
特に、GF(2)は0と1の要素から成り、加法と乗法の演算は下表のようになる。
GF(2)のことを、Z/2Zで表すこともある。
GF(2)の加法演算では、1 + 1 = 0となることに注意すること。
また、加法についての単位元は0、乗法についての単位元は1である。
| + | 0 | 1 |
|---|---|---|
| 0 | 0 | 1 |
| 1 | 1 | 0 |
| × | 0 | 1 |
|---|---|---|
| 0 | 0 | 0 |
| 1 | 0 | 1 |
多項式
体F上の多項式
体Fの要素を係数とする多項式を、体F上の多項式と呼ぶ。
そして、体F上の多項式間の演算は、実数体上の多項式と同様に行う。
既約多項式
体F上の多項式で、それよりも次数の低い体F上多項式に因数分解できない多項式を既約多項式という。
特に、次数がmである時、m次既約多項式という。
例.1
多項式 は、全ての係数がGF(2)の要素0、1であるから、GF(2)上の多項式である。
構文解析に失敗 (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle {\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}}}
構文解析に失敗 (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle {\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
多項式 と 構文解析に失敗 (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle 1+x^{2}+x^{3}}
は、GF(2)上の3次の既約多項式である。
例.3
5次多項式 は、 と因数分解できるため、既約多項式ではない。
GF(2)の既約多項式の求め方
m次の既約多項式を求めるには、まず、m次の次数が存在する必要がある。(例. 3次既約多項式ではx3、5次既約多項式ではx5等)
構文解析に失敗 (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle GF(2)=\{0,1\}}
のため、係数は0、 1のいずれかである。
もし、係数が2以上の値の時は、係数に を用いて計算する。
- 1次既約多項式
GF(2)上の1次既約多項式を求めるには、構文解析に失敗 (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle f(x)=ax+b}
において、因数分解できないため、1次既約多項式は、 の2つである。
2次以降の既約多項式では、必ず定数項を含むことに注意する。
なぜなら、定数項が存在しない場合、構文解析に失敗 (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle f(0)=0}
となり、また、f(x)は1次既約多項式xで可約だから(因数分解できるから)である。
- 2次既約多項式
2次既約多項式を求めるには、 とする時、構文解析に失敗 (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \left\lfloor {\frac {m}{2}}\right\rfloor =1}
(床関数)だから、
f(x)が1次既約多項式で因数分解できなければよく、かつ、剰余定理から ならばよい。
(床関数とは、構文解析に失敗 (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle n\leq x<n+1}
を満たす整数nのことを構文解析に失敗 (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \lfloor x\rfloor }
と記述する。 は、xを超えない最大の整数とも言える。)
構文解析に失敗 (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle f(0)=1\neq 0}
構文解析に失敗 (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle f(1)=1+a+1=a\neq 0\quad {\mbox{す な わ ち}}\quad a=1}
したがって、2次既約多項式は、 となる。
- 3次既約多項式
3次既約多項式を求めるには、構文解析に失敗 (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle f(x)=x^{3}+ax^{2}+bx+1}
とする時、構文解析に失敗 (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \left\lfloor {\frac {m}{2}}\right\rfloor =1}
だから、
f(x)が1次既約多項式で因数分解できなければよく、かつ、剰余定理から ならばよい。
構文解析に失敗 (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle f(1)=1+a+b+1=a+b\neq 0\quad {\mbox{す な わ ち}}\quad (a,b)=(1,0)\quad {\mbox{ま た は}}\quad (0,1)}
したがって、3次既約多項式は、構文解析に失敗 (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle f(x)=x^{3}+x^{2}+1,\quad f(x)=x^{3}+x+1}
の2つとなる。
- 4次既約多項式
4次既約多項式を求めるには、 とする時、構文解析に失敗 (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \left\lfloor {\frac {m}{2}}\right\rfloor =2}
だから、
f(x)が2次以下の既約多項式で因数分解できなければよく、かつ、剰余定理から ならばよい。
f(x)を2次の既約多項式構文解析に失敗 (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle x^{2}+x+1}
で割った剰余は、
構文解析に失敗 (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle b+c+1,\quad a+b+1}
が同時に0になってはならないため、
構文解析に失敗 (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle 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)}
構文解析に失敗 (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle {\mbox{上 記 よ り}}\quad (a,b,c)=(1,1,1),(1,0,0),(0,0,1)}
したがって、4次既約多項式は、 の3つとなる。
5次既約多項式を、以下に示す。
- x
- 1 + x
- 1 + x + x2
- 1 + x + x3
- 1 + x + x3
- 1 + x3 + x4
- 1 + x + x2 + x3 + x4
- 1 + x + x4
- 1 + x3 + x5
- 1 + x2 + x5
- 1 + x + x2 + x3 + x5
- 1 + x + x3 + x4 + x5
- 1 + x2 + x3 + x4 + x5
- 1 + x + x2 + x4 + x5
拡大体
体Kが体F上を含む時、体Kを体Fの拡大体という。
実数体 は、有理数体 の拡大体である。
体F上の既約多項式f(x)がある時、方程式f(x) = 0の根ωを用いて、体Fの拡大体Kを作ることができる。
GF(2)の2次の拡大体
GF(2)上の2次の既約多項式は、 だけである。
f(x) = 0の根をωとすると、 が成り立つ。
このωを用いて、集合構文解析に失敗 (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \{a+b\omega ;a,b\in GF(2)\}}
を作ると、この集合は体となる。
a、bは0か1であるから、この集合の要素は となる。
この集合の任意の2要素の和もこの集合に属する。
また、この集合の任意の2要素の積もこの集合に属する。
例.1
構文解析に失敗 (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \omega +\omega =\omega (1+1)=\omega \times 0=0}
より、 である。
これは、GF(2)では、加えることと減ずることは同じことを意味する。
例.2
構文解析に失敗 (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \omega +(1+\omega )=1+(\omega +\omega )=1+0=1}
例.3
2次の既約多項式 において、f(x) = 0の根をωとすると、 より、
また、 より、構文解析に失敗 (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \omega +1=-\omega -1}
したがって、
例.4
構文解析に失敗 (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \omega (1+\omega )=\omega +\omega ^{2}=\omega +\omega +1=0+1=1}
下表に、GF(2)の2次の拡大体の演算を示す。
| 和 | 0 | 1 | 構文解析に失敗 (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \omega } | |
|---|---|---|---|---|
| 0 | 0 | 1 | 構文解析に失敗 (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \omega } | |
| 1 | 1 | 0 | ||
| 0 | 1 | |||
| 1 | 0 |
| 積 | 0 | 1 | ||
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 1 | ||
| 0 | ||||
| 0 | 1 |
また、これらは商に関しても閉じている。
上表より、 であるから、 である。
これは、 の逆元 は、 との積が1となる元であることを意味する。
以上のように、集合 は、四則において閉じており、体である。
この体のことをGF(22)と表し、GF(2)の2次の拡大体という。
GF(22)の要素の累乗表示において、 より、
となる。
すなわち、集合GF(22)は、以下の2つの表示をすることができる。
- 線形表示
- まとめて
- 累乗表示
- まとめて 構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \{ 0, \omega^{i}; i = 0, 1, 2 \}}
累乗表示の性質から、ωをGF(22)の原始根といい、ωを根にもつ構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle f(x) = x^2 + x + 1}
をGF(22)の原始多項式という。
さらに、構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle (x - \omega)(x - \omega^2) = x^2 - x(\omega + \omega^2) + \omega^3 = x^2 + x + 1 = f(x)}
であるから、原始多項式f(x)はGF(22)で構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle f(x) = (x - \omega)(x - \omega^2)}
と因数分解される。
GF(2)の3次の拡大体
GF(2)の2次の拡大体の構成法にならって、GF(2)の3次の拡大体を構成する。
まず、GF(2)上の3次の既約多項式を求める。
GF(2)上の3次の多項式構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle f(x) = x^3 + ax^2 + bx + c \quad (a, b, c \in GF(2))}
がGF(2)上で既約であるとは、
構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle f(0) = c \ne 0}
かつ 構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle f(1) = 1 + a + b + c \ne 0}
であるから、構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle (a, b, c) = (1, 0, 1) \quad (0, 1, 1)}
となる場合である。
したがって、GF(2)上の既約多項式は、以下の2つとなる。
構文解析に失敗 (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}
GF(2)の3次の拡大体GF(23)を構成するには、まず、GF(2)の3次の既約多項式構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle f(x) = x^3 + x + 1}
を取り上げる。
f(x) = 0の根をωとする時、構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \omega^3 + \omega + 1 = 0}
となり、したがって、構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \omega^3 = - \omega - 1 = \omega + 1}
また、構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \omega \ne 0, \quad \omega \ne 1}
であるから、ωはGF(2)に含まれない。
このωを用いて集合構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \{ a + b \omega + c \omega^2; a, b, c \in GF(2) \}}
を作る。
この集合の要素を全て書くと、構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \{ 0, 1, \omega, \omega + 1, \omega^2, \omega^2 + 1, \omega^2 + \omega, \omega^2 + \omega + 1 \}}
となる。
この8個の要素のどの2つを加算しても、この集合の要素となる。
すなわち、この集合の和は閉じている。差においても閉じていることは明らかである。
下表に、この集合(GF(2)の3次の拡大体GF(23))の積の演算を示す。
| 積 | 1 | 構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \omega} | 構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \omega + 1} | 構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \omega^2} | 構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \omega^2 + 1} | 構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \omega^2 + \omega} | 構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \omega^2 + \omega + 1} |
|---|---|---|---|---|---|---|---|
| 1 | 1 | 構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \omega} | 構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \omega + 1} | 構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \omega^2} | 構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \omega^2 + 1} | 構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \omega^2 + \omega} | 構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \omega^2 + \omega + 1} |
| 構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \omega} | 構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \omega} | 構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \omega^2} | 構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \omega^2 + \omega} | ||||
| 構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \omega + 1} | 構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \omega + 1} | 1 | 構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \omega} |