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

さて, 上で見てきたのは, 線形符号を定義通り ${\bf F}_2^k$から ${\bf F}_2^n$への1対1の線形写像の像としてみることだったが, 実はもう一つ別の見方がある.

(n,k)-線形符号 $C\subset{\bf F}_2^n$は, ${\bf F}_2^n$のk-次元線形部分空間であるから, ${\bf F}_2^n$から ${\bf F}_2^{n-k}$への線形写像でCを核(kernel)とするものが存在する. この写像を$\psi$とすると, $\psi({\mathbf y})={\mathbf y}H$となるような行列 $H\in M(n\times(n-k),{\bf F}_2)$が存在する. ${\mathbf y}\in C \Leftrightarrow \psi({\mathbf y})={\mathbf 0}$であるから,

$${\mathbf y}\in C \Longleftrightarrow {\mathbf y}H={\mathbf 0}$$

が成り立つ. したがって, 線形符号Cは, 斉次連立一次方程式 yH=の解空間として捉えられることがわかる. このHをCのパリティ検査行列(parity check matrix)と呼ぶ. 簡単にわかることだが, 線形符号Cの生成行列が標準形(E_k P)であるとき, パリティ検査行列Hは,

$$H=\begin{pmatrix}-P \\ E_{n-k}\end{pmatrix}$$

で与えられる.