第3章離散情報源の符号化 (3)

情報理論

算術符号

情報源シンボル系列⇒系列の累積確率[0,1)の2進表現（符号も2元）

例）
P(0)=0.7 P(1)=0.3

累積確率二進表現符号
P(000)=0.343 0 .00000...00
P(001)=0.147 0.343 .01010...010
P(010)=0.147 0.49 .01111...011
P(011)=0.063 0.637 .10100...1010
P(100)=0.147 0.7 .10110...1011
P(101)=0.063 0.847 .11011...110
P(110)=0.063 0.91 .11101...1110
P(111)=0.027 0.973 .11111...1111
前後の符号と重ならないところまで符号語長を決める

計算法

演算による比較ができる。表を覚える必要がない。
符号語長さえ共通になっていればいい。小数点以下の桁数が多くなると困るので長さにある程度の制限が必要。シフトとかでごまかして演算すると良い感じ。

3.5 ひずみが許される場合の情報源符号化法

ひずみ：情報源の系列と、それを符号化して復号した系列との差
ひずみ測度 d(x,y) x:元系列 y:復号系列
例)

  • d(x,y)={0 (x=y), 1 (x≠y)
  • d(x,y)=(x-y)^r

平均ひずみ \overline{d}=\sum_x \sum_y d(x,y)p(x,y)

ひずみがない場合：復号結果が得られれば元の系列が完全にわかる。平均情報量H(X)
ひずみがある場合：復号結果が得られても元の系列に対しあいまいさが残る。平均情報量H(X|Y)。相互情報量I(X;Y)=H(X)-H(X|Y)がひずみ
話は簡単ではない

  • 相互情報量が同じでも符号化の仕方により平均ひずみが異なる
  • 平均ひずみが同じでも符号化の仕方により相互情報量が異なる

平均ひずみdがD以下という条件であらゆる符号化を考えたときのI(X;Y)をR(D)＝min(d≦D)I(X;Y)とし、情報源の測度ひずみ関数という。

定理3.7
平均ひずみをD以下に抑えるという条件の下で1情報源記号あたりの平均符号語長が
\frac{R(D)}{\log(r)} \le l \lt \frac{R(D)}{\log(r)} + \varepsilon
となるr元符号が存在する。

符号化法

図3.9とか参照
情報源からの符号をいくつかをまとめて個数を減らして、あとはひずみのない符号化をする。確率の小さいものをまとめる。

中間試験範囲：1,2,3章（隠れマルコフはなし）