第四章情報源符号化の基礎

第四章




情報源符号化の基礎
４・１
４・２
４・３
４・４
情報量とエントロピー
エントロピー符号化
音声符号化
画像符号化
４・１
情報量とエントロピー
(1)情報量
(a)コインを投げてその結果が"表"であるという情報
(b)サイコロを振ってその出た目が"偶数"であるという情報
(c)サイコロを振ってその出た目が"４"であるという情報
情報(c)の方が情報(b)より詳しい：量が多い
情報の発生確率 p が小さいほどその情報の情報量は大きい
情報量 = – log2 p
(bit)
(2)エントロピー
H = –  pi log2 pi
N
平均情報量；エントロピー
i=1
N:情報源から発生する事象の数
pi : i 番目の事象の発生確率
p1 = 1 / 2, p2 = 1 / 4, p3 = 1 / 4 の場合の例
H = – 1 log2 1 – 1 log2 1 – 1 log2 1
2
2 4
4 4
4
= 1 + 2 + 2 = 1.5
2 4 4
冗長度；
r = 1 – H / Hm
４・２
号化
エントロピー符
(1)瞬時符号の平均符号長
固定長符号および可変長符号と一意的に復号不可
能な符号(表４・１)
通報発生固定長符号可変長符号一意的に復号不
要素確率
可能な符号C3
C1
C2
F
1/2
00
0
0
C
1/4
10
10
1
R
1/4
11
11
11
L =  pi li
N
平均符号長：
i=1
各符号（Ｃ１、Ｃ２、Ｃ３）に対応する符号の木(図４・１)
葉
F (00)
0
根
0
1
0
1
0
C (10)
1
R (11)
(a) Ｃ１の符号の木
1
F (0)
0
0
C (10)
1
R (11)
(b) Ｃ２の符号の木
1
F (0)
C (1)
1
R (11)
(c) Ｃ３の符号の木
瞬時符号：異なった葉に通報要素が対応している
瞬時符号の平均符号長
2
N
クラフトの不等式：
– li
1
i=1
li = – log2 pi
のとき平均符号長はエントロピーと一致
整数とは限らないので；
このとき
– log2 pi  li < – log2 pi + 1
– li  log2 pi
つまり
2
– li
 pi
H L<H +1
平均符号長はエントロピーより大きい
(2)ハフマン符号化
手順１：通報要素を確率の大きさ順に並べて、節点を割り当てる。
手順２：最小から２個の要素（節点）を枝で結んで新しい要素（節点）
とし、２個の確率の和を新しい要素の確率とする。
このとき最小から２番目の確率を持つ要素が複数ある場合
には任意に選んでよい。
２本の枝に0と1のラベルを与える。この与え方も任意である。
手順３：手順１と手順２を要素が１個になるまで繰り返し、最終的に得
られた確率１の１個の要素に対応する節点を根とする。
ハフマン符号化により得られた符号の木、小数
の数字は確率を示す(図４・２)
0.5 (F)
0
1
0.5
平均符号長：１．５
0
0.25 (C)
1
0.25 (R)

Download Report