情報理論 第11回 情報源符号化 練習問題解答例
練習問題1
例2の符号で、情報源事象系が
X
=
x
a
x
b
x
c
x
d
0.25
0.25
0.25
0.25
である場合の平均符号長を求めよ。また、この場合に例1と例2のどちらが効率が良いか述べよ。
a, b, c, dに対応する符号語の長さはそれぞれ1, 2, 3, 4なので、平均符号長は
L
=
(
1
+
2
+
3
+
4
)
×
0.25
=
10
×
0.25
=
2.5
となる。これは例1の平均符号長 2 よりも大きいので、
例1の方が効率が良い
。
練習問題2
例2の符号で、情報源事象系が
X
=
x
a
x
b
x
c
x
d
0.8
0.1
0.05
0.05
である場合の平均符号長を求めよ。また、この場合に例1と例2のどちらが効率が良いか述べよ。
a, b, c, dに対応する符号語の長さはそれぞれ1, 2, 3, 4なので、平均符号長は
L
=
1
×
0.8
+
2
×
0.1
+
(
3
+
4
)
×
0.05
=
0.8
+
0.2
+
0.35
=
1.35
となる。これは例1の平均符号長 2 よりも小さいので、
例2の方が効率が良い
。
練習問題3
a～hの8文字を扱えるように例1, 例2を拡張した符号を考え、情報源事象系が
X
=
x
a
x
b
x
c
x
d
x
e
x
f
x
g
x
h
1
-
7
p
p
p
p
p
p
p
p
である場合の例1(拡張)、例2(拡張)の平均符号長を求めよ。また、例2(拡張)の方が例1(拡張)よりも効率が良くなる条件を記述せよ。
例1を拡張したものではすべての符号語の長さが3になるので、平均符号長も3。
一方、例2を拡張したものではa～hに対応する符号語の長さは1～8になるので、平均符号長は
L
=
1
×
(
1
-
7
p
)
+
(
2
+
3
+
4
+
5
+
6
+
7
+
8
)
×
p
=
1
-
7
p
+
35
p
=
1
+
28
p
となる。これが例1の平均符号長 3 よりも小さくなる条件は
1
+
28
p
<
3
28
p
<
2
p
<
1
14
つまり、
p
が
1
14
より小さければよい
。
書く必要はないが、拡張版の例1, 例2の符号は以下のようになる。
シンボル
符号語
a
000
b
001
c
010
d
011
e
100
f
101
g
110
h
111
シンボル
符号語
a
1
b
01
c
001
d
0001
e
00001
f
000001
g
0000001
h
00000001
練習問題4
以下の符号の符号の木を描け。
シンボル
符号語
a
1
b
10
c
100
d
1000
この図は「0の枝を右上に、1の枝を右下に」向けて描いてあるが、どちらにするかには特にルールはない。
もっとも、「0, 1のどちらを上にするか」の規則が混在していると混乱しがちなので、ひとつの図の中でははそろえた方がよい。
資料の説明にある通り、この符号では途中の節点にもシンボルが割り当たる。