☆HOME☆　☆数学のいずみ☆

高校生のための情報理論入門

@Author　Masasi.Sanae　　@Version　1.02;2002.3.16

０．はじめに

　情報化社会においては発信者から受信者への情報の伝達が重要な役割を果たします。更にその情報の伝達を如何に効率よく行うか，如何に正確に行うかが重要となります。そうした分野を対象としているのが「情報理論」と呼ばれているものです。
　情報理論を支えているのが数学の確率・統計に関する基本的な理論です。身の回りを取り巻くディジタルな世界を情報理論を通して解析し，実生活に直結する話題であることを体感してみましょう。

1．確率の基礎知識

1_1　集合

　あるものの集まりを集合という。集合は要素（元）から成り立っている。
　　　A={a₁，a₂，a₃，・・・a_n}
任意の集合Sの要素の一つをxとするとき，xは集合Sに属するといいx∈Sのように表す。また，要素のない集合を空集合といい，φで表す。
　集合Aの要素が全て集合Bの要素であるとき，集合AはBの部分集合であるといいA⊂Bで表す。2つの集合A，Bに対して，次の集合演算を定義する。

• 和集合A∪B　　A，Bどちらかに属している要素の集合
• 積集合A∩B　　A，Bどちらにも属している要素の集合
• 差集合A-B　　集合Aから集合Bを取り除いた要素の集合

（例）A={1，2，3，4，5}　B={0，1，2，3}

1. A∪B={0，1，2，3，4，5}
2. A∩B={1，2，3}
3. A-B={4，5}

1_2　試行と事象

　結果が確率的である行為を試行といい，試行を何度も行ったつながりを試行列という。
　起こりうる全ての試行列の集合を標本空間という。また，標本空間Sの部分集合を事象という。

（例）サイコロを1回振る。事象E_iを次のように定める。
　　　E_i：目iが出る事象　（i=1,2,…6）

1. 標本空間　S={E₁，E₂，E₃，E₄，E₅，E₆}
2. 1の目が出る事象　{E₁}
3. 偶数の目が出る事象　{E₂，E₄，E₆}

1_3　事象の演算

　2つの事象A，Bに対して，次のような演算を定義する。

• 事象の和A∪B　　A，B少なくとも一方が生じる事象
• 事象の積A∩B　　A，B同時に生じる事象
• 事象の否定A^c　　Aが生じない事象

　2つの事象A，Bの間に共通部分がない場合（A∩B=φ），A，Bは排反であるという。

（例）サイコロを1回振るとき，事象E_i，A，Bを次の様に定める。
　　　E_i：目iが出る事象　（i=1,2,…6）　　A：偶数の目が出る　　　B：5以上の目が出る

1. A={E₂，E₄，E₆}　　B={E₅，E₆}
2. A∪B={E₂，E₄，E₅，E₆}
3. A∩B={E₆}
4. A^c={E₁，E₃，E₅}

1_4　確率の定義

　n個の事象からなる標本空間SをS={E₁，E₂，E₃，…，E_n}とする。n個の事象Eiの起こりやすさは同様に確からしいとする。
　事象Aは標本空間Sの中のm個の要素からなるとする。このとき事象Aの起きる確率を
　　　P(A)=m/n
で定める。このとき余事象A^cの起こる確率は，次の様になる。
　　　A^c=1-P(A)

(例)サイコロを1回振るとき，事象E_i，Aを次の様に定める。
　　　E_i：目iが出る事象　（i=1,2,…6）　　A：偶数の目が出る　　　B：5以上の目が出る

1. P(A)=3/6=1/2
2. P(B)=2/6=1/3
3. P(A^c)=1-1/2=1/2

1_5　完全事象系

　互いに排反なn個の事象からなる標本空間S={E₁，E₂，E₃，…，E_n}に対して，各事象の生起確率をP(E₁)，P(E₂)，P(E₃)，…，P(E_n)とする。
　　　Σ P(E_i)=1
が成り立つとき，Sを完全事象系といい次のように表す。

(例)サイコロを1回振るとき，目iが出る事象をE_i（i=1,2,…6）とする。標本空間S={E₁，E₂，E₃，…，E₆}は完全事象系である。

1_6　乗法定理

　2つの事象A，Bを，この順で試行する。このときAが起こったことがわかっているときのBの起こる確率を，条件付確率といいP(B|A)で表す。
　2つの事象A，Bの積（A，Bがともに起こる）確率を結合確率といいP(A∩B)で表す。条件付確率と結合確率の間には，次の関係式が成り立つ。
　　　P(A∩B)=P(A)・P(B|A)
　2つの事象A，Bが互いに相手に影響を及ぼさないとき独立という。このときP(B)=P(B|A)であるから
　　　P(A∩B)=P(A)・P(B)

(例)2つの事象A，Bの起こる確率を3/10，3/5とし，A，Bがともに起こる確率が1/10とする。
　　Aが起こったという条件のもとでのBの起こる確率P(B|A)を求める。
　　　　P(B|A)=P(A∩B)/P(A)=(1/10)/(3/10)=1/3

1_7　ベイズの定理

