情報理論 – 行列とは – 二元体 $\mathbb{F}_2$
情報理論
機械情報システム学科
相馬 正宜
本日の予定
- 第１回から第７回までの授業の概略
- 第８回の授業の一部を再現
本講義の目的
- 雑音のある通信路を使って情報を誤りなく伝える方法を見つける（符号理論）
- その際の通信速度の限界を求める(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)$ を受信ベクトルとして取り出す。
検査行列
情報理論
機械情報システム学科
相馬 正宜