☆HOME☆ ☆数学のいずみ☆

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

@Author Masasi.Sanae  @Version 1.02;2002.3.16

0.はじめに

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

1.確率の基礎知識

1_1 集合

 あるものの集まりを集合という。集合は要素(元)から成り立っている。
   A={a1,a2,a3,・・・an}
任意の集合Sの要素の一つをxとするとき,xは集合Sに属するといいx∈Sのように表す。また,要素のない集合を空集合といい,φで表す。
 集合Aの要素が全て集合Bの要素であるとき,集合AはBの部分集合であるといいA⊂Bで表す。2つの集合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回振る。事象Eiを次のように定める。
   Ei:目iが出る事象 (i=1,2,…6)

  1. 標本空間 S={E1,E2,E3,E4,E5,E6}
  2. 1の目が出る事象 {E1}
  3. 偶数の目が出る事象 {E2,E4,E6}

1_3 事象の演算

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

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

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

  1. A={E2,E4,E6}  B={E5,E6}
  2. A∪B={E2,E4,E5,E6}
  3. A∩B={E6}
  4. Ac={E1,E3,E5}

1_4 確率の定義

 n個の事象からなる標本空間SをS={E1,E2,E3,…,En}とする。n個の事象Eiの起こりやすさは同様に確からしいとする。
 事象Aは標本空間Sの中のm個の要素からなるとする。このとき事象Aの起きる確率を
   P(A)=m/n
で定める。このとき余事象Acの起こる確率は,次の様になる。
   Ac=1-P(A)

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

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

1_5 完全事象系

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

S= ( E1 E2 ・・・ En )
P(E1) P(E2) ・・・ P(En)

(例)サイコロを1回振るとき,目iが出る事象をEi(i=1,2,…6)とする。標本空間S={E1,E2,E3,…,E6}は完全事象系である。

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 ベイズの定理

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

(例)事象Bを胃痛の発生とする。Bの原因として,次の3つの事象を考える。
   A1:ストレス   A2:胃潰瘍   A3:胃がん
 そしてそれぞれが原因で胃痛の起こる確率(事前確率)を0.4,0.5,0.1とする。また,それぞれの事象の発生確率を0.6,0.35,0.05とする。

  1. 事象Bの起こる確率
    P(B)=ΣP(A)・P(B|A)=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(A1|B)=P(A1∩B)/P(B)=P(A1)・P(B|A1)/P(B)=0.6・0.4/0.42=0.57
    P(A2|B)=P(A2∩B)/P(B)=P(A2)・P(B|A2)/P(B)=0.35・0.5/0.42=0.42
    P(A3|B)=P(A3∩B)/P(B)=P(A3)・P(B|A3)/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.情報量

2_1 情報量の定義

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

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

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

(例1)出現確率が等しいコインの情報量
   a:表が出るという事象  I(a)=-log2P(a)=-log21/2=log22=1(ビット)

(例2)出現確率が等しいさいころの目の情報量
   a:1の目が出るという事象  I(a)=-log2P(a)=-log21/6=log26≒2.58(ビット)

(例3)試験の合格可能性が1/8である生徒の合格,不合格を伝える情報量
   a:合格するという事象  I(a)=-log2P(a)=-log21/8=log28=3(ビット)
   b:不合格という事象   I(b)=-log2P(b)=-log27/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)=-log2P(a)=I(a)=-log21/2=1(ビット)   I(b)=-log2P(b)=-log21/3≒1.58(ビット)
  I(ab)=-log2P(ab)=-log21/6=2.58(ビット)
  ∴ I(ab)=I(a)+I(b)

2_3 平均情報量(エントロピー)

 n個の事象からなる完全事象系 A={a1,a2,a3,…,an} (Σai=1,ai∩aj=φ)を考える。情報量I(ai)の期待値をH(A)とすると
   H(A)=ΣP(ai)I(ai)=-ΣP(ai) log2P(ai)
 このHを平均情報量(エントロピー)という。これは情報の不確かさの平均値を表す。