　互いに背反な完全事象系{A₁，A₂，・・・，A_n}に対して，Ａ_ｉが原因となって事象Bが起こるとする。
　Ａ_ｉが原因でBが起こる確率P(B|Ａ_ｉ)を事前確率，Bという条件のもとでＡ_ｉが起こったと考えられる確率P(Ａ_ｉ|B)を事後確率という。
　事前確率P(B|Ａ_ｉ)と事後確率P(Ａ_ｉ|B)の間には，次の関係が成り立つ。
　　　　P(Ａ_ｉ∩B)=P(B)・P(Ａ_ｉ|B)，　　　P(B)=ΣP(Ａ_ｉ)・P(B|Ａ_ｉ)
　　　∴　P(Ａ_ｉ|B)=P(Ａ_ｉ∩B)/P(B)=P(Ａ_ｉ)・P(B|Ａ_ｉ)／ΣP(Ａ_ｉ)・P(B|Ａ_ｉ)

(例)事象Bを胃痛の発生とする。Bの原因として，次の3つの事象を考える。
　　　A₁：ストレス　　　A₂：胃潰瘍　　　A₃：胃がん
　そしてそれぞれが原因で胃痛の起こる確率（事前確率）を0.4，0.5，0.1とする。また，それぞれの事象の発生確率を0.6，0.35，0.05とする。

1. 事象Bの起こる確率
   P(B)=ΣP(Ａ_ｉ)・P(B|Ａ_ｉ)=0.6・0.4+0.35・0.5+0.05・0.1=0.42
   

   	A1	A2	A3
   B	0.4	0.5	0.1

2. それぞれの事象に対する事後確率
   P(Ａ₁|B)=P(Ａ₁∩B)/P(B)=P(Ａ₁)・P(B|Ａ₁)/P(B)=0.6・0.4/0.42=0.57
   P(Ａ₂|B)=P(Ａ₂∩B)/P(B)=P(Ａ₂)・P(B|Ａ₂)/P(B)=0.35・0.5/0.42=0.42
   P(Ａ₃|B)=P(Ａ₃∩B)/P(B)=P(Ａ₃)・P(B|Ａ₃)/P(B)=0.05・0.1/0.42=0.01

1_8　平均値

　標本空間Sにおいて定義される変数Xを考える。変数Xが具体的にxという値をとるときの確率を
　　　　P(X=x)　または　p(x)
と表す。このようなXを確率変数という。また確率変数とその確率の積の総和を平均値（期待値）といい，E(X)で表す。
　　　　E(X)=ΣXP(X=x)=Σxp(x)

(例)Xの確率分布が次のように与えれたときの平均値を求めるE(X)。

X	1	2	3	計
P	7/15	7/15	1/15	1

　　　　E(X)=1*7/15+2*7/15+3*1/15=24/15=1.6

2．情報量

　生起確率（発生確率）がP(a)の事象aが起こったとき，これを知ることにより得られる情報量をI(a)とする。

• I(a)∝1/P(a)
• P(a)が小　→　I(a)が大（驚き大）
  P(a)が大　→　I(a)が小（驚き小）

　情報量I(a)を次のように定義する。
　　　I(a)=log₂1/P(a)=-log₂P(a)　　（単位　ビット(bit）)

　この定義に従うと，次のことが言える。

• 1ビット=確率1/2で起こる事を伝える情報量
• n ビット=確率1/2ⁿで起こることを伝える情報量

（例1）出現確率が等しいコインの情報量
　　　a：表が出るという事象　　I(a)=-log₂P(a)=-log₂1/2=log₂2=1（ビット)

（例2）出現確率が等しいさいころの目の情報量
　　　a：1の目が出るという事象　　I(a)=-log₂P(a)=-log₂1/6=log₂6≒2.58（ビット)

（例3）試験の合格可能性が1/8である生徒の合格，不合格を伝える情報量
　　　a：合格するという事象　　I(a)=-log₂P(a)=-log₂1/8=log₂8=3（ビット)
　　　b：不合格という事象　　　I(b)=-log₂P(b)=-log₂7/8≒0.193（ビット)
　　　　⇒　合格を伝える情報量は不合格を伝える情報量より大きい

2_2　情報量の性質

　生起確率（発生確率）がP(a)の事象aが起こったときの情報量をI(a)とすると，次の性質が成り立つ。

1. 非負性　　I(a)≧0
2. 加法性　　I(ab)=I(a)+I(b)
3. 正規性　　I(1/2)=1

（例）さいころを1個振るとき，2つの事象a，bを次の様に定める。
　　　　a：偶数の目が出る　　b：3の倍数の目が出る
　　I(a)=-log₂P(a)=I(a)=-log₂1/2=1（ビット)　　　I(b)=-log₂P(b)=-log₂1/3≒1.58（ビット)
　　I(ab)=-log₂P(ab)=-log₂1/6=2.58（ビット)
　　∴　I(ab)=I(a)+I(b)

2_3　平均情報量（エントロピー）

　n個の事象からなる完全事象系 A={a₁，a₂，a₃，…，a_n} （Σa_i=1，ai∩aj=φ）を考える。情報量I(a_i)の期待値をH(A)とすると
　　　H(A)=ΣP(a_i)I(a_i)=-ΣP(a_i) log₂P(a_i)
　このHを平均情報量（エントロピー）という。これは情報の不確かさの平均値を表す。

(例1)1枚のコインを投げる。2つの事象を次のように定める。　a₁：表が出る，a₂：裏が出る

1. 出現確率が等しい場合
   P(a₁)=0.5，P(a₂)=0.5
   H=-0.5log₂0.5-0.5log₂0.5=1
