情報理論のバックアップ(No.2)

バックアップ一覧
差分を表示
現在との差分を表示
ソースを表示
情報理論へ行く。
- 1 (2007-11-06 (火) 13:08:14)
- 2 (2008-02-03 (日) 04:48:22)
- 3 (2008-02-03 (日) 08:22:29)
- 4 (2008-02-03 (日) 10:20:10)
- 5 (2008-02-03 (日) 15:49:51)
- 6 (2008-02-03 (日) 21:34:26)
- 7 (2008-02-04 (月) 23:35:20)
- 8 (2008-02-05 (火) 04:20:22)

講義日程-2007年度冬学期

情報理論 †

担当：山本博資教授
1.5単位
- 物工：限定選択
- 数理：限定選択B
- システム：限定選択C
08:30-10:00 工学部六号館 63講義室

出席はとらないが、私語等、授業の邪魔を一切してはいけない。
講義中にはパソコンを一切使用してはいけない。
試験(３時間)で成績評価する。例年２～３割不可るので、やる気がないならとらない方が良い。
レジュメは講義当日もしくは翌週の講義で入手できる。それ以外の日では入手不可能。
レジュメは無断コピー禁止。

Presented by yambi. tzik all blame reserved.

1. 確率変数 $X,Y,Z$ に対して， $H(X)=5$ bits, $H(Y)=3$ bits, $H(XY)=6$ bits, $H(XZ)=8$ bits, $I(X;Y)=3$ bits の関係がある．

(A) $H(Y), H(Y|X), H(X|Y)$ の値は？
- 解
  
  $H(Y)=H(XY)-H(X|Y)=6-2=4$
  
  $H(Y|X)=H(XY)-H(X)=6-5=1$
  
  $H(X|Y)=H(X)-I(X;Y)=5-3=2$

(B) $X$ と $Z$ ， $Y$ と $Z$ それぞれに関して，次のどれが成立するか理由をつけて述べよ．
- 確率的に独立である．
- 確率的に独立でない．
- 判定不能．
- 解
  $H(Z|X)=H(XY)-H(Z)=8-3=5$ より， $H(X)=H(Z|X)$ なので， $X$ と $Z$ は確率的に独立．
  $H(YZ)$ を求める方法がないので $Y$ と $Z$ の独立性は判定不能．（私には判定できないでも可，なのかな．）

2. アルファベット $\mathcal{X}=\{a,b,c\}$ 上の値をとる定常な単純マルコフ過程の遷移確率が次のように与えられている．
現状態 $\backslash$ 次状態 a b c
a 0.5 0.5 0
b 0.4 0 0.6
c 0.4 0.6 0

$P_{X_t}(t), P_{X_t}(b), P_{X_t}(c)$ を求めよ．
- 解
  状態遷移行列を $A$ と書くことにする．
  すると， $(P_{X_t}(a),P_{X_t}(b),P_{X_t}(c))=A^t(P_{X_0}(a),P_{X_0}(b),P_{X_0}(c))$

$A^{\top}$ の固有値1に対応する固有ベクトルは $(32/72,25/72,15/72)^{\top}$ なので， $P_{X_t}(a)=32/72=4/9,\ P_{X_t}(b)=25/72,\ P_{X_t}(c)=15/72$ だと思う．

