線形符号の代数的表現(1)

さて, これから少し線形代数のお話. 線形代数の本では, 大抵の場合, ベクトルといったら縦ベクトル(ようするに数字が縦に並んでいるやつね)で,

$${\mathbf x}=\begin{pmatrix}x_1\\ x_2\\ \vdots \\ x_n\end{pmatrix}$$

などと書かれるのが標準だが, 情報理論では, 前節で ${\bf F}_2^3$の元 x=(x₁,x₂,x₃)を考えたように, 普通横ベクトルを使う(コンピュータが横書き文化だからだろうが, その方がイメージに合うのだ, なんとなく). したがって, 同じ線形代数でも普段見慣れているのとはちょっと見た目が異なることになる(外見が異なるだけで本質は何も変わらない).

以上の準備の下で, 線形符号を用いた情報通信を線形代数の言葉で記述してみよう.

まず, ${\bf F}_2^n$のk次元線形空間Vを考える(k<n). Vは線形符号である. ここで, $\sharp V=2^k$であるから V はkビットの情報を持つ. さて, ${\mathbf g}_1,{\mathbf g}_2,\dots, {\mathbf g}_k\in V$をVの基底とすると, $V=\langle{\mathbf g}_1,{\mathbf g}_2,\dots, {\mathbf g}_k\rangle$ と書けるから, これを使って, 次のように ${\bf F}_2^k$とVとの間の同型写像 $f : {\bf F}_2^k \to V$をつくる.

$${\bf F}_2^k\ni{\mathbf x}=(x_1,x_2,\cdots,x_k) \longmapsto {\... ...ix}=x_1{\mathbf g}_1+x_2{\mathbf g}_2+\cdots +x_k{\mathbf g}_l$$

この同型で, 左側の ${\bf F}_2^k$が元のデータの集合で, 右側のVが符号化されたデータの集合, そしてfが符号化を行うしゃぞうである(符号化されたデータの集合がまずあって, それから元のデータの集合が出てくるというのは, 話の順序が逆と思うかも知れないが, これは単に説明の順序の問題であって本質的なことではない. 分かりにくい場合には, まず, 元のデータの集合を ${\bf F}_2^k$と同一視し(これは前節の話と同様), 次にこれから ${\bf F}_2^n$(n>k)への1対1の線形写像を考え, その写像の像(image)Vを符号化したものの集合と考えればよい. 結局のところ, ${\bf F}_2^k$から ${\bf F}_2^n$への1対1線形写像を考えることと, ${\bf F}_2^n$のk次元線形部分空間を考えることとは同じことなのである).

こうすると, 第7節の図における復号化が次の線形写像で与えられることは明らかである.

$$f^{-1} : V \to {\bf F}_2^l$$

上の同型写像に現れる行列

$$G=\begin{pmatrix} g_{11}&g_{12}&\cdots&g_{1n}\\ g_{21}&g_{22... ...ots & & \vdots \\ g_{k1}&g_{k2}&\cdots&g_{kn}\\ \end{pmatrix}$$

を生成行列(generating matrix)と呼ぶ.

符号の誤り訂正能力だけに着目すれば, ${\bf F}_2^n$の座標の入れ替えによるCの 取り替えは符号の誤り訂正能力を全く変えない. したがって, 2つの符号CとC'が ${\bf F}_2^n$の座標の入れ替えで移り合う場合, 2つを同一視することにする.

座標の入れ替えを行ったものを「同一視」することで, 線形符号の生成行列のとり方には, (Cの基底のとり方)＋( ${\bf F}_2^n$の座標の入れ替え)分の自由度が生じることになる. Cの基底の取り替えと ${\bf F}_2^n$の座標の入れ替えを行うことで, 生成行列は次の形の行列に変形できる.

$$\begin{pmatrix} {\mathbf g}_1\\ {\mathbf g}_2 \\ \vdots \\ {... ...ix} \qquad \text{ ただし, } P\in M(k\times (n-k), {\bf F}_2)$$

上の(E_k P)の形の生成行列を生成行列の標準形(standard form)と呼ぶ. 生成行列の標準形を考えるご利益は次の通りである.

1.

符号語がデータとパリティ検査ビットにきれいに分かれている. $\varphi : {\bf F}_2^k \to C$を標準形を生成行列とする線形符号とすると, $\varphi({\mathbf x})=({\mathbf x}, {\mathbf x}P)$となり, 左のk-ビット xが元のデータ, 右側の(n-k)-ビット xPがパリティ検査ビットとなる. したがって, 受信語 $(y_1,y_2,\dots,y_n)\in {\bf F}_2^n$に対してのパリティ検査 (エラーが起きたかどうかのチェック)は, $(y_{k+1},y_{k+2},\dots,y_n)P=(y_1,y_2,\dots,y_k)$をチェックすればよい.

2.

復号が簡単. 上のことからすぐわかるように, 復号は, 射影 ${\bf F}_2^n\ni (y_1,y_2,\dots,y_n)\mapsto (y_1,y_2,\dots,y_k)\in {\bf F}_2^k$ のCへの制限で得られる.