2. 出現確率が等しくない場合
   P(a₁)=0.6，P(a₂)=0.4
   H=-0.6log₂0.6-0.4log₂0.4=0.6*0.44+0.4*0.53=0.97

　　コインが公正なものでないときにはコインが公正な場合よりも エントロピーが減少する。

(例2)ある都市のある日の天気予報が，晴れ45%，曇り35%，雨12%，雪8%のときのエントロピーH
　　　H=-0.45log₂0.45-0.35log₂0.35-0.12log₂0.12-0.08log₂0.08
　　　　=0.45*1.15+0.35*1.51+0.12*3.06+0.08*3.64
　　　　=0.52+0.53+0.37+0.29=1.17

2_4　最大エントロピー

　2つの事象からなる完全事象系Aを考える。

　このときのエントロピーH(A)は，次のようになる。
　　　H(A)=-P(a₁)log₂P(a₁)-P(a₂)log₂P(a₂)=-plog₂p-(1-p)log₂(1-p)
　このpについての関数をエントロピー関数といいH (p)で表す。（注：ここでは記述上区別して斜体で表す）
　　　H (p)=-plog₂p-(1-p)log₂(1-p)
　これをグラフ化したものが右図である。このグラフから次のことがわかる。

• 確率p=0，1のとき，不確かさは最小で0ビット
• 確率p=1/2のとき，不確かさは最大で1ビット

　同様に3つの事象からなる完全事象系のエントロピーは，次の式で与えられる。
　　　H=-p₁log₂p₁-p₂log₂p₂-(1-p₁-p₂)log₂(1-p₁-p₂)
　最大エントロピーはp₁=p₂=p₃=1/3のときにH=log₂3（ビット）で与えられる。（右図）

　一般にn個の事象からなる完全事象系の最大エントロピーは，
　　　p₁=p₂=・・・=p_n=1/nのときにH=log₂n（ビット）
で与えられる。

(例1)A市におけるa₁：晴れとa₂：雨の確率をそれぞれ
　　　P(a₁)=0.99，　　P(a₂)=0.01
　とするときのエントロピーはエントロピー関数表でp=0.01の値を参照しH (0.01)=0.08（ビット）を得る。

(例2)サイコロを1回振るときの最大エントロピーは
　　　H=-Σ1/6log₂1/6=log₂6=2.585（ビット）

3．相互情報量

3_1　結合エントロピー

　2つの事象系A，Bを次のようにとる。

A= ( a1 a2 ) P(a1) P(a2)

B= ( b1 b2 ) P(ｂ1) P(b2)

　この2つの事象系の事象を組み合わせて新しい事象系を作成する。ただし，(a_i，b_j)=a_i∩b_j，P(a_i，b_j)=P(a_i∩b_j)とする。

AB=	(	(a1，b1)	(a1，b2)	(a2，b1)	(a2，b2)	)
		P(a1，b1)	P(a1，b2)	P(a2，b1)	P(a2，b2)

　これを簡単に次のような表で表すこととする。

	b1	b2
