1 0/1, a/b/c/ {0, 1} S = {s 1, s 2,..., s q } S x = X 1 X 2 X 3 X n S (n = 1, 2, 3,...) n n s i P (X n = s i ) X m (m < n) P (X n = s i X n 1 = s j )

通信とネットワーク

(Communication and Network)

第１０回，第１１回：情報源符号化 内容

•

一意復号可能な符号

•

瞬時復号可能な符号

•

最適符号

•

ハフマン符号

•

情報エントロピー

1

_定義

•

シンボル：情報を表す記号：

0/1, a/b/c/

· · ·

，

•

アルファベット：シンボルの集合：

{0, 1}

，英語のアルファベット

•

情報源アルファベット：情報源が出力するアルファベット  ここでは，有限集合

S =

{s

₁

, s

₂

, . . . , s

_q

}

を考える。

•

情報源

S

：シンボル列

x = X

₁

X

₂

X

₃

· · ·

を出力する。  

X

_n

∈ S (n = 1, 2, 3, . . .)

は，

n

番目のシンボルを表す確率変数

•

記憶のない情報源：  

n

番目に出力されるシンボルが

s

_iである確率

P (X

_n

= s

_i

)

が，過去の   シンボル

X

_m

(m < n)

に依存しない。

•

記憶のある情報源の例：マルコフ情報源  直前のシンボルに応じて，シンボルを出力する確率が定まる。  

P (X

_n

= s

_i

|X

_n−1

= s

_j

)

が与えられる。

 

p

_i，

p

_ij は確率であるので，次式が成立する。

p

_i

≥ 0

p

_ij

≥ 0

q

∑

i=1

p

_i

= 1

q

∑

i=1

p

_ij

= 1

•

情報源の例：

–

_{サイコロ：情報源アルファベットは，サイコロの目の数。}

–

_{天気：情報源アルファベットは，}

{

晴れ，曇り，雨，雪

}

–

_{本：情報源アルファベットは，本に使われている文字の全体。}

•

符号化：情報源のシンボル列を，通信路の特性に合わせたシンボル列 に変換する。

•

符号シンボル：情報源を符号化するためのシンボル

•

符号アルファベット：符号シンボルの全体

T =

{t

₁

, . . . , t

_r

}

•

基数

r

：符号シンボルの数

•

2

_元符号：

2

種類のシンボルを使う。  

T = Z

₂

≡ {0, 1}

として，最も広く用いられている。

• 3

元符号：

3

種類のシンボルを使う。  モールス信号，符号と符号の間に区切りの無音部分がある。

⇒ 3

元符号。

•

符号化：情報源シンボルを

(

複数の

)

符号シンボルで表す。

•

符号語

w

：符号シンボルからなる有限列

•

符号語長

|w|

：

w

に含まれる符号シンボルの数

•

ϵ

：長さ

0

の空語

(

これも符号語

)

とみなす。

•

T

n：長さ

n

の符号語の全体

•

T

∗：符号語の全体

•

T

+

= T

∗

− {ϵ}

：空語を除いた符号語の全体

T

∗

=

∪

T

n

•

符号

C : S → T

+

(S

から

T

+への写像

)

• w

i

=

C(s

i

)

ならば，符号語

w

iは情報源シンボル

s

iを表していると考え ることができる。

•

誤解が生じないときは，

C

で情報源シンボルを表す符号語全体の集合 を表す。

C = {w

1

, w

2

, . . . , w

q

}

• C

は

S

の要素列の集合

S

∗の写像へ拡張できる。

C : s = s

i₁

s

i₂

s

i₃

· · · s

i_n

7→ t = w

i₁

w

i₂

w

i₃

· · · w

i_n ただし，

w

_in

=

C(s

_in

)

である。

•

この写像の値域は，以下のようになる。

C

∗

=

{w

_i1

w

_i2

w

_i3

· · · w

_in

| w

_ij

∈ C, n ≥ 0}

• l

i

=

|w

i

|

：符号長

•

L(

C)

：符号

C

の平均符号長：

L(

C) =

q

∑

i=1

p

_i

l

_i

1.1

_{符号化の目的}

•

処理が容易で一意な復号

t

7→ s

_{が存在する。}

•

平均符号長

L

(

C)

_{が小さい。} 符号の例：サイコロの目が

i (i = 1, 2, 3, 4, 5, 6)

を

2

元符号で表す。

• s

i

= i

• p

i

=

1₆

• w

1

= 1, w

2

