情報理論

6.符号化法（６章）
1
符号化法
情報源符号化定理（シャノンの第１定理）は、符
号化の理論的限界を与えているだけであり、具
体的な符号化の手法を与えてはいない。すな
わち、ある情報源に対して、エントロピーは平
均符号長の目標にすぎない。
ここでは、具体的な符号化法を与える。
2
代表的符号化法
• シャノン・ファノ符号化（算術符号化）
確率を２進数化して符号化する。
• ハフマン符号化（コンパクト符号化）
最小の平均符号長を持つ符号
（コンパクト符号）を実現する符号。
符号の木の葉から符号を割り当てていく。
3
（シャノンファノ符号化の準備）
ｐ進数
ｐ種類の記号 {0,1, L , p - 1} を基に、
数を表現することができる。小数点以上ｎ桁、小数点以下ｍ
桁のｐ進数
(qn - 1qn - 2 L q0 .q- 1q- 2 L q- m )p
は以下の値を持つ。ただし、 qi Î {0,1, L , p - 1}
n
å
qi ´ p i
i= - m
= qn - 1p n - 1 + qn - 2 p n - 2 + L + q0 p 0
整数部
（小数点の左の
数、１以上）
+ q- 1p - 1 + q- 2 p - 2 + L + q- m p - m 小数部
（小数点の右の
数、１未満）
4
１０進数と２進数
10n - 1
0
10
10 = 1
10
- 1
1
=
10
10- m =
1
10m
(dn - 1dn - 2 L d1d0 .d- 1d- 2 L d- m )10
di Î {0,1, 2, 3, 4, 5, 6, 7, 8, 9}
bi Î {0,1}
(bn - 1bn - 2 L bb
1 0 .b- 1b- 2 L b- m )2
2n - 1
2- 1 =
2
20 = 1
1
2
2- m =
1
2m
5
練習
次の値を求めよ。
（３）
（１）
(43.21)5
(11011.01)2
（２）
（４）
(2102.2)3
(72.3)8
6
１０進数から２進数への変換１
整数部分
入力
D = (dp- 1dp- 2 L d1d0 )10
出力
B = (bq- 1bq- 1 L bb
1 0 )2
ステップ１： D0 = D, i = 0 とおく。
ステップ２：
ステップ３：
Di > 0
bi = Di
である限りステップ３を繰り返す。
(mod 2)
Di + 1 = êëDi / 2ú
û
とし、 i = i + 1
ステップ４：
とする。
B = (bq- 1bq- 1 L bb
1 0 )2
２で割った余り
切捨て
として出力する。
7
開始
D0 = D,
i= 0
偽
Di > 0
真
bi = Di
(mod 2)
Di + 1 = êëDi / 2ú
û
i= i+1
B = (bq- 1bq- 1 L bb
1 0 )2
として出力。
終了
8
例
(54)10
2）５４
2）２７
2）１３
2）６
2）３
2）１
０
を２進数に変換せよ。
・・・０
・・・１
・・・１
・・・０
・・・１
・・・１
2） D 0
2） D1
2） D2
・・・ b0
・・・ b1
2）Dq- 1 ・・・ bq- 2
０・・・ bq- 1
よって、
(54)10 = (110110)2
9
練習
次の１０進数を２進数に変換せよ。
（１）
（２）
(35)10
（３）
(48)10
(63)10
（４）
(41)10
10
１０進数から２進数への変換法が
正しく動作する理由（アルゴリズムの正当性）
A を B
で割った商が
以下の式が成り立つ。
A = Bq + r
q
で余りが
r
であるとき、
,0 £ r < B
(dp- 1 L d0 ) = D = B = (bq- 1 L b0 )
であることに注意する。このとき次式が成り立つ。
êD ú
ê ú=
êë2 ú
û
êB ú
ê ú=
êë2 ú
û
= (bq- 1 L b1 )2
ê(b L b b ) ú
1 0 2ú
ê q- 1
ê
ú
2
êë
ú
û
11
よって、 B = (b b
i
q- 1 q - 2 L
次式が成り立つ。
アルゴリズム
の途中で現れ
る１０進数
bi )2
とおくと、
Di = B i
先頭のq - i 桁
を抜き出した２進
数。（途中では、
求まっていない
ことに注意す
る。）
このような式を
ループ不変条件という。
Di (mod 2)
= B i (mod 2)
= bi
12
１０進数から２進数への変換２
小数部分
入力
D = (0.d- 1d- 2 L d- s + 1d- s )10
出力
B = (0.b- 1b- 2 L b- t + 1b- t )2
ステップ１： D - 1 = D, j = - 1とおく。
ステップ２：
Dj < 1
である限りステップ３を繰り返す。
ステップ３：
bj = D j ´ 2　の整数部分
D j - 1 = D j ´ 2 の少数部分
とし、 j = j - 1
ステップ４：
とする。
B = (0.b- 1b- 2 L b- t + 1b- t )2 として出力する。
13
例
(0.5625)10
を２進数に変換せよ。
2 ´ 0.5625 = 1.125 L 1 + 0.125
2 ´ D- 1 = b- 1 + D- 2
2 ´ 0.125 = 0.25 L 0 + 0.25
2 ´ D- 2 = b- 2 + D- 3
2 ´ 0.25
= 0.5
L 0 + 0.5
2´ 1
= 1.0
L 1 + 0.0
M
2 ´ D- t = b- t + 0.0
よって、
(0.5625)10 = (0.1001)2
小数点に近い方から
順に求まる。
14
練習
次の１０進数を２進数に変換せよ。
（１）
（２）
(0.625)10
（３）
(0.3)10
(0.53125)10
（４）
(0.59375)10
15
練習
小数点の変換アルゴリズムにおけるループ不変条件を示せ。
16
シャノンファノ符号化
入力：情報源（情報源記号の集合とその発生確率）
ìïï s1 , L
S = íp , L
ïîï 1
, sn ü
ïï
, pn ý
ïþ
ï
出力：符号（情報源記号に対応する符号語の集合）
C = {c 1, c 2, L , c n }
ステップ１：発生確率の大きい順に並べる。
（ここでは、添え字でこの順序が見たされるとする。）
ステップ２：各符号語長を次式で求める。
li = éê- log pi ù
ú +
ステップ３：次のような累積確率 pi を求める。切り上げ
i- 1
+
1
p
= 0(i = 1), pi =
+
å
pi (i ³ 2)
j=1
ステップ４：累積確率 pi + を２進数 (pi + )2 に変換する。
+
ステップ５：２進数(pi )2 の上位
li 桁を符号語 c i とする。
17
例
次の無記憶情報源
S
に対して、シャノンファノ符号を構成せよ。
ìï a , b , c , d ü
ïï
ï
S = í
ý
ïï 0.2 , 0.3 , 0.1 , 0.4ïï
î
þ
ステップ１
ìï d , b , a , c ü
ïï
ï
S = í
ý
ïï 0.4 , 0.3 , 0.2 , 0.1ïï
î
þ
\ s1 = d , s 2 = b, s 3 = a, s 4 = c
18
ステップ２
d : - log 0.4 ; 1.322
したがって、
\ l1 = ld = éê- log 0.4ù
ú= 2
L = {l1, l2 , l3 , l4 }
b : - log 0.3 ; 1.737
= {2, 2, 3, 4}
\ l2 = lb = éê- log 0.3ù
ú= 2
a : - log 0.2 ; 2.322
の符号語長を持つ符号
を構成する。
\ l3 = la = éê- log 0.2ù
ú= 3
c : - log 0.1 ; 3.322
\ l4 = lc = éê- log 0.1ù
ú= 4
19
ステップ３
情報源符号語長
記号
d
b
確率
累積確率
l1 = 2 p1 = P (d ) = 0.4 p1+ = 0.0
l2 = 2 p2 = P (b) = 0.3 p + = 0.4
2
+
a
l3 = 3 p3 = P (a ) = 0.2 p3 = 0.7
c
p4 = P (c) = 0.1 p4+ = 0.9
l4 = 4
20
ステップ4
+
1 10
(p ) = (0.0)10 ; (0.00000)2
+
2 10
(p ) = (0.4)10 ; (0.01100)2
+
3 10
(p ) = (0.7)10 ; (0.10110)2
+
(p4 )10 = (0.9)10 ; (0.11100)2
21
ステップ５
d ® 00
b ® 01
a ® 101
c ® 1110
\ C = {c 1, c 2 , c 3 , c 4 }
= {00, 01,101,1110}
22
符号の木
d
0
0
b
1
1
0
1
a
1
0
1
c
平均符号長
L = 2 ´ 0.4 + 2 ´ 0.3 + 3 ´ 0.2 + 4 ´ 0.1
= 2.4
23
練習
次の情報源ジャンをシャノンファノの符号化法に従って
符号化せよ。
ìï グー , チョキ , パーü
ïï
ï
ジャン = í
ý
ïï 0.35 , 0.25 , 0.4 ïï
ïþ
îï
また、得られた符号に対する符号の木を示し、平均符
号長を求めよ。
24
シャノンファノ符号化法の平均符号長
-
1 £ i £ n に対して、
li = éê- log pi ù
ú
どこか
で見た
式
であるが、これは次式を満たす。
- log pi £ li < - log pi + 1
したがって、平均符号長は次式で求められる。
n
å
i= 1
n
pi log pi £
å
i= 1
n
pili < -
å
n
pi log pi +
i= 1
å
pi
i= 1
\ H (S ) £ L < H (S ) + 1
25
累積確率
累積確率
確率
１
１
p3+
p1
p2+ p2
p2
p1+
s1 s 2
面積が１
情報源
記号
p1 p1
s1 s 2
高さが１に漸近
する。（一種の
積分に対応。）
情報源
記号
26
シャノンファノ符号の非特異性
シャノンファノ符号化法で構成された符号
は非特異符号である。
証明
符号語長の選び方より、次式が成り立つ。
 log pi  li   log pi  1