a1	P(a1，b1)	P(a1，b2)
a2	P(a2，b1)	P(a2，b2

　このときの平均情報量を結合エントロピーといいH(AB)で表す。
　　　　H(AB)=-Σ_iΣ_jP(a_i，b_j)log₂P(a_i，b_j)　　　　

(例)A市における天気に関する事象系A（a₁：晴れ，a₂：雨）と温度に関する事象系B（b₁：20度以上，b₂：20度未満）に対して，次の表のような確率が成り立っているとする。このときのA，BのエントロピーおよびABの結合エントロピーを求める。

	b1	b2	P(ai)
a1	0.18	0.42	0.6
a2	0.12	0.28	0.4
P(bi)	0.3	0.7	1

1. H(A)=-0.6log₂0.6-0.4log₂0.4=0.6*0.74+0.4*1.32=0.97（ビット）
2. H(B)=-0.3log₂0.3-0.7log₂0.7=0.3*1.74+0.7*0.51=0.88（ビット）
3. H(AB)=-0.18log₂0.18-0.42log₂0.42-0.12log₂0.12-0.28log₂0.28=0.18*2.47+0.42*1.25+0.12*3.06+0.28*1.84=1.85（ビット）

　　　　＊H(AB)=H(A)H(B)が成り立つとき，事象A，Bは独立していることを示す。

3_2　条件付きエントロピー

　2つの事象系A，Bを次のようにとる。

A= ( a1 a2 ・・・ am ) P(a1) P(a2) ・・・ P(am)

B= ( b1 b2 ・・・ bn ) P(b1) P(b2) ・・・ P(bn)

　条件付エントロピーを次のように定める。
　　　　H(B|A)=ΣiP(ai)H(B|ai)=-Σ_iΣ_jP(a_i)P(b_j|a_i)log₂P(b_j|a_i)

　条件付きエントロピーは次の性質を持っている。

1. H(AB)=H(A)+H(B|A)＝H(B)+H(A|B)=H(BA)
2. H(B|A)≧0
3. H(A)≧H(A|B)，H(B)≧H(B|A)　　（シャノンの基本不等式）
4. H(AB)≦H(A)+H(B)　　（等号は事象系A，Bが独立のとき）

(例)A市における天気に関する事象系A（a₁：晴れ，a₂：雨）と温度に関する事象系B（b₁：20度以上，b₂：20度未満）に対して，次の表のような確率が成り立っているとする。このときの条件付きエントロピーP(B|A)を求める。

	b1	b2	P(ai)
a1	0.18	0.42	0.6
a2	0.32	0.08	0.4
P(bi)	0.5	0.5	1

1. 条件付き確率
   P(b₁|a₁)=P(a₁，b₁)/P(a₁)=0.18/0.6＝0.3（ビット）
   P(b₂|a₁)=P(a₁，b₂)/P(a₁)=0.42/0.6＝0.7（ビット）
   P(b₁|a₂)=P(a₂，b₁)/P(a₂)=0.32/0.4＝0.8（ビット）
   P(b₂|a₂)=P(a₂，b₂)/P(a₂)=0.08/0.4＝0.2（ビット）
2. 条件付きエントロピー
   H(B|A)=-Σ_iΣ_jP(a_i)P(b_j|a_i)log₂P(b_j|a_i)
   　　　　=-0.6*0.3*log₂0.3-0.6*0.7*log₂0.7-0.4*0.8*log₂0.8-0.4*0.2*log₂0.2
   　　　　=0.31+0.22+0.10+0.19
   　　　　=0.82（ビット）

　　H(B)=-0.5log₂0.5-0.5log₂0.5=0.5*1+0.5*1=1（ビット）　であるからH(B)≧H(B|A)であることがわかる。

3_3　相互情報量

　事象系AとBになんらかの関係があれば，Aが何であるかを知ることによって，Bが何であるかについても若干の情報が得られるはずである。この情報量はAを知ることによって得られるBのエントロピーの減少分によって定義することができる。これを相互情報量といいH(A；B)で表す。
　　　　I(A；B)=H(B)-H(B|A)
　ここでH(B)を事前エントロピー，H(B|A)を事後エントロピーという。

　相互情報量は次のような性質を持っている。

1. I(A；B)=I(B；A)
2. I(A；B)≧H(A)，H(B)
3. I(A；B)≧0

(例)A市における天気に関する事象系A（a₁：晴れ，a₂：雨）と温度に関する事象系B（b₁：20度以上，b₂：20度未満）に対して，次の表のような確率が成り立っているとする。このときの相互情報量I(A；B)を求める。

	b1	b2	P(ai)
a1	0.24	0.36	0.6
a2	0.26	0.14	0.4
P(bi)	0.5	0.5	1

1. 条件付き確率
   P(b₁|a₁)=P(a₁，b₁)/P(a₁)=0.24/0.6＝0.4（ビット）
   P(b₂|a₁)=P(a₁，b₂)/P(a₁)=0.36/0.6＝0.6（ビット）
   P(b₁|a₂)=P(a₂，b₁)/P(a₂)=0.26/0.4＝0.65（ビット）
   P(b₂|a₂)=P(a₂，b₂)/P(a₂)=0.14/0.4＝0.35（ビット）
2. 事前エントロピー
   H(B)=-0.5log₂0.5-0.5log₂0.5=0.5*1+0.5*1=1（ビット）
3. 条件付きエントロピー
   H(B|A)=-Σ_iΣ_jP(a_i)P(b_j|a_i)log₂P(b_j|a_i)
   　　　　=-0.6*0.4*log₂0.4-0.6*0.6*log₂0.6-0.65*0.26*log₂0.26-0.35*0.14*log₂0.14
   　　　　=0.32+0.18+0.29+0.05
   　　　　=0.84（ビット）
4. 相互情報量
   I(A；B)=H(B)-H(B|A)=1-0.84=0.16（ビット）

4．情報源

　情報をA地からB地へ伝送（伝達）することを通信という。通信には2つの重要な条件「正確」「高速」が必要になる。シャノンが提案した通信系のモデルは次のようなものである。

4_2　情報源

　情報として各種の記号（アルファベット）を出力する源を情報源，その記号を情報源記号という。情報源記号の集合を情報源アルファベットといい，次のように表す。
　　　　S={s₁，s₂，s₃，・・・，s_n}
　情報源記号は数字0〜9でも良いし，英字のA〜Zや五十音でも良い。
　情報源記号が2つしかない情報源を2元情報源という。

（例1）1枚の硬貨5回を投げたときの出方　S={表，裏，表，表，裏}

（例2）1つのサイコロを6回投げたときの目の出方　S={4，2，3，4，1，5}

4_3　情報源の分類

　情報源には次の2つの種類がある。情報源をS={s₁，s₂，s₃，・・・，s_n}とする。

1. 記憶のない情報源
   記号s_iが統計的に独立に発生する情報源。
2. 記憶のある情報源（マルコフ情報源）
   s_iの生起に統計的依存性がある情報源。
   過去のm個の記号に依存してs_iが生起するとき，この情報源をm重マルコフ情報源という。特にm=1のとき，つまり直前の1個のみに依存する場合を単純マルコフ情報源という。

（例：記憶のない情報源）1つのサイコロを6回投げたときの目の出方　S={4，2，3，4，1，5}

（例：記憶のある情報源）

• 晴れの翌日は、晴れる確率が高い.。雨の翌日は雨の降る確率が高い。
• 母音の次に子音が続く確率は高い。子音の次には母音が続く確率がきわめて高い

4_4　状態遷移図

　情報源記号が2つの2重マルコフ情報源（2元2重マルコフ情報源）S={0，1}を考える。

　このとき2つ前の記号と1つ前の記号の組み合わせとして，次の4つが考えられる。
　　　　q₁=(00)，　q₂=(01)，　q₃=(10)，　q₄=(11)
　ある状態から次の状態へと変化することを遷移という。2元2次マルコフ情報源S={0，1}の場合，次の8つの遷移が考えられる。
　　　　�@00→00　　　　�A00→01　　　　�B01→10　　　　�C01→11
　　　　�D10→00　　　　�E10→01　　　　�F11→10　　　　�G11→11
　これを右のような図に表したものを状態遷移図という。

（例）2元単純マルコフ情報源の遷移図
　　　　S={0，1}，q₁=(0)，q₂=(1)
　　に対して，次の4つの遷移が考えられる。
　　　　�@0→0　　　　�A0→1　　　　�B1→0　　　　�C1→1

4_5　定常確率

　 情報源記号s_i（i=1，2，・・・，m)を持つ情報源アルファベットをS={s₁，s₂，・・・，s_m}とし，状態q_jの下でのs_iの生起確率をP(s_i|q_j)とする。各状態q_jの発生する確率を定常確率といい，P(q_j)で表す。このとき，次の関係式が成り立つ。

