線形符号
線形符号とは、デジタル通信で誤り検出・訂正に使われる、データに冗長なビットを付加するブロック符号の一種です。ハミング符号が１個のエラーを訂正するのに対し、線形符号は複数個のエラーを訂正することができます。
線形符号では、 $n$ 桁の信号ベクトルで $k$ 桁の情報を送信します。残りの $m$（ $=n-k$ ）桁は検査ビットと呼ばれ、情報ビットのエラーの検出と訂正に使われます。
符号とパリティ検査行列
以下の $n$ 桁の信号を考えるとき、この信号が作る $n$ 次元のベクトル空間（線形空間）には $2^n$ 個の信号ベクトルが含まれます。
$${\bf v}=(v_1,v_2,\cdots,v_n)^t$$
この $n$ 次元ベクトル空間から $k$ 個の一次独立な基本ベクトル ${\bf u}_i$ を抽出すると、これらの基本ベクトルは $k$ 次元のベクトル空間（部分空間）を作り、この中には $2^k$ 個の信号ベクトル ${\bf w}$ が含まれます。この ${\bf w}$ を符号ベクトル（以下、符号）として利用します。
$${\bf w}=\sum_{i=1}^ka_i{\bf u}_i , a_i=0\,\mathrm{or}\,1$$
この符号 ${\bf w}$ は、$m\times n$ のパリティ検査行列 $H$ に対し以下の条件を持ちます。
$$H{\bf w}=0 -①$$$$\left(\begin{array}{ccc} h_{11} & \cdots & h_{1n} \\
\vdots & & \vdots \\
h_{m1} & \cdots & h_{mn} \end{array}\right)\left(\begin{array}{ccc} w_1 \\
\vdots \\
w_n \end{array}\right)=0$$
符号化法
$n$ 桁の信号ベクトルを $k$ 桁の情報ビット ${\bf x}$ と $m$ 桁の検査ビット ${\bf c}$ に分けます。
$${\bf w}=({\bf x},{\bf c})^t=(x_1,\cdots,x_k,c_1,\cdots,c_m) -②$$
検査ビットは以下で求めます。
$${\bf c}=-H_1{\bf x} -③$$
尚、ここで $H_1$ は、②を使って①を書き換えた以下の式で定義されます。
$$H_1{\bf x}+H_2{\bf c}=0 -⓸$$$$\left(\begin{array}{ccc} h_{11} & \cdots & h_{1k} \\
\vdots & & \vdots \\
h_{m1} & \cdots & h_{mk} \end{array}\right)\left(\begin{array}{ccc} x_1 \\
\vdots \\
x_k \end{array}\right)+\left(\begin{array}{ccc} 1 & & 0 \\
& \ddots & \\
0 & & 1 \end{array}\right)\left(\begin{array}{ccc} c_1 \\
\vdots \\
c_m \end{array}\right)=0$$
③の導出
②を使って①を書き換えると以下になり、これを２つに分けると④が得られます。
$$\left(\begin{array}{ccc} h_{11} & \cdots & h_{1k} & h_{11}’ & \cdots & h_{1m}’ \\
\vdots & & \vdots & \vdots & & \vdots \\
h_{m1} & \cdots & h_{mk} & h_{m1}’ & \cdots & h_{mm}’ \end{array}\right)\left(\begin{array}{ccc} x_1 \\ \vdots \\ x_k \\ c_1 \\ \vdots \\ c_m \end{array}\right)=0$$
⓸の両辺の左から $H_2^{-1}$ を掛けると、
$${\bf c}+H_2^{-1}H_1{\bf x}=0$$
ここで $H_2$ を単位行列とすると③が得られます。
複合化法
信号ベクトル ${\bf w}$ を送信し、途中でエラー ${\bf e}$ が発生した場合、実際に受信された信号 ${\bf z}$ は、
$${\bf z}={\bf w}+{\bf e} -⑤$$$${\bf e}=(e_1,e_2,\cdots,e_n)^t$$
このときのエラーの個数 $d_i$ は、２つの信号ベクトルの距離により求められます。
$$d_i=d({\bf z},{\bf w}_i)\equiv\sum_{j=1}^n|z_j-w_{ij}| -⑥$$
$m$ 桁のベクトル ${\bf s}$ を以下で定義すると、
$${\bf s}\equiv H{\bf z}$$$$\left(\begin{array}{ccc} s_1 \\ \vdots \\ s_m \end{array}\right)=\left(\begin{array}{ccc} h_{11} & \cdots & h_{1k} & 1 & \cdots & 0 \\
\vdots & & \vdots & \vdots & \ddots & \vdots \\
h_{m1} & \cdots & h_{mk} & 0 & \cdots & 1 \end{array}\right)\left(\begin{array}{ccc} z_1 \\ \vdots \\ z_n \end{array}\right)$$
これに⑤を代入し、①を使うと以下になります。
$$H{\bf e}={\bf s} -⑦$$
⑦は $n$ 桁の変数（$e_1\sim e_n$）に対して $m$ 個の式の連立方程式であるため、⑧が成り立つエラーベクトル ${\bf e}$ は $2^k$ 個あります。この ${\bf e}$ の中で成分の１の数が最も少ないエラーベクトルを $\hat{\bf e}$ とすると、送信した信号ベクトル $\hat{\bf w}$ は以下で求められます。
$$\hat{\bf w}={\bf z}+\hat{\bf e} -⑧$$
尤度関数による複合化
１桁の信号のエラーが起きる確率を $q$ とすると、信号ベクトル ${\bf w}_i$ を送付したときに信号ベクトル ${\bf z}$ が受信する確率 $p({\bf z}|{\bf w}_i)$ は、
$$p({\bf z}|{\bf w}_i)=q^{d_i}(1-q)^{1-d_i}$$
これにより、信号ベクトル ${\bf z}$ を受信したときに、送信した信号ベクトルが ${\bf w}_i$ である確率 $p({\bf w}_i|{\bf z})$ は、ベイズの定理より以下で求められます。$p({\bf w}_i|{\bf z})$ が最大となる ${\bf w}_i$ が送信した信号ベクトルと考えることができます。
$$p({\bf w}_i|{\bf z})=\frac{p({\bf z}|{\bf w}_i)p({\bf w}_i)}{p({\bf z})}$$
$p({\bf w}_i)$ が信号によらず一定であるとすると、上記は最大の $p({\bf z}|{\bf w}_i)$ を求める問題となります。$p({\bf z}|{\bf w}_i)$ は、２つの信号ベクトルの距離⑥が小さいほど大きくなります。
エラー訂正
パリティ検査行列 $H$ と訂正可能なエラービットの数 $d$ には以下の定理が成り立ちます。
| 線形符号が $d$ 個のエラーを訂正できるための条件は、パリティ検査行列 $H$ のどの $2d$ 個の列も一次独立であることである。 |
この定理を分解すると以下になります。
- $d$ 個のエラーを訂正できる符号系は、各符号間の距離が $2d+1$ 以上である。
- 各符号間の距離の最小値（$2d+1$）は、各符号の１の数の最小値（$2d+1$）に等しい。
- 各符号の１の数が $2d$ より大きいことと、パリティ検査行列の任意の $2d$ 個の列が一次独立であることは同値である。
１については符号間の距離（ハミング距離）の定義より明らかであるため、２と３について導出します。
２の導出
最小の距離を持つ２つの符号を ${\bf v}_1$ と ${\bf v}_2$ とします。この距離は平行移動で不変であり、${\bf v}_2+{\bf v}_2=0$ であるため、
$$d({\bf v}_1,{\bf v}_2)=d({\bf v}_1+{\bf v}_2,{\bf v}_2+{\bf v}_2)=d({\bf v}_1+{\bf v}_2,0)$$
以下より、${\bf v}_1$ と ${\bf v}_2$ が符号であれば、${\bf v}_1+{\bf v}_2$ も符号になります。上式の右辺は符号 ${\bf v}_1+{\bf v}_2$ と原点との距離を表しますが、これは ${\bf v}_1+{\bf v}_2$ の１の数に等しくなります。従って、符号間の距離の最小値と符号の１の数の最小値は等しくなります。
$$H({\bf v}_1+{\bf v}_2)=H{\bf v}_1+H{\bf v}_2=0$$
３の導出
$2d$ 個のビットが１である符号を ${\bf v}$ とすると、①の $H{\bf v}$ はパリティ検査行列の $2d$ 個の列の和になります。これらの列が１次独立であれば、$H{\bf v}\ne0$ であるため、${\bf v}$ は符号にはなりません。
同様に $2d$ 個未満のビットが１であるも符号にはなりません。従って、${\bf v}$ が符号であるためには、１の数が $2d+1$ 以上である必要があります。
