集合から線形空間へ

元のデータの形式はいろいろだが, 通信に使われるデータは, 結局のところ, 1 と 0 からなる数字の列にほかならないってことで, 前章では, 0 と 1 だけからなる数の集合$B=\{0,1\}$を考えたわけだが, ここでは, さらに この集合Bに, 足し算, 引き算, かけ算, 割算の四則演算の入れたものを考える. ここでの, 足し算, 引き算, かけ算, 割り算で, 普通と違うのは次の一点だけである.

1+1=0

これは, 1+1がBからはみ出すことを防ぐためのものである. これさえつけておけば, Bが四則演算について閉じていることが保証される. あれ? 0-1=-1は? と思う人がいるかも知れない. これは 1+1=0より, 1=-1となるから大丈夫なのだ. この四則演算の入ったBは数学で体と呼ばれるものになり, 通常 ${\bf F}_2$ という記号で書かれる.

で, この ${\bf F}_2$をBの代わりに使うと, どうなるか. まず,

$$\{\text{$k$ビットの信号}\}={\bf F}_2^k$$

となることは, Bのときと同様.

$$\begin{array}{ccc} \text{3ビットの信号}&&{\bf F}_2^3\text{ の... ...(1,0,1) \\ 110 & & (1,1,0) \\ 111 & & (1,1,1) \\ \end{array}$$

3ビットのときの例も見た目はBと全く変わらない. じゃあ, Bのときと何がちがうねん, という声が聞こえてきそうだが, ここで, 思い出して欲しい, ${\bf F}_2$には四則演算が入っていることを. この四則演算を使って, ${\bf F}_2^k$にはベクトルの足し算や${\bf F}_2$の元によるスカラー倍 (実際には「1倍」と「0倍」しかないのだが)が定義される.
$$\begin{align*}(x_1,x_2,\cdots,x_k)+(y_1,y_2,\cdots,y_k)&=(x_1+y_1,x_2+y_2,\cdots... ..._1,\lambda x_2,\cdots,\lambda x_k) \quad\quad (\lambda\in{\bf F}_2) \end{align*}$$
すなわち, ${\bf F}_2^k$は${\bf F}_2$上の線形空間(ベクトル空間) というわけだ. で, 線形空間として見ることには次の利点がある.

5桁の符号語01000を送ったらエラーが起こって, 01001になったとしよう. このときエラーは3番目と5番目のビットに起こったわけだが, ベクトル表記を用いると, x=(0,1,0,0,0), y=(0,1,0,0,1)としたとき,

$${\mathbf y}={\mathbf x}+{\mathbf e},\qquad {\mathbf e}=(0,0,1,0,1)$$

と書け, eの0でない成分のある場所がエラーの起こった個所を示すことになる. このように, 送信語と受信語そしてエラーの関係をベクトルの足し算を用いることにより, 分かりやすく記述することができるのが線形空間を用いる大きな利点の一つである. 上のように, 送信語 xと受信語 yに対し, y=x+eとなる ベクトル eのことを誤りベクトルと呼ぶ.

この利点を生かすべく, ブロック符号の数学的定式化として用いた集合の間の単射

$$\varphi : B^k \to C=\operatorname{Im}\varphi \subset B^n$$

の代わりに, 1対1の線形写像

$$\varphi : {\bf F}_2^k \to C=\operatorname{Im}\varphi\subset {\bf F}_2^n$$

を用いる. このように, ${\bf F}_2^k$から ${\bf F}_2^n$ (n>k)への1対1線形写像の像となっているような特別なブロック符号を線形符号とよぶ.

注意 1.1   一応注意しておくと, ${\bf F}_2^k$から ${\bf F}_2^n$ (n>k)への1対1線形写像の像は ${\bf F}_2^n$内のk-次元部分空間を定め, 逆に, ${\bf F}_2^n$内のk-次元部分空間に 対して, ${\bf F}_2^k$からの同型写像(したがって当然1対1)が存在するから, 結局, 線形符号とは ${\bf F}_2^n$内のk-次元部分空間である, といっても同じことにある.

以下, 本稿では線形符号のみを考える. 線形符号が一般の符号の中でよいものであるという理由については次節で述べる.