1. P(q_ｊ)=ΣP(q_j)P(s_i|q_j)
2. ΣP(a_j)=1

(例）2元単純マルコフ情報源
　　S={0，1}，q₁=(0)，q₂=(1)で与えられる2元単純マルコフ情報源の状態遷移図が，右図の様に与えられたときの状態確率を求める。
　　　　P(q₁)=P(q₁)P(0|q₁)+P(q₂)P(0|q₂)=P(q₁)*0.7+P(q₂)*0.1　・・・�@
　　　　P(q₂)=P(q₁)P(1|q₁)+P(q₂)P(1|q₂)=P(q₁)*0.3+P(q₂)*0.9　・・・�A
　　　　P(q₁)+ P(q₂)=1　・・・�B
　　　�@�A�Bより　P(q₁)=1/4，P(q₂)=1/3

4_6　情報源のエントロピー

1. 記憶のない情報源の場合
   　情報源記号s_i（i=1，2，・・・，m)を持つ情報源アルファベットをS={s₁，s₂，・・・，s_m}とし，その生起確率をP(s_i)とする。
   　1つの記号の持つエントロピーH(S)は，次の式で与えられる。
   　　　　H(S)=-ΣP(s_i)log₂P(s_i)　（ビット）
2. 記憶のある情報源の場合
   　情報源記号s_i（i=1，2，・・・，m)を持つ情報源アルファベットをS={s₁，s₂，・・・，s_m}とする。状態q_jの下でのs_iの生起確率をP(s_i|q_j)とすると，q_jの下でのエントロピーH(S|q_j)は
   　　　　H(S|q_j)=-ΣP(s_i|q_j)log₂P(s_i|q_j)　（ビット）
   　1つの記号を持つエントロピーH(S)は
   　　　　H(S)=ΣP(q_j)H(S|q_j)=-ΣP(q_j)ΣP(s_i|q_j)log₂P(s_i|q_j)　（ビット）