(例1)1枚のコインを投げる。2つの事象を次のように定める。 a1:表が出る,a2:裏が出る

  1. 出現確率が等しい場合
    P(a1)=0.5,P(a2)=0.5
    H=-0.5log20.5-0.5log20.5=1
  2. 出現確率が等しくない場合
    P(a1)=0.6,P(a2)=0.4
    H=-0.6log20.6-0.4log20.4=0.6*0.44+0.4*0.53=0.97

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

(例2)ある都市のある日の天気予報が,晴れ45%,曇り35%,雨12%,雪8%のときのエントロピーH
   H=-0.45log20.45-0.35log20.35-0.12log20.12-0.08log20.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を考える。

A= ( a1 a2 ) = ( a1 a2 )
P(a1) P(a2) p 1-p

 このときのエントロピーH(A)は,次のようになる。
   H(A)=-P(a1)log2P(a1)-P(a2)log2P(a2)=-plog2p-(1-p)log2(1-p)
 このpについての関数をエントロピー関数といいH (p)で表す。(注:ここでは記述上区別して斜体で表す)
   H (p)=-plog2p-(1-p)log2(1-p)
 これをグラフ化したものが右図である。このグラフから次のことがわかる。

 同様に3つの事象からなる完全事象系のエントロピーは,次の式で与えられる。
   H=-p1log2p1-p2log2p2-(1-p1-p2)log2(1-p1-p2)
 最大エントロピーはp1=p2=p3=1/3のときにH=log23(ビット)で与えられる。(右図)

 一般にn個の事象からなる完全事象系の最大エントロピーは,
   p1=p2=・・・=pn=1/nのときにH=log2n(ビット)
で与えられる。

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

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

3.相互情報量

3_1 結合エントロピー

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

A= ( a1 a2 )
P(a1) P(a2)
B= ( b1 b2 )
P(b1) P(b2)

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

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(ai,bj)log2P(ai,bj)    

