組合せとグラフの理論（塩田）第7回 (2) 2元体 $\mathbb{F}_2$
スカラーとは
ベクトルに対してただの数のことを「スカラー」と呼びます。
線形代数を習い始めたころは実数がスカラーで、
固有値の勉強をする頃になると複素数もスカラーとして使います。
行列計算をするときに、数として要求されることは何かと考えて次の定義に至ります：
Def.1 加減乗除の四則演算ができる数の集合を「体（たい）」と呼ぶ。
この観点から、実数の集合は「実数体」、複素数の集合は「複素数体」と呼ばれます。
また、実数をスカラーと考えるベクトルは「実ベクトル」あるいは「実数体上のベクトル」というように呼びます。
2元体 $\mathbb{F}_2$
ここで、情報科学にとって大切な体を導入します。
Def.2 $0$ と $1$ の 2 つしか要素を持たない集合に、
次のように加減乗除を定義した体 $\mathbb{F}_2=\{\,0,1\,\}$ を 「2元体」と呼ぶ。
|
$\begin{array}{|r|cc|}
\hline
a ＼ b & 0 & 1 \\\hline
0 & 0 & 1 \\
1 & 1 & 0 \\
\hline
\end{array}$
|
$\begin{array}{|r|cc|}
\hline
a ＼ b & 0 & 1 \\\hline
0 & 0 & 1 \\
1 & 1 & 0 \\
\hline
\end{array}$
|
$\begin{array}{|r|cc|}
\hline
a ＼ b & 0 & 1 \\\hline
0 & 0 & 0 \\
1 & 0 & 1 \\
\hline
\end{array}$
|
$\begin{array}{|r|c|}
\hline
a ＼ b & 1 \\\hline
0 & 0 \\
1 & 1 \\
\hline
\end{array}$
|
|
$a+b$
|
$a-b$
|
$a \times b$
|
$a \div b$
|
（普通の数と同様、$0$ では割れません。）
法演算を知っている人には、$\bmod 2$ の計算、と言えばわかるでしょうか。
$2=0$, $\quad -x=x$
と思って計算するのが $\mathbb{F}_2$ です。
Rem.3 $\mathbb{F}_2$ を使って設計したシステムは
- $0$, $1$ はビットそのもの
- 加法＝減法は XOR（排他的論理和）
- 乗法は AND
ですから容易にハードウェア化できて、計算も高速にできるというメリットがあります。