(例1）2元単純マルコフ情報源
　　S={0，1}，q₁=(0)，q₂=(1)で与えられる2元単純マルコフ情報源の状態遷移図が，右図の様に与えられたときの平均情報量H(S)を求める。

1. それぞれの状態における確率（状態確率）
   P(q₁)=P(q₁)P(0|q₁)+P(q₂)P(0|q₂)=P(q₁)*0.6+P(q₂)*0.8　・・・�@
   P(q₂)=P(q₁)P(1|q₁)+P(q₂)P(1|q₂)=P(q₁)*0.4+P(q₂)*0.2　・・・�A
   P(q₁)+ P(q₂)=1　・・・�B
   　�@�A�Bより　P(q₁)=2/3，P(q₂)=1/3
2. 平均情報量（エントロピー）
   H(S)=-ΣP(q_j)ΣP(s_i|q_j)log₂P(s_i|q_j)
   　　　=-ΣP(q_j){P(0|q_j)log₂P(0|q_j)+P(1|q_j)log₂P(1|q_j)}
   　　　=-P(q₁){P(0|q₁)log₂P(0|q₁)+P(1|q₁)log₂P(1|q₁)}-P(q₂){P(0|q₂)log₂P(0|q₂)+P(1|q₂)log₂P(1|q₂)}
   　　　=-2/3*(0.6log₂0.6+0.4log₂0.4)-1/3*(0.8log₂0.8+0.2log₂0.2)
   　　　=2/3*H (0.4)+1/3*H (0.2)
   　　　=2/3*0.9710+1/3*0.7219
   　　　=0.89　(ビット)

(例2)2元2重マルコフ情報源
　　S={0，1}，q₁=(00)，q₂=(01)，q₃=(10)，q₄=(11)で与えられる2元単純マルコフ情報源の状態遷移図が，右図の様に与えられたときの平均情報量H(S)を求める。

1. それぞれの状態における確率（状態確率）
   P(q₁)=P(q₁)P(0|q₁)+P(q₃)P(0|q₃)=P(q₁)*0.9+P(q₃)*0.7　・・・�@
   P(q₂)=P(q₁)P(1|q₁)+P(q₃)P(1|q₃)=P(q₁)*0.1+P(q₃)*0.3　・・・�A
   P(q₃)=P(q₂)P(0|q₂)+P(q₄)P(0|q₄)=P(q₂)*0.4+P(q₄)*0.2　・・・�B
   P(q₄)=P(q₂)P(1|q₂)+P(q₄)P(1|q₄)=P(q₂)*0.6+P(q₄)*0.8　・・・�C
   P(q₁)+ P(q₂)+ P(q₃)+ P(q₄)=1　・・・�D
   　�@〜�Dより　P(q₁)=7/12，P(q₂)=1/12，P(q₃)=1/12，P(q₄)=1/4
2. 平均情報量（エントロピー）
   H(S)=-ΣP(q_j)ΣP(s_i|q_j)log₂P(s_i|q_j)
   　　　=-ΣP(q_j){P(0|q_j)log₂P(0|q_j)+P(1|q_j)log₂P(1|q_j)}
   　　　=-P(q₁){P(0|q₁)log₂P(0|q₁)+P(1|q₁)log₂P(1|q₁)}
   　　　　-P(q₂){P(0|q₂)log₂P(0|q₂)+P(1|q₂)log₂P(1|q₂)}
   　　　　-P(q₃){P(0|q₃)log₂P(0|q₃)+P(1|q₃)log₂P(1|q₃)}
   　　　　-P(q₄){P(0|q₄)log₄P(0|q₄)+P(1|q₄)log₂P(1|q₄)}
   　　　=-7/12*(0.9log₂0.9+0.1log₂0.1)-1/12*(0.4log₂0.4+0.6log₂0.6)
   　　　　-1/12*(0.7log₂0.7+0.3log₂0.3)-1/4*(0.2log₂0.2+0.8log₂0.8)
   　　　=7/12*H (0.1)+1/12*H (0.4)+1/12*H (0.3)+1/4*H (0.2)
   　　　=7/12*0.4690+1/12*0.9710+1/12*0.8813+1/4*0.7219
   　　　=0.61　(ビット)

5．符号化

　通信とは発信者から媒体を通して情報を伝えることである。通信システムのモデルでは次のような経路をたどる。

1. 情報源
   情報として各種の記号を出力する源を情報源，その記号を情報源記号，情報源記号の集合を情報源アルファベットという。
2. 情報源符号化
   通信システムのモデルでは，まず情報源記号を符号記号（0と1がよく用いられる，単に符号ともいう）に変換する。符号の集合を符号アルファベットという。情報源記号を符号記号の組み合わせでできたものを符号語，その集合を情報源符号という。情報源から発信された信号を符号記号に変換することを情報源符号化という。
3. 通信路符号化
   通信路における誤りに対処できるように別な符号語に変換する。これを通信路符号化という。
4. 通信路
   符号化された情報は通信路，つまり媒体に入力される。この通信路の周りの雑音源からの雑音を受け，情報の一部が欠損したり，変化するような誤りが発生する。
5. 通信路復号
   誤りを検出・訂正するような復号を行う。
6. 情報源復号
   情報源記号に戻す復号をお行う。
7. 受信者

（例）情報源アルファベットS={A，B，C，D}，符号アルファベット{0，1}を用いて，情報源記号を次のように符号化する。

1. 情報源
   ADA
2. 情報源符号化　A：00，B：01，C：10，D：11
   ADA=001100
3. 通信路符号化　0：000　1：111
   001100=000 000 111 111 000 000
4. 通信路（誤り発生）
   001100⇒000 010 111 110 000 000
5. 通信路復号　000：0　100：0　010：0　001：0　111：1　011：1　101：1　110：1
   000 010 111 110 000 000=001100
6. 情報源復号　00：A　01：B　10：C　11：D
   001100=ADA
7. 受信者

5_2　符号

　情報源から符号を用いて符号語を作成する場合を考える。

• 符号の長さが等しい場合を固定長符号，そうでない場合を可変長符号という。
  固定長符号の場合の符号の長さを符号長という。
• 受信した符号語が唯一に復号できる場合を一意的復号可能という。
• 符号語を受け取った瞬間に復号できるような符号を瞬時符号という。

（例）情報源記号S={A，B，C，D}を符号語アルファベット{0，1}で，次の�Tから�Zの7通りの符号で符号化する。

　情報源ABCDを通信路符号化したあと，復号することで一意復号可能，瞬時符号について検証する。

1. 符号�T　AADBC→0000110110
   0000110110→00 00 11 01 10と区切れば良いので，一意復号可能であり，また瞬時符号である。
2. 符号�U　AADBC→00111010110
   00111010110→0 0111010110→0 0 111010110→0 0 1110 10110→0 0 1110 10 110と前から順次区切られ，一意復号可能であり，また瞬時符号である。これは0が区切りを与えるので，コンマ符号と呼ばれる。
3. 符号�V　AADBC→0011110110
   0011110110→0 011110110→0 0 11110110→0 0 111 10110→0 0 111 10 110と前から順次区切られ，一意復号可能であり，また瞬時符号である。
4. 符号�W　AADBC→0011101011
   �@0011101011→0 011101011→0 0 11101011→0 0 111 01011→0 0 111 0 1011→×
   �A0011101011→0 011101011→0 0 11101011→0 0 111 01011→0 0 111 01 011
   �B0011101011→0 011101011→0 01 1101011→×
   �C0011101011→0 011101011→0 011 101011→×
   これは最後には一つに定まるが，確定するにはいくつかのパターンを検証しなければならない。つまり一意復号可能であるが瞬時符号ではない。
5. 符号�X　AADBC→0001111
   �@0001111→0 001111→0 0 01111→0 0 0 1111→0 0 0 1 111→0 0 0 1 1 11→0 0 0 1 1 1 1
   �A0001111→0 001111→0 0 01111→0 0 0 1111→0 0 0 1 111→0 0 0 1 1 11
   　　・・・・・・・・・
   これは様々な復号ができるので一意復号可能ではない。当然瞬時符号でもない。
6. 符号�Y　AADBC→0001011
   同じ符号語があるので一意復号可能ではない。当然瞬時符号でもない。
7. 符号�Z　AADBC→0000001011
   同じ符号語があるので一意復号可能ではない。当然瞬時符号でもない。

5_3　瞬時符号の判定

　ある符号語が別の符号語の頭部に一致しなければ瞬時符号となる。これを語頭条件という。
　この語頭条件の判定を容易にする表現の方法として符号の木（ツリー）がある。（右図）
　符号の木においては，全ての符号語が葉に対応付けられていれば，他の符号の語頭にはならないので瞬時符号となる。

（例）情報源記号S={A，B，C，D}を符号語アルファベット{0，1}で，次の�Tから�Zの7通りの符号で符号化する。そのツリー表示。
　　�T〜�Vは全ての符号語が葉に対応しているが，それ以外は節点にも対応しているので瞬時符号とならない。

	�T	�U	�V	�W	�X	�Y	�Z
A	00	0	0	0	0	0	00
B	01	10	10	01	1	10	10
C	10	110	110	011	11	11	11
D	11	1110	111	111	01	0	00
木							***
一意	○	○	○	○	×	×	×
瞬時	○	○	○	×	***	***	***

5_4　クラフトの不等式

　長さｌ_ｉを持つm個のｒ元符号が瞬時符号であるための必要条件
　　　　Σ1/r^li　　（クラフトの不等式）

（例）情報源記号S={A，B，C，D}を符号語アルファベット{0，1}で，次の�Tから�Zの7通りの符号で符号化する。その時のΣ1/2^liの値を求める。

1. 符号�T　Σ1/2^li=1/2²+1/2²+1/2²+1/2²=1
2. 符号�U　Σ1/2^li=1/2¹+1/2²+1/2³+1/2⁴=15/16＜1
3. 符号�V　Σ1/2^li=1/2¹+1/2²+1/2³+1/2³=1
4. 符号�W　Σ1/2^li=1/2¹+1/2²+1/2³+1/2³=1
5. 符号�X　Σ1/2^li=1/2¹+1/2¹+1/2²+1/2²=1.5＞1
6. 符号�Y　Σ1/2^li=1/2¹+1/2²+1/2²+1/2¹=1.5＞1
7. 符号�Z　Σ1/2^li=1/2²+1/2²+1/2²+1/2²=1

　符号�U，�X，�Yのより符号語長{1，2，3，4}，{1，1，2，2}をもつ符号は瞬時符号になり得ない。
　符号�T，�Zより符号語長{2，2，2，2}を持つ符号は瞬時符号となる符号を作ることができる。しかしクラフトの不等式を満たすからと言って瞬時符号になるとは限らない。

5_5　平均符号長

　ｒ元符号において生成される情報源{A₁，A₂，・・・，A_m}を考える。記号A_iの生起確率をP(A_i)，符号語の長さをl_iとするとき，符号語の平均符号長Lは，次の式で与えられる。
　　　　L=ΣP(A_i)l_i

（例）情報源記号S={A，B，C，D}を符号語アルファベット{0，1}で，次の�Tから�Zの7通りの符号で符号化する。その時の平均符号長を求める。

1. 符号�T　ΣP(A_i)l_i=0.4*2+0.3*2+0.2*2+0.1*2=2
2. 符号�U　ΣP(A_i)l_i=0.4*1+0.3*2+0.2*3+04*2=2
3. 符号�V　ΣP(A_i)l_i=0.4*1+0.3*2+0.2*3+0.1*3=1.9
4. 符号�W　ΣP(A_i)l_i=0.4*1+0.3*2+0.2*3+0.1*3=1.9
5. 符号�X　ΣP(A_i)l_i=0.4*1+0.3*1+0.2*2+0.1*2=1.3
6. 符号�Y　ΣP(A_i)l_i=0.4*1+0.3*2+0.2*2+0.1*1=1.5
7. 符号�Z　ΣP(A_i)l_i=0.4*2+0.3*2+0.2*2+0.1*2=2

5_6　符号化の効率

　ｒ元符号において生成される情報源{A₁，A₂，・・・，A_m}を考える。記号A_iの生起確率をP(A_i)とするとき，情報源のエントロピーHは，次の式で与えられる。
　　　　H=-ΣP(A_i)log₂P(A_i)
　また，符号語の平均符号長をLとすると，1符号あたりの情報量eは，次の式で与えられる。
　　　　e=H/L
　このeは符号化の効率を表し，1に近いほど効率の良い符号化が行われたことになる。
　符号化の効率を高めるためには『生起確率の大きい記号に短い符号語を割り当てる』ことが，最も基本的なことと言える。

（例）情報源記号S={A，B，C，D}を符号語アルファベット{0，1}で，次の�Tから�Zの7通りの符号で符号化する。その時の符号化の効率を求める。
　　　エントロピーHはみな同じで
　　　　H=-0.4*log₂0.4-0.3*log₂0.3-0.2*log₂0.2-0.1*log₂0.1=0.53+0.52+0.46+0.33=1.84

5_7　シャノン・ファノの符号化法

　ｒ元符号において生成される情報源{A₁，A₂，・・・，A_m}を考え，記号A_iの生起確率をP(A_i)とする。シャノン・ファノの符号化法は次の通りである。

1. A_iをP(A_i)の大きい順に並べる。
2. P(A_i)の和がほぼ等しくなるようにA_iを2群に分ける。
3. その各群を更に2つに分ける。分割できなければ終了。
4. 分割をツリー表現し，ルートの上の枝を0，下の枝に1を割り当てる。ルートから葉へ至るまでの0と1の並びが求める符号語となる。

（例）次の情報源にシャノン・ファノの符号化法を用いる。

A=	(	A1	A2	A3	A4	A5	A6	)
		0.09	0.14	0.40	0.15	0.12	0.10

1. A₃＞A₄＞A₂＞A₅＞A₆＞A₁　（0.40＞0.15＞0.14＞0.12＞0.10＞0.09）
2. �@A₃，A₄　｜　A₂，A₅，A₆，A₁　（0.55　｜　0.45）
   �AA₃　｜　A₄　（0.40　｜　0.15）
   　 A₂，A₅　｜　A₆，A₁　（0.26　｜　0.19）
   �BA₂　｜　A₅　　（0.16　｜　0.12）
   　 A₆　｜　A₁　　（0.10　｜　0.09）
3. 
4. A₄=00，A₃=10，A₂=100，A₅=101，A₆=110，A₁=111

　ここでエントロピーH，平均符号化長L，符号化効率eを求める。

1. H=-0.09log₂0.09-0.14log₂0.14-0.40log₂0.40-0.15log₂0.15-0.12log₂0.12-0.10log₂0.10
   　=0.31+0.40+0.53+0.41+0.37+0.33=2.35　（ビット）
2. L=0.09*3+0.14*3+0.40*2+0.15*2+0.12*3+0.10*3
   　=0.27+0.42+0.80+0.30+0.36+0.30=2.45
3. e=2.35/2.45=0.96

5_8　ハフマンの符号化法

　ｒ元符号において生成される情報源{A₁，A₂，・・・，A_m}を考え，記号A_iの生起確率をP(A_i)とする。ハフマンの符号化法は次の通りである。

1. A_iをP(A_i)の大きい順に並べる。
2. P(A_i)の最も小さい2つの記号を統合して1つのグループとする。この生起確率は2つの生起確率の和とする。
3. 全体が1つになるまで1，2を繰り返す。
4. 全体をツリー表現し，ルートの上の枝を0，下の枝に1を割り当てる。ルートから葉へ至るまでの0と1の並びが求める符号語となる。

（例）次の情報源にハフマンの符号化法を用いる。

A=	(	A1	A2	A3	A4	A5	A6	)
		0.09	0.14	0.40	0.15	0.12	0.10

1. A₃＞A₄＞A₂＞A₅＞A₆＞A₁　（0.40＞0.15＞0.14＞0.12＞0.10＞0.09）
2. �@A₁+A₆=A₇　P(A₆)=0.09+0.10=0.19
   �AA₃＞A₇＞A₄＞A₂＞A₅　（0.40＞0.19＞0.15＞0.14＞0.12）
   �BA₂+A₅=A₈　P(A₈)=0.14+0.12=0.26
   �CA₃＞A₈＞A₇＞A₄　（0.40＞0.26＞0.19＞0.15）
   �DA₇+A₄=A₉　P(A₉)=0.19+0.15=0.34
   �EA₃＞A₉＞A₈　（0.40＞0.34＞0.26）
   �FA₉+A₈=A₁₀　P(A₁₀)=0.34+0.26=0.60
   �GA₃＞A₁₀　（0.60＞0.40）
   �HA₃+A₁₀=1
3. 
4. A₁=0000，A₆=0001，A₄=001，A₂=010，A₅=011，A₃=1

　ここでエントロピーH，平均符号化長L，符号化効率eを求める。

1. H=-0.09log₂0.09-0.14log₂0.14-0.40log₂0.40-0.15log₂0.15-0.12log₂0.12-0.10log₂0.10
   　=0.31+0.40+0.53+0.41+0.37+0.33=2.35　（ビット）
2. L=0.09*4+0.14*3+0.40*1+0.15*3+0.12*3+0.10*4
   　=0.36+0.42+0.40+0.45+0.36+0.40=2.39
3. e=2.35/2.39=0.98

≪参考資料≫

• わかりやすいディジタル情報理論（塩野充著，オーム社出版局，平成10年4月5日発行）
• 図解情報理論入門（野村由司彦著，コロナ社，1998年5月10日発行）
• 情報を送るための理論（佐藤洋一）　http://www.cl.is.sci.toho-u.ac.jp/text.htm
• 情報数学基礎（大木 真）　http://mail.sp.es.yamanashi.ac.jp/~ohki/education/2001/fim2001/text070/text070.html
• 教科情報授業プリント（柴田功）　http://www.ne.jp/asahi/k/suzuki/index.html

☆HOME☆　☆数学のいずみ☆