(例)A市における天気に関する事象系A(a1:晴れ,a2:雨)と温度に関する事象系B(b1:20度以上,b2: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.6log20.6-0.4log20.4=0.6*0.74+0.4*1.32=0.97(ビット)
  2. H(B)=-0.3log20.3-0.7log20.7=0.3*1.74+0.7*0.51=0.88(ビット)
  3. H(AB)=-0.18log20.18-0.42log20.42-0.12log20.12-0.28log20.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(ai)P(bj|ai)log2P(bj|ai)

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

  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(a1:晴れ,a2:雨)と温度に関する事象系B(b1:20度以上,b2: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(b1|a1)=P(a1,b1)/P(a1)=0.18/0.6=0.3(ビット)
    P(b2|a1)=P(a1,b2)/P(a1)=0.42/0.6=0.7(ビット)
    P(b1|a2)=P(a2,b1)/P(a2)=0.32/0.4=0.8(ビット)
    P(b2|a2)=P(a2,b2)/P(a2)=0.08/0.4=0.2(ビット)
  2. 条件付きエントロピー
    H(B|A)=-ΣiΣjP(ai)P(bj|ai)log2P(bj|ai)
        =-0.6*0.3*log20.3-0.6*0.7*log20.7-0.4*0.8*log20.8-0.4*0.2*log20.2
        =0.31+0.22+0.10+0.19
        =0.82(ビット)

  H(B)=-0.5log20.5-0.5log20.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(a1:晴れ,a2:雨)と温度に関する事象系B(b1:20度以上,b2: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(b1|a1)=P(a1,b1)/P(a1)=0.24/0.6=0.4(ビット)
    P(b2|a1)=P(a1,b2)/P(a1)=0.36/0.6=0.6(ビット)
    P(b1|a2)=P(a2,b1)/P(a2)=0.26/0.4=0.65(ビット)
    P(b2|a2)=P(a2,b2)/P(a2)=0.14/0.4=0.35(ビット)
  2. 事前エントロピー
    H(B)=-0.5log20.5-0.5log20.5=0.5*1+0.5*1=1(ビット)
  3. 条件付きエントロピー
    H(B|A)=-ΣiΣjP(ai)P(bj|ai)log2P(bj|ai)
        =-0.6*0.4*log20.4-0.6*0.6*log20.6-0.65*0.26*log20.26-0.35*0.14*log20.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.情報源

4_1 シャノンの通信系モデル

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

情報源 符号化 通信路 復号化 受信者
メッセージ 送信信号 雑↑音 受信信号 メッセージ
雑音源

4_2 情報源

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

(例1)1枚の硬貨5回を投げたときの出方 S={表,裏,表,表,裏}

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

4_3 情報源の分類

 情報源には次の2つの種類がある。情報源をS={s1,s2,s3,・・・,sn}とする。

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

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

(例:記憶のある情報源)

4_4 状態遷移図

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

──→ ──→
├2 個┤ si
この2個の記号に依存してsiが生起する

 このとき2つ前の記号と1つ前の記号の組み合わせとして,次の4つが考えられる。
    q1=(00), q2=(01), q3=(10), q4=(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},q1=(0),q2=(1)
  に対して,次の4つの遷移が考えられる。
    @0→0    A0→1    B1→0    C1→1

4_5 定常確率

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

  1. P(q)=ΣP(qj)P(si|qj)
  2. ΣP(aj)=1

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

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

  1. 記憶のない情報源の場合
     情報源記号si(i=1,2,・・・,m)を持つ情報源アルファベットをS={s1,s2,・・・,sm}とし,その生起確率をP(si)とする。
     1つの記号の持つエントロピーH(S)は,次の式で与えられる。
        H(S)=-ΣP(si)log2P(si) (ビット)
  2. 記憶のある情報源の場合
     情報源記号si(i=1,2,・・・,m)を持つ情報源アルファベットをS={s1,s2,・・・,sm}とする。状態qjの下でのsiの生起確率をP(si|qj)とすると,qjの下でのエントロピーH(S|qj)は
        H(S|qj)=-ΣP(si|qj)log2P(si|qj) (ビット)
     1つの記号を持つエントロピーH(S)は
        H(S)=ΣP(qj)H(S|qj)=-ΣP(qj)ΣP(si|qj)log2P(si|qj) (ビット)

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

  1. それぞれの状態における確率(状態確率)
    P(q1)=P(q1)P(0|q1)+P(q2)P(0|q2)=P(q1)*0.6+P(q2)*0.8 ・・・@
    P(q2)=P(q1)P(1|q1)+P(q2)P(1|q2)=P(q1)*0.4+P(q2)*0.2 ・・・A
    P(q1)+ P(q2)=1 ・・・B
     @ABより P(q1)=2/3,P(q2)=1/3
  2. 平均情報量(エントロピー)
    H(S)=-ΣP(qj)ΣP(si|qj)log2P(si|qj)
       =-ΣP(qj){P(0|qj)log2P(0|qj)+P(1|qj)log2P(1|qj)}
       =-P(q1){P(0|q1)log2P(0|q1)+P(1|q1)log2P(1|q1)}-P(q2){P(0|q2)log2P(0|q2)+P(1|q2)log2P(1|q2)}
       =-2/3*(0.6log20.6+0.4log20.4)-1/3*(0.8log20.8+0.2log20.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},q1=(00),q2=(01),q3=(10),q4=(11)で与えられる2元単純マルコフ情報源の状態遷移図が,右図の様に与えられたときの平均情報量H(S)を求める。

  1. それぞれの状態における確率(状態確率)
    P(q1)=P(q1)P(0|q1)+P(q3)P(0|q3)=P(q1)*0.9+P(q3)*0.7 ・・・@
    P(q2)=P(q1)P(1|q1)+P(q3)P(1|q3)=P(q1)*0.1+P(q3)*0.3 ・・・A
    P(q3)=P(q2)P(0|q2)+P(q4)P(0|q4)=P(q2)*0.4+P(q4)*0.2 ・・・B
    P(q4)=P(q2)P(1|q2)+P(q4)P(1|q4)=P(q2)*0.6+P(q4)*0.8 ・・・C
    P(q1)+ P(q2)+ P(q3)+ P(q4)=1 ・・・D
     @〜Dより P(q1)=7/12,P(q2)=1/12,P(q3)=1/12,P(q4)=1/4
  2. 平均情報量(エントロピー)
    H(S)=-ΣP(qj)ΣP(si|qj)log2P(si|qj)
       =-ΣP(qj){P(0|qj)log2P(0|qj)+P(1|qj)log2P(1|qj)}
       =-P(q1){P(0|q1)log2P(0|q1)+P(1|q1)log2P(1|q1)}
        -P(q2){P(0|q2)log2P(0|q2)+P(1|q2)log2P(1|q2)}
        -P(q3){P(0|q3)log2P(0|q3)+P(1|q3)log2P(1|q3)}
        -P(q4){P(0|q4)log4P(0|q4)+P(1|q4)log2P(1|q4)}
       =-7/12*(0.9log20.9+0.1log20.1)-1/12*(0.4log20.4+0.6log20.6)
        -1/12*(0.7log20.7+0.3log20.3)-1/4*(0.2log20.2+0.8log20.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.符号化

5_1 通信システムのモデル

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

  1. 情報源
    情報として各種の記号を出力する源を情報源,その記号を情報源記号,情報源記号の集合を情報源アルファベットという。
  2. 情報源符号化
    通信システムのモデルでは,まず情報源記号を符号記号(0と1がよく用いられる,単に符号ともいう)に変換する。符号の集合を符号アルファベットという。情報源記号を符号記号の組み合わせでできたものを符号語,その集合を情報源符号という。情報源から発信された信号を符号記号に変換することを情報源符号化という。
  3. 通信路符号化
    通信路における誤りに対処できるように別な符号語に変換する。これを通信路符号化という。
  4. 通信路
    符号化された情報は通信路,つまり媒体に入力される。この通信路の周りの雑音源からの雑音を受け,情報の一部が欠損したり,変化するような誤りが発生する。
  5. 通信路復号
    誤りを検出・訂正するような復号を行う。
  6. 情報源復号
    情報源記号に戻す復号をお行う。
  7. 受信者
     符号化       復号
   ADA・・・ 001100・・・ 000 000 111 111 ・・・  000 010 111 110・・・ 001100・・・ ADA・・・
情報源 情報源
符号化
通信路
符号化
通信路 通信路
復号
情報源
復号
受信者
情報源
アルファベット
S={A,B,C,D}
A:00
B:01
C:10
D:11
0::000
1:111
↑雑音 誤り
発生
000:0
100:0
010:0
001:0
111:1
011:1
101:1
110:1
00:A
01:B
10:C
11:D

(例)情報源アルファベット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通りの符号で符号化する。

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
等長符号 × × × × ×
一意復号可能 × × ×
瞬時符号 × *** *** ***

 情報源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 クラフトの不等式

 長さlを持つm個のr元符号が瞬時符号であるための必要条件
    Σ1/rli  (クラフトの不等式)

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

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
Σ1/2li 1 15/16 1 1 1.5 1.5 1
一意 × × ×
瞬時符号 × *** *** ***
  1. 符号T Σ1/2li=1/22+1/22+1/22+1/22=1
  2. 符号U Σ1/2li=1/21+1/22+1/23+1/24=15/16<1
  3. 符号V Σ1/2li=1/21+1/22+1/23+1/23=1
  4. 符号W Σ1/2li=1/21+1/22+1/23+1/23=1
  5. 符号X Σ1/2li=1/21+1/21+1/22+1/22=1.5>1
  6. 符号Y Σ1/2li=1/21+1/22+1/22+1/21=1.5>1
  7. 符号Z Σ1/2li=1/22+1/22+1/22+1/22=1

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

5_5 平均符号長

 r元符号において生成される情報源{A1,A2,・・・,Am}を考える。記号Aiの生起確率をP(Ai),符号語の長さをliとするとき,符号語の平均符号長Lは,次の式で与えられる。
    L=ΣP(Ai)li

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

P(Ai) T U V W X Y Z
A 0.4 00 0 0 0 0 0 00
B 0.3 01 10 10 01 1 10 10
C 0.2 10 110 110 011 11 11 11
D 0.1 11 1110 111 111 01 0 00
平均符号長 2 2 1.9 1.9 1.3 1.5 2
  1. 符号T ΣP(Ai)li=0.4*2+0.3*2+0.2*2+0.1*2=2
  2. 符号U ΣP(Ai)li=0.4*1+0.3*2+0.2*3+04*2=2
  3. 符号V ΣP(Ai)li=0.4*1+0.3*2+0.2*3+0.1*3=1.9
  4. 符号W ΣP(Ai)li=0.4*1+0.3*2+0.2*3+0.1*3=1.9
  5. 符号X ΣP(Ai)li=0.4*1+0.3*1+0.2*2+0.1*2=1.3
  6. 符号Y ΣP(Ai)li=0.4*1+0.3*2+0.2*2+0.1*1=1.5
  7. 符号Z ΣP(Ai)li=0.4*2+0.3*2+0.2*2+0.1*2=2

5_6 符号化の効率

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

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

P(Ai) T U V W X Y Z
A 0.4 00 0 0 0 0 0 00
B 0.3 01 10 10 01 1 10 10
C 0.2 10 110 110 011 11 11 11
D 0.1 11 1110 111 111 01 0 00
エントロピー 1.84 1.84 1.84 1.84 1.84 1.84 1.84
平均符号長 2 2 1.9 1.9 1.3 1.5 2
効率 0.92 0.92 0.97 0.97 142 1.23 0.92

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

 r元符号において生成される情報源{A1,A2,・・・,Am}を考え,記号Aiの生起確率をP(Ai)とする。シャノン・ファノの符号化法は次の通りである。

  1. AiをP(Ai)の大きい順に並べる。
  2. P(Ai)の和がほぼ等しくなるようにAiを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. A3>A4>A2>A5>A6>A1 (0.40>0.15>0.14>0.12>0.10>0.09)
  2. @A3,A4 | A2,A5,A6,A1 (0.55 | 0.45)
    AA3 | A4 (0.40 | 0.15)
      A2,A5 | A6,A1 (0.26 | 0.19)
    BA2 | A5  (0.16 | 0.12)
      A6 | A1  (0.10 | 0.09)
  3. A4=00,A3=10,A2=100,A5=101,A6=110,A1=111

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

  1. H=-0.09log20.09-0.14log20.14-0.40log20.40-0.15log20.15-0.12log20.12-0.10log20.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 ハフマンの符号化法

 r元符号において生成される情報源{A1,A2,・・・,Am}を考え,記号Aiの生起確率をP(Ai)とする。ハフマンの符号化法は次の通りである。

  1. AiをP(Ai)の大きい順に並べる。
  2. P(Ai)の最も小さい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. A3>A4>A2>A5>A6>A1 (0.40>0.15>0.14>0.12>0.10>0.09)
  2. @A1+A6=A7 P(A6)=0.09+0.10=0.19
    AA3>A7>A4>A2>A5 (0.40>0.19>0.15>0.14>0.12)
    BA2+A5=A8 P(A8)=0.14+0.12=0.26
    CA3>A8>A7>A4 (0.40>0.26>0.19>0.15)
    DA7+A4=A9 P(A9)=0.19+0.15=0.34
    EA3>A9>A8 (0.40>0.34>0.26)
    FA9+A8=A10 P(A10)=0.34+0.26=0.60
    GA3>A10 (0.60>0.40)
    HA3+A10=1
  3. A1=0000,A6=0001,A4=001,A2=010,A5=011,A3=1

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

  1. H=-0.09log20.09-0.14log20.14-0.40log20.40-0.15log20.15-0.12log20.12-0.10log20.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

≪参考資料≫

☆HOME☆ ☆数学のいずみ☆