情報理論 - ガロア体
概要
誤り検出能力や誤り訂正能力を高めるための基礎的な理論には、体と拡大体の考え方が用いられる。
ここでは、体と拡大体の基本的な考え方を記載する。
体
有理数の全体を構文解析に失敗 (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}
は四則で閉じている。
すなわち、構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle a, b \in \Q}
とすると、以下が成り立つ。
同様に、実数の全体をとする時、も四則で閉じている。
集合に限らず、四則で閉じている集合を体という。
特に、集合を有理数体、集合を実数体という。
下図に、群環体の定義を示す。
ガロア体
体には、要素数が有限のものもあり、これをガロア体(有限体)といい、要素数が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
多項式構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle 1 + x^2, 1 + x + x^2, 1 + x + x^3}
は、全ての係数がGF(2)の要素0、1であるから、GF(2)上の多項式である。
構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \begin{align} (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{align} }
構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \begin{align} (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{align} }
例.2
多項式構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle 1 + x + x^3}
と 構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle 1 + x^2 + x^3}
は、GF(2)上の3次の既約多項式である。
例.3
5次多項式構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle 1 + x + x^2 + x^5}
は、構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle (1 + x^2)(1 + x + x^3)}
と因数分解できるため、既約多項式ではない。
GF(2)の既約多項式の求め方
m次の既約多項式を求めるには、まず、m次の次数が存在する必要がある。(例. 3次既約多項式ではx3、5次既約多項式ではx5等)
構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle GF(2) = \{0, 1\}}
のため、係数は0、 1のいずれかである。
もし、係数が2以上の値の時は、係数に構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \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 \left \lfloor \frac{m}{2} \right \rfloor = 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 n \le x < n + 1}
を満たす整数nのことを構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \lfloor x \rfloor}
と記述する。構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \lfloor x \rfloor}
は、xを超えない最大の整数とも言える。)
構文解析に失敗 (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 \left \lfloor \frac{m}{2} \right \rfloor = 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つとなる。
- 4次既約多項式
4次既約多項式を求めるには、構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle f(x) = x^4 + ax^3 + bx^2 + cx + 1}
とする時、構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \left \lfloor \frac{m}{2} \right \rfloor = 2}
だから、
f(x)が2次以下の既約多項式で因数分解できなければよく、かつ、剰余定理から構文解析に失敗 (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 + c + 1 = a + b + c \ne 0 \quad \mbox{し た が っ て} \quad a + b + c = 1}
f(x)を2次の既約多項式構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle x^2 + x + 1}
で割った剰余は、構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle x(b + c + 1) + (a + b + 1)}
構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle b + c + 1, \quad a + b + 1}
が同時に0になってはならないため、構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle b + c = 0 \quad \mbox{ま た は} \quad a + b = 0}
構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\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)}
構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle 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)}
構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \mbox{上 記 よ り} \quad (a, b, c) = (1, 1, 1), (1, 0, 0), (0, 0, 1)}
したがって、4次既約多項式は、構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle f(x) = x^4 + x^3 + x^2 + x + 1, \quad x^4 + x^3 + 1, \quad x^4 + x + 1}
の3つとなる。