= 10, w

3

= 11, w

4

= 100, w

5

= 101, w

6

= 110

• s = s

1

s

2

s

5

7→ t = 110101

•

平均符号長：

1

6

(1 + 2 + 2 + 3 + 3 + 3) =

7

3

•

一意復号可能か？ 

1.2

_{一意復号可能な符号}

•

一意復号可能：

(

略して

u.d.

と書く。

)

C : S

∗

→ T

∗が単射であること。すなわち，

2

つの符号語の列が

u

₁

· · · u

_m

= v

₁

· · · v

_n

(u

₁

, . . . , u

_m

, v

₁

, . . . , v

_n

∈ C)

を満たすならば，

m = n

かつ

u

_i

= v

_iであることである。

•

定理：符号語長がすべて同じならば，

C

は一意復号可能

•

サイコロの場合で符号長が等しい例：

w

₁

= 001, w

₂

= 010, w

₃

= 011, w

₄

= 100, w

₅

= 101, w

₆

= 110

•

ブロック符号：符号語の長さがすべて等しい符号

•

長さが同じではなくても，一意復号可能な符号は存在する。

w

₁

= 0, w

₂

= 01, w

₃

= 011, w

₄

= 0111, w

₅

= 01111, w

₆

= 011111

例：

t = 001011

1.2.1

_{サーディナス・パターソンの定理}

•

一意復号可能な符号の条件を考える。次の符号語の集合を定義する。

C

0

=

C

C

n

=

{w ∈ T

+

| uw = v, u ∈ C, v ∈ C

n−1

or u

∈ C

n−1

, v

∈ C}

C

_∞

=

∞

∪

n≥1

C

_n

–

C

₁

=

{w ∈ T

+

| uw = v, u, v ∈ C}

–

最終的には

C

_nは，周期的な集合になる。

–

C = {1, 10, 11, 100, 101, 110}

の場合  

C

₁

=

{0, 1, 00, 01, 10}

 

C

₂

=

{0, 1, 00, 01, 10}

 

C

_∞

=

{0, 1, 00, 01, 10}

–

C = {0, 01, 010, 111}

の場合

–

C = {0, 01, 011, 0111, 01111, 011111}

の場合  

C

₁

=

{1, 11, 111, 1111, 11111}

 

C

₂

= ϕ

 

C

₃

= ϕ

 

C

_∞

=

{1, 11, 111, 1111, 11111}

•

サーディナス・パターソンの定理：  符号が一意復号可能であるための必要十分条件は，次式が成立する こと。

C

_∞

∩ C = ϕ

•

証明は参考書を見ること

(

本で

5

ページ程度必要

)

。

• C = {1, 10, 11, 100, 101, 110}

は，一意復号不可能

• C = {0, 01, 011, 0111, 01111, 011111}

は，一意復号可能

1.3

_{瞬時復号可能}

• w

1

= 0, w

2

= 01, w

3

= 11

という符号を考える。

• C

1

=

{1}

，

C

2

=

{1}

，

C

∞

=

{1}

サーディナス・パターソンの定理より一意復号可能  

0111110

· · ·

は

s

₂

s

₃

s

₃

· · ·

 

01111110

· · ·

は

s

₁

s

₃

s

₃

s

₃

· · ·

連続する

1

の数が分かってから，はじめの

1

が

01

か

11

に属するかわかる。

• w

1

= 0, w

2

= 10, w

3

= 11

という符号を考える。 符号化されたものを先頭から見ていけば，すぐに符号語がわかる。

0101111100

· · ·

は

s

₁

s

₂

s

₃

s

₃

s

₂

s

₁

· · ·

•

瞬時復号可能：  任意の符号語列

w

_i1

w

_i2

· · · w

_in に対して，その符号語列で始まる任意 の符号列

w

w

· · · w

· · ·