この情報源のエントロピーレート $H(X)$ を，関数 $h(t)=-t\log_2 t-(1-t)\log_2(1-t$ を用いて表せ．

3. 情報源符号化に関して，次の2つの相違を説明すると共に，それらを比較した時の互いに得失を説明せよ．
- FV符号とVF符号
- Huffman符号と算術符号
- エントロピー符号化とユニバーサル符号化

4. 2つの情報源出力 $X$ と $Y$ を歪を許して情報源符号化する場合を考える．
- 情報源出力 $X$ と $Y$ が共に2値で，その生起確率が $P_X(0)=1-P_X(1)=0.3,\ P_Y(0)=1-P_Y(1)=0.2$ で与えられているものとする．歪をハミング歪で測るものとして， $X$ を平均歪み $D_X=0.2$ まで許して符号化する場合と $Y$ を平均歪み $D_Y=0.1$ まで許して符号化する場合について考える．最適な符号化が行える場合，どちらの方がより多くの符号化レートを必要とするか？

情報源出力 $X$ と $Y$ が，それぞれの分散 $\sigma_X^2=10,\ \sigma_Y^2=3$ を持つ正規分布に従うものとする．歪みを2乗誤差歪みで測るものとして， $X$ を平均歪 $D_X=5$ まで許して符号化する場合と， $Y$ を平均歪み $D_Y=2$ までえ許して符合化する場合を考える．最適な符号化が行える場合，どちらのほうがより多くの符号化レートを必要とするか？

5. 通信路の入力アルファベット $\mathcal{X}$ と出力アルファベット $\mathcal{Y}$ が $\mathcal{X}=\{a_1,a_2,a_3},\ \mathcal{Y}=\{b_1,b_2,b_3\}$ であるとする．このとき，通信路の遷移確率 $P(y|x)$ 次のように与えられる時，それぞれの通信路容量 $C$ を関数 $h(t)=-t\log_2 t-(1-t)\log_2(1-t$ を用いて表せ．

$\backslash$	$b_1$	$b_2$	$b_3$
$a_1$	0.8	0.2	0
$a_2$	0	0.8	0.2
$a_3$	0.2	0	0.8

$\backslash$	$b_1$	$b_2$	$b_3$
$a_1$	0.3	0	0.7
$a_2$	0	1	0
$a_3$	0.7	0	0.3

6. 生成行列 $G$ が次式で与えられるハミング符号がある．
$G=\begin{pmatrix}1&0&0&0&1&1&1\\0&1&0&0&1&1&0\\0&0&1&0&1&0&1\\0&0&0&1&0&1&1\end{matrix}$
- この符号の符号化レート $R$ を求めよ．
- $\bold{y}=(1100010)$ を受信した時，そのシンドロームを求め，この $\bold{y}$ に誤りが含まれているか否かを定めよ．誤りがない場合は「誤りなし」と下記，その理由を説明せよ．また，誤りが含まれている場合は，1ビットの誤りであると仮定してその誤りを訂正せよ．
- このハミング符号に対して，誤り訂正は行わないで誤り検出のみを行うとき，何ビットの誤りまで検出可能か？

7. 次の各説明が正しいか誤っているかを解答せよ．ただし，誤っている場合は，その理由を説明せよ．
- エントロピー $H(X)$ ，微分エントロピー $H_d(X)$ ，相互情報量 $I(X:Y)$ ，相対エントロピー $D(P\| Q)$ などの情報量は全て非負の量である
- FV符号において，長さ2ビットの符号語が1個，長さ3ビットの符号後が4個，長さ4ビットの符号後が3個，長さ5ビットの符号語が4個の符号は，工夫すれば瞬時符号として作れる．
- 誤り訂正符合における最充複合方は，常に最小の複合誤り率を達成できるため，広く用いられている．
- $\{0,1\}$ を100ビット用いると $2^{100}$ の情報を表現できる．しかし，通信路容量 $C=0.1$ を持つ2値対称通信路を通して情報を伝送する場合は，誤りが生じる可能性がある．誤り訂正するためには $2^{100}$ 個全てを符号語として用いることができず，冗長性を持たせてその一部のみ符号語として用いることになる．通信路容量 $C$ が0.1なので，十分余裕を見て $0.001\times 2^{100}$ 個程度の符号後を，ハミング距離が互いにもっとも離れるように配置すれば，十分小さい復号誤り率を達成できる誤り訂正符号が作れる．
- 雑音電力密度 $N_0=$ (Watt/Hz)を持つ加法的白色ガウス雑音通信路に対して，時間連続信号波形 $x(t)$ を用いて情報を伝送する場合を考える． $x(t)$ を用いて最大で $1/2W$ 病後とに独立な情報を送ることができる．したがって，信号電力 $S$ が一定の時，帯域幅 $W$ を大きくすれば送れる情報量が増え，その通信路容量 $C$ も $W$ の増加につれていくらでも大きくできる．

現状態 $\backslash$ 次状態	a	b	c
a	0.5	0.5	0
b	0.4	0	0.6
c	0.4	0.6	0

情報理論 のバックアップ(No.2)

情報理論 †

情報理論のバックアップ(No.2)