Download

第四回レポート課題
1. 確率分布が表 1 となる情報源を Huﬀman アルゴリズムで符号化した
時の平均符号長 R を求め，圧縮限界と比較せよ．
表 1: X の確率分布と符号語
X
Pr{X = xi }
x1
0.36
x2
0.14
x3
0.13
x4
0.12
x5
0.10
x6
0.09
x7
0.04
x8
0.02
回答例
Huﬀman アルゴリズムより，確率が大きい順に並べた後，一番小さ
い二つのかく率を加算してからまた大きい順に並べると，次の表.2-8
のようになる．
表.2-8 にて，最も小さい二つの確率（確率和）に対応する変数に，
0 と 1 を割り当てると，表.9 の最後の行に示した符号語が得られる
が，x = (xi )8i=1 の符号長は ` = (2 3 3 3 3 3 4 4) となるので，
p = (Pr{X = xi })8i=1 とおくと，平均符号長は
R = `pT = 2.7 [ビット]
となる．
シャノンの符号化定理により，離散無記憶情報源の圧縮限界は H(X)
となるので，
H(X) = − Pr{X = xi } log2 Pr{X = xi } = 2.6209 [ビット]
であり，表.9 で与えられた符号は無歪み圧縮の条件式
R ≥ H(X)
を満たす．
1
x1
0.36
x2
0.14
x1
0.36
x3
0.13
x2
0.14
x1
0.36
表 2: 一回目
x4
x5
0.12
0.10
表 3: 二回目
x3
x4
x5
0.13
0.12
0.10
x6
0.09
x6
0.09
表 4: 三回目
x6 + x7 + x8
x2
x3
0.15
0.14 0.13
x1
0.36
x1
0.36
x4 + x5
0.22
x7
0.04
表 5: 四回目
x6 + x7 + x8
0.15
x7 + x8
0.06
x4
0.12
x2
0.14
x8
0.02
x5
0.10
x3
0.13
表 6: 五回目
x2 + x3 x4 + x5 x6 + x7 + x8
0.27
0.22
0.15
表 7: 六回目
x4 + x5 + x6 + x7 + x8
x1
0.37
0.36
x2 + x3
0.27
表 8: 七回目
x1 + x2 + x3 x4 + x5 + x6 + x7 + x8
0.63
0.37
2. 集合 X = {x1 , x2 , x3 } の入力 X に対して，出力 Y が集合 Y =
{y1 , y2 , y3 } 上の要素となる三元無記憶対称通信路において，xi ,i =
1, 2, 3, が入力された時に yj ,j = 1, 2, 3, が出力される確率を次の通
信路確率行列の (i, j) 番目に記述して表現した場合，この通信路の
容量を求め，通信路容量を達成するための X の確率分布を求めよ．


0.3 0.2 0.5


p(y|x) = 0.5 0.3 0.2
0.2 0.5 0.3
回答例
Pr{X = xi } = pi , i = 1, 2, 3 とおくと，相互情報量は定義および資
2
表 9: 割り当て符号語の変化
x1
X
E(xi )
一回目
二回目
三回目
四回目
五回目
六回目
七回目
0
00
x2
0
0
10
010
x3
x4
0
0
00
00
100
1
1
11
011
x5
x6
1
1
01
01
101
0
0
0
10
10
110
x7
0
10
10
10
110
110
1110
x8
1
11
11
11
111
111
1111
料 p.65 の三行目の式を用いて
I(X; Y ) = H(Y ) − H(Y |X)
3
3
∑
∑
= H(Y ) −
pi
p(yj |xi ) log p(yj |xi )
i=1
j=1
で表される．
p(y|x) の書き方により，p(yj |xi ) は p(y|x) 行列の (i, j) 番目の値な
ので
3
∑
p(yj |xi ) log p(yj |xi )
j=1
= −(0.2 log2 0.2 + 0.3 log2 0.3 + 0.5 log2 0.5)
である．
この i に依存しない値を h3 とおくと
I(X; Y ) = H(Y ) − h3
3
∑
pi = H(Y ) − h3
i=1
より
C = max I(X; Y ) = max H(Y ) − h3
p
p
が得られ，H(Y ) は確率変数 Y が均一の確率分布を持つ時に最大と
なるので，通信路容量は
C = log2 3 − h3 = 0.0995 [ビット]
3
である．
次に，通信路容量を達成する X の分布を求める．表現の便宜上，
p = (p1 , p2 , p3 ) とし，y = (Pr{Y = y1 }, Pr{Y = y2 }, Pr{Y = y3 })
とすると，
y = pp(y|x)
の関係式となるので，Y が均一の確率分布を持つ X の分布は
  

1
0.3 0.2 0.5
 3

(p1 , p2 , p3 ) 0.5 0.3 0.2 =  13 
0.2 0.5 0.3
1
3
となる p を求めることになる．具体的な解き方は線形代数の教科書
に譲るが，結果的には
(
)
(p1 , p2 , p3 ) = 13 13 13
である．
3. 二重バリティ・ビット方式が 1 ビットの誤りを訂正できる事実から
符号語間の最小 Hamming 距離が満たすべき条件を導き，橋本版資
料 (p45) の符号器から送られた次の受信語を復号せよ．
(a) 11110010101111101001
(b) 11110010101111100101
回答例
符号語間の最小 Hamming 距離を dmin とすると，橋本先生のテキス
トの定理 3-2 より，最小距離復号より訂正可能な最大ビット数は
tmax ≤ b
dmin − 1
c
2
を満たす．二重バリティ・ビット方式が 1 ビットの誤りを訂正でき
るので，
dmin − 1
1≤b
c
2
を満たし，この符号の最小 Hamming 距離は３もしくは 4 となる．
橋本先生のテキスト
http://borodin.ee.uec.ac.jp/~hasimoto/lecture/Joho/book_ind.pdf
p.223 にある問題 3-3 の回答を参考
4

Download Report