li
li 1
2  pi  2
27
一方、

i
記号 si 1 の生成確率

i 1
p  p  pi 1 に注意する。
累積確率の
i
番目
累積確率の
i  1 番目
よって、２進数表現して、次式が成り立つ。
 p   p    p 

i 2
2
log pi1
2
 li1

i 1 2
i 1 2
第 li 1 桁で必ず異なることを
意味する。
Q.E.D
28
（ハフマン符号化の準備）
縮退情報源
情報源 S 対して、
S の２つ以上の情報源記号 si , s j  S を一つにまとめた
情報源を元の情報源の縮退情報源という。すなわち、
 s1 ,
S 
 p2 ,
 s1 ,

S 
 p1 ,
ここで、 * s
k

,
si
,
sj
,
,
,
pi
,
pj
,
,
,
*
sk
,
,
,
*
pk
,
,
 {si , s j }
S  S 1
*
sn 

pn 
sn 

pn 
pk  pi  p j
29
例
次の情報源の縮退情報源をいくつか示せ。
ìï a , b , c , d ü
ïï
ï
S = í
ý
ïï 0.2 , 0.3 , 0.1 , 0.4ïï
î
þ
解）
ìï A
S 1- = ïí
ïï 0.5
î
ìï a
S 2 = ïí
ïï 0.2
î
d ü
ïï
ý, A = {a, b}
, 0.1 , 0.4ïï
þ
, B , d ü
ïï
ý, B = {b, c}
, 0.4 , 0.4ïï
þ
,
c
,
ìï C , b , d ü
ïï
ï
S = í
ý,C = {a, c}
ïï 0.3 , 0.3 , 0.4ïï
î
þ
3
30
練習
次の情報源に対して、２記号を１記号に縮退して得られる情報源
をすべて示せ。
ìï a
,
b
,
c
, d ü
ïï
ï
S = í
ý
ïï 0.15 , 0.25 , 0.05 , 0.55ïï
î
þ
31
ハフマン符号化
入力：情報源（情報源記号の集合とその発生確率）
ìïï s1 , L
S = íp , L
ïîï 1
, sn ü
ïï
, pn ý
ïþ
ï
出力：符号（情報源記号に対応する符号語の集合）
C = {c 1, c 2, L , c n }
ステップ１： k = 0
ìï s10 , L
とし、 S 0 = S = ïí 0
ïï p1 , L
îï
ここで、 si0 = si , pi0 = pi
, sn0 ü
ïï
0ý
, pn ïï
ï
þ
とする。
(1 £ i £ n )
ステップ2：発生確率の大きい順に並べる。
（添え字の順序をこの順序とする。）
32
ステップ３：縮退情報源
ìï s1k , L
ï
S k = ïí k
ïï p1 , L
îï
, snk - k üïï
ïý
, pnk - k ïï
þï
k
k
に対して、確率の小さい２つの情報源記号 sn - k , sn - k - 1 に対して、
対応する符号の末尾に０と１を割り当てる。さらに、 snk - k , snk - k - 1 を
縮退して、新たな縮退情報源
Sk+1
ìï s1k + 1 , L
ï
= ïí k + 1
ïï p1
, L
îï
, snk -+ k1- 2
,
, snk -+ k1- 2
,
ü
ïï
ïý
* k+1
sn - (k + 1) ïï
ï
þ
* k+1
n - ( k + 1)
s
を作成する。
ここで、
sik + 1 = sik , pik + 1 = pik
* k+ 1
n - ( k + 1)
s
*
(1 £ i £ n - k - 2)
= {snk - k - 1, snk - k },
pnk -+ (1k + 1) = pnk - k - 1 + pnk - k
(i = n - k - 1)
33
ステップ４： k < n - 1 である限り、 k = k + 1
ステップ２に戻る。
として
34
ハフマン符号化例
次の符号のハフマン符号を与える。
ìï a , b , c , d ü
ïï
ï
S = í
ý
ïï 0.2 , 0.3 , 0.1 , 0.4ïï
î
þ
符号の木を葉から構成していくと分かりやすい。
B = {b, A }(0.6)1
d (0.4)
1
b(0.3)
a(0.2)
c(0.1)
S 0 = {d, b, a, c}
0
1
A = {a, c}(0.3)
0
0
S 1 = {d, b, A }
35
S 2 = {B , d }
前のスライドの符号の木より、
d® 0
b ® 11
a ® 101
c ® 100
平均符号長
L
は、次のように計算される。
L = 0.4 ´ 1 + 0.3 ´ 2 + 0.2 ´ 3 + 0.1 ´ 3
= 1.9
36
練習
次の符号をハフマン符号化し、
符号の木、平均符号長、効率を求めよ。
ìï a
,
b
,
c
, d ü
ïï
ï
S = í
ý
ïï 0.15 , 0.25 , 0.05 , 0.55ïï
î
þ
37
コンパクト符号
（定義）コンパクト符号
情報源に対して、符号語長が最短となる符号を
コンパクト符号という。
コンパクト符号であっても、効率が１
になるとは限らない。効率が１なら明
らかにコンパクト符号である。
38
ハフマン符号のコンパクト性
ハフマン符号は、コンパクト符号である。
ハフマン符号化で得られる符号は、１
通りとは限らない。しかし、どのような
ハフマン符号もコンパクトとなる。
この証明のために、次の補題を示す。
39
補題
情報源 S i の最小の生成確率を持つ２記
号を縮退して得られる情報源をSi 1 とする。
情報源 S i のハフマン符号を Ci とし、情
報源 Si 1 のハフマン符号をCi+ 1 とする。こ
のとき、 Ci+ 1 がコンパクト符号ならば、 Ci
もコンパクト符号である。
証明
Ci の平均符号長を Li とし、
Ci+ 1 の平均符号長を Li+ 1 とする。
40
まず、符号の木の経路長が最長の葉は２つある。
（もし、経路長が最長の葉が１つだけなら、さらに短くできる。）
Ci
Ci
この２つの葉に発生確率最小の２記号 si , s j  Si を割り当
てる。（もし、発生確率が最小以外の記号を割り当てるとより短い
平均符号長が得られる。）
Ci
si
sj
Li =
å
pk lk
sk Î Si
£
å
sk Î Si
pk lk - pili - p j l j + p'i li + p' j l j
41
si
sj
Ci+ 1
Li+ 1 = Li - pili - p j li + ( pi + p j )( li - 1 )
= Li - pi - p j
今、 Si 1 に対する任意の符号の平均符号長を L'i+ 1 と表す。
このとき、 Li+ 1
のコンパクト性より、以下が成り立つ。
Li+ 1 £ L'i+ 1
42
同じ値を両辺から引いているだけ。
\
Li+ 1 - pi - p j £ L'i+ 1 - pi - p j
\
Li £ L'i
情報源
したがって、
Si 1
Ci
の平均符号長と等しい。
もコンパクト符号になる。
Q.E.D
43
（ハフマン符号のコンパクト性の証明）
基礎
i = n- 2
のとき。
このとき、縮退情報源の記号の数は、
Si = Sn- 2 = 2
であり、ハフマン符号は明らかにコンパクト符号である。
帰納
に対して、ハフマン符号
n - 2 ³ i > 0 のすべての i
Ci
Si
が情報源
のコンパクト符号だと仮定する。（帰納法の
仮定）
先の補題より、
Ci がコンパクト符号ならば、 Ci- 1 もコンパクト符号である。
したがって、 S0 をハフマン符号化した C0 もコンパクト符
号である。
Q.E.D 44

Download Report