はじめに
テスト勉強も兼ねて、情報通信に用いられる2元線形符号の定義を解説します。
線形符号は情報の符号化と復号化が容易であるという特徴を持っており、通信の分野では基本的な符号という扱いになっているようです。
線形符号のうち、特に0と1のバイナリで符号を表現するものは2元線形符号と呼ばれます。
2元線形符号の定義は次のとおりです。
符号Cが2元有限体$\mathbb{F}_2^n$の部分集合で表現され、かつその符号が線形空間をなすものを線形符号と呼ぶ
言葉が難しいので解説します。
有限体
有限体という単語が聞き慣れないという方もいるかもしれませんが、今回扱う有限体は、みなさんが知っているビットと同じものです。
有限体とは数の集合のことです。特に今回扱う2元有限体$\mathbb{F}_2$は0と1で構成される集合です。
\mathbb{F}_2 = \{0, 1\}
また、集合の要素についての四則演算は「演算の結果を2で割ったその余り」になります。
四則演算
$\mathbb{F}_2$の上では、四則演算の結果は「演算の結果を2で割ったその余り」となります。
例えば足し算だとこんな感じです。
\begin{align}
0 + 0 &= 0 \\
0 + 1 &= 1 \\
1 + 0 &= 1 \\
1 + 1 &= 0 \\
\end{align}
整数上では$1 + 1 = 2$ですが、$\mathbb{F}_2$上では「演算の結果を2で割ったその余り」が演算の結果となるため、$1 + 1 = 0$となります。これは繰り上がりを考慮しないビットの可算と同じですね。
引き算の結果は足し算の結果と同じになります。
\begin{align}
0 - 0 &= 0 \\
0 - 1 &= 1 \\
1 - 0 &= 1 \\
1 - 1 &= 0 \\
\end{align}
掛け算はこうなります。
\begin{align}
0 \times 0 &= 0 \\
0 \times 0 &= 0 \\
1 \times 0 &= 0 \\
1 \times 1 &= 1 \\
\end{align}
割り算は0があってちょっとややこしいのでここでは考えません。
有限体のベクトル
有限体のベクトルは、有限体の要素を並べてベクトルにしたものです。
例えば2元有限体の要素を3つ並べて作られるベクトルの集合は次のようになります。
\mathbb{F}_2^3 = \{
(0 0 0),
(0 0 1),
(0 1 0),
(0 1 1),
(1 0 0),
(1 0 1),
(1 1 0),
(1 1 1)
\}
要はビット列のことです。
$\mathbb{F}_2^3$の上で成り立つ四則演算は繰り上がりを考慮しないので、例えばベクトルの足し算は
$$(0 0 1) + (0 1 1) = (0 1 0)$$
というふうになります。
線形符号とは
そもそも符号とは
ここでは2元ブロック符号という符号を扱います。
2元ブロック符号とは、要は$\mathbb{F}_2^n$の部分集合で構成される符号、もっと大ざっぱに言ってしまえば、決まった長さのビット列で表される符号のことです。
例えば長さ3の2元ブロック符号は
$$C_1 = \{(0 0 1), (0 1 1), (1 1 0)\}$$
長さ4の2元ブロック符号には
$$C_2 = \{(0 0 0 0), (0 0 1 1), (1 1 0 0), (1 1 1 1)\}$$
といったものがあります。
2元線形符号とは
2元線形符号とは、「符号Cが$\mathbb{F}_2^n$の部分集合で表現され、かつその符号が線形空間をなすもの」です。
線形空間とは、$k$個の線形独立なベクトル$\mathbf{e}_1, \mathbf{e}_2, ..., \mathbf{e}_k$によって張り出される空間のことを言います。
例えば$\mathbb{F}_2^3$において、2本の線形独立なベクトル
\mathbf{e}_1 = (0 1 1) \\
\mathbf{e}_2 = (1 1 0)
によって張り出される空間$V$は
\begin{align}
V &= \{ \\
& 0 \times (0 1 1) + 0 \times (1 1 0), \\
& 0 \times (0 1 1) + 1 \times (1 1 0), \\
& 1 \times (0 1 1) + 0 \times (1 1 0), \\
& 1 \times (0 1 1) + 1 \times (1 1 0) \\
\} \\ \\
V &=
\{
(0 0 0),
(1 1 0),
(0 1 1),
(1 0 1)
\}
\end{align}
となります。
符号$C$が$V$と同じものであるとき、$C$は$\mathbb{F}_2^n$の部分線形空間をなしています。すなわち$C$は2元線形符号であると言えます。