(

符号列であるので，符号語の並びでなくて

•

瞬時符号：瞬時復号可能な符号

•

語頭符号：どの符号語

w

_iも他の符号語

w

_j

(j

̸= i)

の語頭

(

先頭部

)

になっ ていな符号。

⇒ C

1

= ϕ

となる。

•

定理：  ある符号が瞬時復号可能であるための必要十分条件は，その符号が 語頭符号

(

C

₁

= ϕ)

となることである。

瞬時符号

クラフトの不等式 基数

r

の符号において，符号語長

l

₁

, l

₂

, . . . , l

_qの瞬時符号が存在するため の必要十分条件は， q

∑

i=1

r

−li

≤ 1

を満たすことである。

(

証明の概略

)

•

一般性を失うことなく，

l

₁

≤ l

₂

≤ · · · ≤ l

_qを仮定する。

• l = l

q

(l

iの最大値

)

とする。高さ

l

の木を考えれば良い。

•

符号長

l

_iの符号から降って行ったときに存在する葉

(

木の先端

)

の数は，

r

l−li_{個である。}

•

符号語を木の節点に割り当てるとき，その下の接点に符号語を割り当 てないようにする。

•

すなわち，２つの符号語から枝を伝わって葉の方へ降って行ったとき に，葉が両者で重ならないようにする。

• l

1

≤ l

2

≤ · · · ≤ l

q で， q

∑

i=1

r

l−li

≤ r

l だから，符号語を左から順番に割り当てることができる。

•

逆に，

∑

q_i=1

r

−li

_{> 1}

_ならば， q

∑

i=1

r

l−li

_{> r}

l となり，符号語の下にある葉が重なるので，瞬時復号不可能になる。

1.3.2

_{マクミランの不等式}

•

瞬時符号

⇒

一意復号可能

•

「一意復号可能」だけならば，符号長に関する条件が，クラフトの不 等式よりもゆるくなるか？

⇒

そうはならない。 マクミランの不等式 基数

r

の符号において，符号語長

l

₁

, l

₂

, . . . , l

_qの一意復号可能符号が存在 するための必要十分条件は， q

∑

i=1

r

−li

≤ 1

を満たすことである。

(

クラフトの不等式と同じ

)

• l = max(l

1

, l

2

, . . . l

q

)

• m = min(l

1

, l

2

, . . . l

q

)

•

また，

K

を次のように定義する。

K =

q

∑

i=1

r

−li

• K

n

_(K

_の

_n

_乗

₎

_{を展開すれば。その各項は次の形で書ける。}

r

−li1

× r

−li2

× · · · × r

−lin

_{= r}

−j ここで，

j = l

_i1

+ l

_i2

+

· · · + l

_in

• m ≤ l

i₁

, l

i₂

, . . . , l

i_n

≤ l

より，

mn

≤ j ≤ ln

となる。

•

従って，

K

nは次の形で書くことができる。

K

n

=

ln

∑

j=mn

N

_j,n

r

−j

• N

j,nは，符号長が

j

となる

n

個の符号語の列の数と等しい。すわなち，

n

個の符号語の列

w

_i1

w

_i2

· · · w

_inで，この列の符号シンボルの総数が

j

個 であるものの数となる。

•

このとき，符号シンボルの数が

j

であるから，その符号列は

r

j 個以上 のものを表すことができないので，次式が成立する。

N

_j,n

≤ r

j

•

従って，次式が成立する。

K

n

=

ln

∑

i=mn

N

_j,n

r

−j

≤

ln

∑

i=mn

r

j

r

−j

=

ln

∑

i=mn

1 = (l

− m)n + 1

•

上式は

n

を変化させると，

K

nは指数関数的に，右辺は

1

次関数的に変 化する。

• K > 1

の場合，

n

を大きくすると上式が成立しなくなる。

2

_{ハフマン符号}

• w

1

, w

2

, . . . , w

q：符号語

• l

1

, l

2

, . . . , l

q：

w

1

, w

2

, . . . , w

q の符号長

• p

1

, p

2

, . . . , p

q：

w

1

, w

2

, . . . , w

q の出現確率

• L(C)

：平均符号長

L(

C) =

q

∑

i=1

p

_i

l

_i

•

例：

p

₁

= 1/2

，

p

₂

= 1/4

，

p

₃

= 1/8

，

p

₄

= 1/8

符号

C

₁を

w

₁

= 00

，

w

₂

= 01

，

w

₃

= 10

，

w

₄

= 11

とする。

L(

C

₁

) =

1

2

× 2 +

1

4

× 2 +

1

8

× 2 +

1

8

× 2 = 2

符号

C

₂を

w

₁

= 0

，

w

₂

= 10

，

w

₃

= 110

，

w

₄

= 111

とする。

L(

C

₁

) =

1

2

× 1 +

1

4

× 2 +

1

8

× 3 +

1

8

× 3 = 1.75

•

最適符号

(

_{コンパクト符号}

)

：

r

と

p

_iが与えられたとき，平均符号長が最小になる一意復号可能な符号

•

定理

(

最適符号の存在

)

：  任意の情報源

S

は，任意の整数

r

に対して，最適な

r

元符号を持つ。

(

証明は，平均符号長がある値以下の符号の種類が有限であることを使 って行う。詳細は参考書を参照すること。

)

2.1

2

_{元ハフマン符号}

• 2

元符号：符号アルファベット

T = Z

₂

=

{0, 1}

•

情報源

S

：  シンボル：

s

₁

, s

₂

, . . . , s

_q−2

, s

_q−1

, s

_q  出現確率：

p

₁

, p

₂

, . . . , p

_q−2

, p

_q−1

, p

_q

• s

′を

s

_q−1と

s

_qをまとめたシンボル

(s

′

= (s

_q−1

∨ s

_q

))

とする。

•

縮退情報源

S

′は次のようになる。  シンボル：

s

₁

, s

₂

, . . . , s

_q−2

, s

′  出現確率：

p

₁

, p

₂

, . . . , p

_q−2

, (p

_q−1

+ p

_q

)

• S

′の符号

C

′

=

{w

₁

, w

₂

, . . . , w

_q−2

, w

′

}

が与えられたとき，

S

の符号

C = {w

1

, w

2

, . . . , w

q−2

, w

′

0, w

′

1

}

を与えることができる。

• C

′が瞬時符号ならば，

C

も瞬時符号である。

2

_{元ハフマン符号の構成}

1.

S

(0)

=

S

，

k = 1

とおく。

2. k == q

ならば縮退した情報源のシンボル数が

1

になったので，符号

C

(q)

_{= ϵ}

_{を割り当て，}

_{goto 5}

_{。そうでなければ，次へ進む。}

3.

S

(k)のシンボルの中で，出現確率が最も低い

2

つのシンボルを縮退させ た情報源

S

(k+1)を作成する。

4. k = k + 1

，

goto 2

5. k == 0

ならば終了。そうでなければ，次へ進む。

6.

S

(k−1)を縮退して

S

(k)を構成した時に作成したシンボルに対する

C

(k) の符号語を

w

(k)とする。縮退する前の

2

つのシンボルに符号語

w

(k)

0

と

w

(k)

1

を割り当て，

S

(k−1)の符号

C

(k−1)を作成する。

7. k = k

− 1

，

goto 5

2.1.1

_{ハフマン符号の構成例}

2.1.2

_{縮約と平均符号長}

1. p

(k)：

S

(k−1)から

S

(k)に縮退するときに作成したシンボルの出現確率。

2. p

(k_i −1)，

p

(k_j −1)：縮退する前の

2

つのシンボルの出現確率。 次式が成立する。

p

(k)

= p

(k_i −1)

+ p

(k_j −1)

3. L(

C

(k−1)

)

と

L(

C

(k)

)

の差は，

w

(k−1)に

0

と

1

を付加したために生じる。

L(

C

(k−1)

)

− L(C

(k)

) = p

(k)

2.1.3

2

_{元ハフマン符号の最適性} 符号語

w

₁と

w

₂が兄弟：  ある符号語

w

に対して，

w0

，

w1

という形をしている。 補題 すべての情報源

S

は，符号長が最大の符号語が兄弟であるような，

2

元 最適符号

D

をもつ。

(

証明

)

一意復号可能な符号に対して，符号長がすべて等しい瞬時復号可能な符 号が存在するため，以下，すべての符号を瞬時復号可能としても一般性 を失わない。定理

(

最適符号の存在

)

より，

S

に対する

2

元最適符号

D

が存 在する

(1

つとは限らない

)

。符号

D

のすべての符号長の和を

σ(

D)

で表す。

σ(

D) =

∑

i

l

_i いま，その最適符号の中で

σ(

D)

が最小になるものを選び出し，

D

₀とお く。

D

₀の符号長が最大の符号語は，それより長さが

1

短い符号語

w

に対 して，

w0

あるいは

w1

という形をしている。このとき，この

2

つのうちの どちらかの符号語が

D

₀の中に存在しないとする。

D

は瞬時復号可能であ

るから，符号語

w

は

D

₀に含まれない。

w0

あるいは

w1

の一方しか存在し ないならば，それを

w

に置き換えても瞬時復号可能である。その符号を

D

₀′ とすれば，

D

′も最適符号で，

σ(

D

₀′

) = σ(

D

₀

)

− 1

となる。これは，

D

₀ の選択に矛盾する。 定理

(

ハフマン符号は最適符号

)

 

2

元ハフマン符号は最適符号である。

(

証明

)

ハフマン符号が瞬時符号であることは構成から明らか。最適符号である ことをシンボル数

q

の数学的帰納法で示す。 シンボル数が

1

のとき，

C = {ϵ}

，

L(

C) = 0

で最適。 シンボル数が

q

− 1

のときにハフマン符号は最適符号であるものとする。 シンボル数が

q

のときのハフマン符号を

C

とし，

s

₁

, . . . , s

_q−2

, s

_q−1

, s

_q

(

シ ンボルの出現確率が降順

)

を縮約して，

s

₁

, . . . , s

_q−2

, (s

_q−1

∨s

_q

)

を得る。そ

上の補題により，

C

と同じ情報源に対して，最長な符号語が兄弟の関係 にある最適な符号

D

∗が存在する。その最長な兄弟の関係にある

2

つの符 号語がシンボル

s

_i と

s

_j

(i < j)

を表しているものとする。ここで，

s

_iと

s

_q−1 で，

s

_j と

s

_q で表す符号を入れ替えた符号

D

を考える。

l

_{i を}

D

∗ _の各 符号の符号長とする。

s

_i と

s

_j の選び方から

l

_i

≥ l

_q−1，

l

_j

≥ l

_q が成立し

(l

_i

, l

_j

, l

_q−1

, l

_q ともに

D

∗の符号長であることに注意

)

，ハフマン符号の構 成法より

p

_i

≥ p

_q−1

, p

_j

≥ p

_q が成立する。従って，次式が成立する。

L(

D

∗

)

− L(D)

= p

_q−1

l

_q−1

+ p

_q

l

_q

+ p

_i

l

_i

+ p

_j

l

_j

− (p

_q−1

l

_i

+ p

_q

l

_j

+ p

_i

l

_q−1

+ p

_j

l

_q

)

= (p

_q−1

− p

_i

)(l

_q−1

− l

_i

) + (p

_q

− p

_j

)(l

_q

− l

_j

)

≥ 0

従って，

L(

D) ≤ L(D

∗

)

より，

L(

D)

も最適符号で，兄弟の関係にある最 長な符号語が

s

_q−1と

s

_q を表している符号になる。

D

の

s

_q−1と

s

_q を縮約した符号を

D

′とおく。

L(

D) − L(D

′

) = p

_q−1

+ p

_q

= L(

C) − L(C

′

)

が成立する。帰納法の過程から

C

′は最適符号であるから，

L(

C

′

)

≤ L(D

′

)

となり，

L(

C) ≤ L(D)

となる。

D

は最適符号なので，

C

も最適符号になる。

2.2

r

_{元ハフマン符号}

•

基本的には，

2

元ハフマン符号と同じ。

•

もっとも出現確率が低い

r

個のシンボルを縮約して，

1

つのシンボル

s

′ を作成する。

• s

′に対する符号語

w

′が定まった場合，もとのシンボルに対する符号語 を，それぞれ，

w

′

0, w

′

1, . . ., w

′

r

とする。

• 1

回の縮約について，

r

− 1

個シンボルが減少する。

•

最後に

r

個のシンボルが残るようにしないと効率が下がる。

•

最初に，シンボル数が

n(r

− 1) + 1

_{個になるように，仮想的に出現確率}

0

_{のシンボルを追加する}

(n

はある整数

)

。  例：

r = 3, p

₁

= 0.4, p

₂

= 0.3, p

₃

= 0.2, p

₄

= 0.1

とする。 仮想的に

1

つのシンボル

s

₅を追加し，

p

₅

= 0

とする。

w

₁

= 0, w

₂

= 1, w

₃

= 20, w

₄

= 21

となる。

3

_{エントロピー}

3.1

_定義

•

I(s

_i

)

：情報源シンボル

s

_iがもつ情報の量

• I(s

i

)

に対する要求

– I(s

_i

)

は，

s

_iの生起確率

p

_iの単調減少関数

– p

_i

= 1

のとき

I(s

_i

) = 0

–

シンボルの生起が独立

(P (s

_i

s

_j

) = P (s

_i

)P (s

_j

))

のとき

I(s

_i

s

_j

) = I(s

_i

) + I(s

_j

)

•

上の条件を満たすものは，次のように求まる。

I

_r

(s

_i

) =

− log

_r

(p

_i

)

r

は対数の基数である。

• r = 2

としたときの情報量には，単位

[bit]

を用いる。

•

エントロピー：情報源の平均情報量

H

_r

(

S) =

q

∑

i=1

p

_i

I

_r

(s

_i

) =

−

q

∑

i=1

p

_i

log

_r

p

_i

•

基数を明示しない場合は以下のようになる。

H(

S) =

q

∑

i=1

p

_i

I(s

_i

) =

−

q

∑

i=1

p

_i

log p

_i

• p = 0

のとき，

p log p = 0

とする。

•

H(p)

：情報源

S

が，確率

p

と

1

− p

の

2

つのシンボルを出力する場合の エントロピー

H(

S) = H(p) ≡ −p log p − (1 − p) log(1 − p)

•

次式が成立する。

3.2

_{エントロピー関数の性質} エントロピー関数

H

_r

(

S) = −

∑

i

p

_i

log

_r

p

_i

• H

r

(

S) ≥ 0

となる。  

H

_r

(

S) = 0

となるための必要十分条件は，ある

i

に対して

p

_i

= 1

であ る。

•

補題：  すべての

x > 0

に対して，

ln x

≤ x − 1

となる。等号が成立する必要 十分条件は

x = 1

である。

(ln x = log

_e

x)

•

証明は，右辺−左辺を微分して証明する。

定理

x

_i

≥ 0

，

y

_i

> 0

，

∑

_i

x

_i

=

∑

_i

y

_i

= 1

とする。このとき，次の式が成立 する。

−

∑

i

x

_i

log

_r

x

_i

≤ −

∑

i

x

_i

log

_r

y

_i

(

証明

)

左辺−右辺は，前のページの補題を使うと，次のようになる。

∑

i

x

_i

log

_r

y

i

x

_i

=

1

ln r

∑

i

x

_i

ln

y

i

x

_i

≤

1

ln r

∑

i

x

_i

(

y

_i

x

_i

− 1

)

=

1

ln r

∑

i

(y

_i

− x

_i

) =

1

ln r

(1

− 1) = 0

等号が成立する必要十分条件は，

y

_i

/x

_i

= 1

がすべての

i

に対して成立す ることである。

•

定理

(

エントロピーの上限

)

情報源

S

が

q

個のシンボルを持つとき，

H

_r

(

S) ≤ log

_r

q

が成立する。 等号が成立する必要十分条件は，

p

₁

= p

₁

=

· · · = p

_q

= 1/q

である。

(

証明

)

先の命題で，

x

_i

= p

_i，

y

_i

= 1/q

とおけば，

H

_r

(

S) = −

∑

i

p

_i

log

_r

p

_i

≤ −

∑

i

p

_i

log

_r

(1/q) = log

_r

q

となる。等号が成立する条件も明らか。

3.3

_{エントロピーと平均符号長} 定理

C

が情報源

S

の一意復号可能な

r

元符号ならば，

L(

C) ≥ H

_r

(

S)

が成立する。

(

証明

)

C

の符号長を

l

₁

, l

₂

, . . . , l

_q とし，

K =

q

∑

i=1

r

−li とする。

y

_i

= r

−li

_/K

_{とおけば，}

∑

q

_y

i

= 1

であるから，

p.36

の定理を

一意復号可能であるから，

K

≤ 1

である

(log

_r

K

≤ 0)

。

H

_r

(

S) = −

q

∑

i=1

p

_i

log

_r

p

_i

≤ −

q

∑

i=1

p

_i

log

_r

y

_i

=

−

q

∑

i=1

p

_i

log

_r

(r

−li

_/K)

=

q

∑

i=1

p

_i

l

_i

+

q

∑

i=1

p

_i

log

_r

K = L(

C) + log

_r

K

≤ L(C)

となる。

系  前ページの定理で，等号が成立する必要十分条件は，任意の

i

に対し て，

log

_r

p

_iが整数になっていることである。

(

証明の概要

)

等号が成立すれば，

p

_i

= y

_i かつ

log

_r

K = 0

である

(K = 1)

。従って，

log

_r

p

_i

=

−l

_iとなり整数になる。 逆に，

log

_r

p

_iが整数ならば，

l

_i

=

− log

_r

p

_iとすれば， q

∑

i=1

r

−li

₌

q

∑

i=1

p

_i

= 1

となり，マクミランの不等式を満たすので，その符号長の一意復号可能 な符号が存在する。

例：

•

情報源

S

：

p

₁

= 1/2

，

p

₂

= 1/4

，

p

₃

= 1/8

，

p

₄

= 1/8

符号

C

：

w

₁

= 0

，

w

₂

= 10

，

w

₃

= 110

，

w

₄

= 111

H

₂

(

S) = −

1

2

log

2

1

2

−

1

4

log

2

1

4

−

1

8

log

2

1

8

−

1

8

log

2

1

8

= 1.75

L(

C) =

1

2

× 1 +

1

4

× 2 +

1

8

× 3 +

1

8

× 3 = 1.75

η = 1.75/1.75 = 1.0

•

情報源

S

：

p

₁

= 0.3

，

p

₂

= 0.2

，

p

₃

= 0.2

，

p

₄

= 0.2

，

p

₅

= 0.1

符号

C

：

w

₁

= 00

，

w

₂

= 10

，

w

₃

= 11

，

w

₄

= 010

，

w

₄

= 011

H

₂

(

S) = −0.3 log

₂

0.3

− 0.2 log

₂

0.2

− 0.2 log

₂

0.2

− 0.2 log

₂

0.2

−0.1 log

2

0.1

= 2.2464

L(

C) = 0.3 × 2 + 0.2 × 2 + 0.2 × 2 + 0.2 × 3 + 0.1 × 3 = 2.3

η = 2.2464/2.3 = 0.9767

3.4

_{シャノン・ファノ符号}

• ⌜x⌝

：実数

x

に対して，

x

以上の最小の整数。  例：

⌜2.3⌝ = 3

，

⌜4.0⌝ = 4

•

出現確率が

0

のシンボルが存在しないとする。

• l

i

=

⌜− log

r

p

i

⌝

とすれば，

− log

_r

p

_i

≤ ⌜− log

_r

p

_i

⌝ < − log

_r

p

_i

+ 1

q

∑

i=1

r

−li

≤

q

∑

i=1

p

_i

= 1

となり，マクミランの不等式を満たす。

•

従って，この符号長の瞬時復号可能な符号が存在する。 シャノン・ファノ符号と呼ぶ。

•

また，上の不等号を平均して以下の式を得る。

(

出現確率

0

のシンボルにも符号語を割り当てる。  

p

₀

= 1

，

p

₁

= 0

，

w

₀

= 0

，

w

₁

= 1)

•

平均符号長は

H

_r

(

S) + 1

以下になる。

•

シャノン・ファノ符号は一般には最適符号ではない。

•

ハフマン符号は最適符号であるから， ハフマン符号の平均符号長も

H

_r

(

S) + 1

_{以下である。}

•

例：情報源

S

：

p

₁

= 0.3

，

p

₂

= 0.2

，

p

₃

= 0.2

，

p

₄

= 0.2

，

p

₅

= 0.1

log

₂

0.3 =

−1.73

，

log

₂

0.2 =

−2.321

，

log

₂

0.1 =

−3.32

，

L(

C) = 0.3 × 2 + 0.2 × 3 + 0.2 × 3 + 0.2 × 3 + 0.1 × 4 = 2.8

となる。

η = 0.8214

である

(

ハフマン符号は

L(

C) = 2.2464

だった

)

。

•

次節で説明する拡大情報源を使えば，シャノン・ファノ符号は最適符

3.5

_{拡大情報源}

• S

：

{s

₁

, . . . , s

_q

}

，

p

₁

, . . . , p

_q

• T

：

{t

₁

, . . . , t

_q′

}

，

p

′₁

, . . . , p

′ q′

•

拡大情報源

S × T

：シンボルは

S

と

T

のシンボルの組

(s

_i

, t

_j

)

からなる。

•

情報源が独立：シンボル

(s

_i

, t

_j

)

_{の生起確率が}

p

_i

p

′_j となること。

• S

と

T

を独立な情報源とするとき，次式が成立する。

H

_r

(

S × T ) = H

_r

(

S) + H

_r

(

T )

(

証明

)

H

_r

(

S × T ) = −

q

∑

i=1 q′

∑

j=1

p

_i

p

′_j

log

_r

p

_i

p

′_j

=

−

∑

i

∑

j

p

_i

p

′_j

(log

_r

p

_i

+ log

_r

p

′_j

)

∑



∑



∑



∑



•

帰納的に，情報源

n

個の情報源

S

₁

,

S

₂

, . . . ,

S

_nの積に拡張する。

• S

n_を，

S

1

× S

2

× · · · × S

n

= (

S

1

× S

2

× · · · × S

n−1

)

× S

n

• S

1

,

S

2

, . . . ,

S

nに対して，それぞれの

 シンボル：

s

_1,i1

, s

_2,i2

, . . . , s

_n,in

 生起確率：

p

_1,i1

, p

_2,i2

, . . . , p

_n,inで表す。

• S

1

,

S

2

, . . . ,

S

nが独立とする。

•

拡大情報源

S

₁

× S

₂

× · · · × S

nでは，

 シンボル：

(s

_1,i1

, s

_2,i2

,

· · · , s

_n,in

)

  

(

それぞれのシンボルを組み合わせて

1

つのシンボルができる。

)

 生起確率：

p

_1,i1

p

_2,i2

· · · p

_n,inで与えられる。

  

(

それぞれの生起確率の積で与えられる。

)

• S

1

,

S

2

, . . . ,

S

nが独立な情報源ならば，次式が成立する。

• S

1

,

S

2

, . . . ,

S

nを情報源

S

の独立した

n

個のコピーとする。

S

n

_{≡ S}

1

× S

2

× · · · × S

n と定義すれば，次式が成立する。

3.6

_{シャノンの第１基本定理}

• L

n：

S

nに対する符号長。

•

シャノン・ファノの符号化より，次の関係を満たす符号が存在する。

H

_r

(

S

n

)

≤ L

_n

≤ H

_r

(

S

n

) + 1

•

S

n_{の符号語は情報源}

_S

_{のシンボル}

_n

_{個を表している。}

• S

のシンボル

1

つを表すために必要な平均符号長は

L

_n

/n

である。

• H

r

(

S

n

) = nH

r

(

S)

であるので以下の式が成立する。

H

_r

(

S) ≤

L

n

n

≤ H

r

(

S) +

1

n

• n → ∞

で，

1/n

→ 0

。

•

シャノンの第１基本定理：  十分大きな

n

に対して，

S

nを符号化すれば，情報源

S

の一意復元可 能な

r

元符号で，平均符号長がエントロピー

H

_r

(

S)

に十分近いものが存 在する。

•

例：

p

₁

= 3/4

，

p

₂

= 1/4

のとき。

– H

₂

(

S) = 0.81128

–

S

に対して，

w

₁

= 0, w

₂

= 1

となり

L

₁

= 1

–

S

2に対して，ハフマン符号を構成する。  

w

₁₁

= 0, w

₁₂

= 10, w

₂₁

= 110, w

₂₂

= 111

となり，

L

₂

/2 = 0.84375

–

S

3に対して，ハフマン符号を構成する。  

w

₁₁₁

= 0, w

₁₁₂

= 110, w

₁₂₁

= 100, w

₁₂₂

= 11100, w

₂₁₁

= 101,

w

₂₁₂

= 11101, w

₂₂₁

= 11110, w

₂₂₂

= 11111

となり，

L

₃

/3 = 0.82292

3.7

_{マルコフ過程のエントロピー}

•

情報源が出力するシンボルの確率が直前のシンボルに依存する。

• p

ij：直前にシンボル

j

を出力したという条件のもとで，   シンボル

i

_{を出力する確率}。

• p

∗_i ：定常状態において，シンボル

i

を出力する確率。   

(

エルゴード性

)

p

∗_i

=

∑

j

p

_ij

p

∗_j

•

シンボル

j

_{を受け取っていたとする。}

–

このとき，シンボル

i

を受け取ったときの情報量：  

(

解消する不確定さの量

)

。

− log p

ij

–

そのときの平均情報量

−

∑

i

p

_ij

log

_r

p

_ij

•

これを直前に受け取ったシンボル

j

に関して平均したものがエントロ ピーになる。

H

_r

(

S) = −

∑

j

∑

i

p

∗_j

p

_ij

log

_r

p

_ij

•

∑

_i

p

_ij

= 1

であるから，

p.36

の定理より，任意の

j

に対して，

−

∑

i

p

_ij

log

_r

p

_ij

≤ −

∑

i

p

_ij

log

_r

p

∗_i が成立する。従って，

H

_r

(

S) = −

∑

j

∑

i

p

∗_j

p

_ij

log

_r

p

_ij

≤ −

∑

j





∑

i

p

_ij

p

∗_j



 log

_r

p

∗_i

∑

4

_まとめ

•

エントロピーは情報量を考えるための非常に重要な概念。

(

エントロピー符号化：

ZIP, LHA, JPEG

など

)

•

エントロピーは抽象的な感じがするが，符号と結びついて具体的な感 じになる。

•

最近は，ハフマン符号より複雑であるが性能の高い「算術符号化」が 使われる。