情報理論

機械情報システム学科

本講義の目的

雑音のある通信路を使って情報を誤りなく伝える方法を見つける（符号理論）←今回の授業
その際の通信速度の限界を求める(Shannonの通信路符号化定理)
参考資料はここをクリックしてください。

行列とは

　　 $$ \begin{pmatrix} 3 & 4 & 5 \\\ 1 & 3 & 7 \\\ 4 & 2 & 19 \end{pmatrix} $$

$2 \times 2 $ 行列の足し算

$$ \begin{pmatrix} a & b \\\ c & d \end{pmatrix} + \begin{pmatrix} x & y \\\ z & w \end{pmatrix} = \begin{pmatrix} a+x & b+y \\\ c+z & d+w \end{pmatrix} $$

$2 \times 2 $ 行列の掛け算

$$ \begin{pmatrix} a & b \\\ c & d \end{pmatrix} \begin{pmatrix} x & y \\\ z & w \end{pmatrix} = \begin{pmatrix} ax+bz & ay+bw \\\ cx+dz & cy+dw \end{pmatrix} $$

$$ \begin{pmatrix} a & b \\\ c & d \end{pmatrix} \begin{pmatrix} x \\\ y \end{pmatrix} = \begin{pmatrix} ax+by \\\ cx+dy \end{pmatrix} $$

$2 \times 2 $ 行列の転置

$$ \begin{pmatrix} a & b \\\ c & d \end{pmatrix}^T= \begin{pmatrix} a & c \\\ b & d \end{pmatrix} $$

応用問題

$$ \begin{pmatrix} 1&0&1 \end{pmatrix} \begin{pmatrix} 2&1\\ 1&0\\ 1&2 \end{pmatrix} = $$

$$ \begin{pmatrix} 1&-1 \end{pmatrix} \begin{pmatrix} 1&2&1\\ 3&1&1 \end{pmatrix} = $$

二元体 $\mathbb{F}_2$

$\mathbb{F}_2=\{0,1\}$

$\mathbb{F}_2$の演算は、整数として計算した後、

計算結果が偶数なら$0$奇数なら $1$と置き換えればよい。

特に、任意の$x \in \mathbb{F}_2$に対し$x+x=0$が成立する。

二元体上の行列の演算

$$ \begin{pmatrix} 0&1&1\\ \end{pmatrix} \begin{pmatrix} 1&1&0\\ 1&0&0\\ 1&1&1 \end{pmatrix} = $$

通信のベクトル表記

$\mathbb{F}_2^n$: $\mathbb{F}_2$上の$n$次元ベクトル空間

$v_1v_2...v_n$: $n$ビットのデータ

$v=(v_1,v_2,...,v_n)\in\mathbb{F}_2^n$：データのベクトル表記

$e=(e_1,e_2,...,e_n)$: 通信エラーのベクトル表記

データ$v$を送信しエラー$e$が発生した場合、受信されるデータは $r=v+e$で表される。このとき、$v=r+e$、$e=v+r$という関係も成立している($\mathbb{F}_2$上のベクトル空間の特殊性！)。

符号化

写像 $$\varphi :\mathbb{F}_2^k\ni u=(u_1,..,u_k)\to v=(v_1,...,v_n)\in \mathbb{F}_2^n$$ を 符号化と呼ぶ。ただし、$k\leq n$とする。符号化によって得られる$\mathbb{F}_2^n$の部分集合 $$C=\{ \varphi(u);u\in \mathbb{F}_2^k \}$$ を符号と呼び、$C$の要素を 符号語と呼ぶ。

単一パリティ検査符号

$ u=(u_1,...,u_k)\to v=(u_1,...,u_k,\sum_{i=1}^ku_i) $

$ C=\{v=uG;u\in \mathbb{F}_2^k \}$ : 単一パリティ検査符号

$ G= \begin{pmatrix} 1&&&1\\ &\ddots&&\vdots\\ &&1&1 \end{pmatrix} $ : 生成行列

受信側の処理

送信されたパリティ検査符号$v$に対し、受信語$r=v+e=(r_1,...,r_n)$を得る
$r_1+\cdots+r_n=1$ならば誤りが発生したと判定し、 $r_1+\cdots+r_n=0$ならば誤りが発生していないと判定する。
誤りが発生したと判定された場合、送信者にデータの再送を要求する。
誤りが発生していないと判定された場合、受信者はデータ$r$の最初の$k=n-1$ビット $(r_1,...,r_k)$ を受信ベクトルとして取り出す。

検査行列

パリティ検査符号$C$は、検査行列 $H$を使って以下のように表すことができる。

\[ C=\{v\in \mathbb{F}_2^n; vH^T=0 \} \]

ハミング符号

単一パリティ検査符号: 符号語に生じた１個の誤りを検出することができる
ハミング符号: 符号語に生じた１個の誤りを訂正することができる

ハミング符号の検査行列$H$は、零ベクトル以外のすべての$\mathbb{F}_2^m$の列ベクトルを並べて得られる

$m=3$の場合の例:

\begin{equation} H= \begin{pmatrix} 1&0&1&0&1&0&1\\ 0&1&1&0&0&1&1\\ 0&0&0&1&1&1&1 \end{pmatrix} \end{equation}

ハミング符号の生成行列$G$は、検査行列$H$より求めることが出来る

(求め方については資料を参考にしてください。)

$m=3$の場合の生成行列:

\begin{equation} G= \begin{pmatrix} 1&0&0&0&0&1&1\\ 0&1&0&0&1&0&1\\ 0&0&1&0&1&1&0\\ 0&0&0&1&1&1&1 \end{pmatrix} \end{equation}

記号の準備

\begin{equation} {H}^T= \begin{pmatrix} 1&0&0\\ 0&1&0\\ 1&1&0\\ 0&0&1\\ 1&0&1\\ 0&1&1\\ 1&1&1 \end{pmatrix} = \begin{pmatrix} h'_1\\ h'_2\\ h'_3\\ h'_4\\ h'_5\\ h'_6\\ h'_7 \end{pmatrix} \end{equation}

$e_i$: 第$i$成分のみが$1$でそれ以外の成分はすべて0の$7$次元ベクトル

受信側の処理　

受信データ$r$のシンドローム$s=rH^T$を計算する
シンドローム$s$が$s\neq 0$の場合は、$s=h'_j$となる$j$の値を　　$j=1,2,..,7$の中から見つけ、その値を$j=j_0$とする
$r'=r+e_{j_0}$と受信語の誤りを訂正した後、$r'$の最初の$4$ビットを情報ビットとして受け取る

このような誤り訂正を行うことにより、$1$個の誤りが生じた場合でも正しい情報を受け取ることが可能になる。実際、符号語$v=uG$を送信し誤り$e_j$が発生した場合、受信語は $r=v+e_j$となるが、この場合のシンドローム$s$は $s=rH^T=vH^T+e_jH^T=e_jH^T=h'_j$ となり、 $r'=r+e_j=v+e_j+e_j=v$ と誤り訂正することにより符号語$v$が正しく復元されている。