aaa

Size: px

Start display at page:

Download "aaa"

さやしまむね
4 years ago
Views:

1 Information an Coing Theory, 07 by Toyoaki Nishia 情報源符号化とその限界 Copyright 07 Toyoaki Nishia All Rights Reserve.

2 本科目の構成情報源 information source 情報源符号器 source encoer 通信路符号器 channel encoer 通信路 channel 通信路復号器 channel ecoer 情報源復号器 source ecoer 受信者 estination 通信路符号 ( 例 :FAX, デジタル符号 ) 情報源符号 ( 例 : 文字 ) 通報 ( 例 : アイデア ) 雑音源 noise source

3 情報源のモデル化情報源 : 確率モデルを用いてモデル化する. ( 例 ) 人, 生命, 情報源情報源記号列 B C A B A 情報源モデル情報源記号 {A, B, C, D, } 情報源記号の生成を説明する確率モデル t

4 情報源符号化情報源から発せられる情報源記号 ( 列 ) を符号語列に変換する. 情報源情報源記号列 B C A B A 情報源モデル情報源記号 {A, B, C, D, } 符号語列 0 情報源符号化 BC, ABA 0, 符号アルファベット {0, }

5 平均符号長情報源情報源符号化 A 00, B 0, C 0, D 情報源モデル情報源記号 {A, B, C, D} p(a)=0.5, p(b)=0.5, p(c)=0.5, p(d)=0.5 平均符号長 = 符号アルファベット {0, }

6 平均符号長情報源情報源符号化 A 00, B 0, C 0, D 情報源モデル情報源記号 {A, B, C, D} p(a)=0.6, p(b)=0. p(c)=0., p(d)=0. 平均符号長 = 符号アルファベット {0, }

7 平均符号長情報源情報源符号化 A 0, B 0, C 0, D 情報源モデル情報源記号 {A, B, C, D} p(a)=0.6, p(b)=0. p(c)=0., p(d)=0. 平均符号長 = =.4 符号アルファベット {0, }

8 平均符号長さえ短ければいいのか? 情報源情報源モデル情報源記号 {A, B, C, D} p(a)=0.6, p(b)=0. p(c)=0., p(d)=0. 情報源符号化 A 0, B 0, C 0, D ADA? BC? 00 平均符号長 = =.4 符号アルファベット {0, }

9 符号化に課せられる条件一意復号可能性瞬時性

10 一意復号可能な符号情報源情報源符号化 A 0, B 0, C 0, D 情報源モデル情報源記号 {A, B, C, D} p(a)=0.6, p(b)=0. p(c)=0., p(d)=0. 平均符号長 = =.6 符号アルファベット {0, }

11 瞬時符号情報源情報源モデル情報源記号 {A, B, C, D} p(a)=0.6, p(b)=0. p(c)=0., p(d)=0. 一意復号可能だが非瞬時 A 0, B 0, C 0, D 瞬時符号 A 0, B 0, C 0, D 平均符号長 = =.6 符号アルファベット {0, }

12 ここまでのまとめ Shannon-Fano モデルいろいろな情報源情報源のモデル化情報源符号化平均符号長情報源符号の持つべき性質一意復号可能性, 瞬時性

13 残った疑問平均符号長はどこまで短くできるのか? 一意復号可能性の判定法? 瞬時符号の判定法? 平均符号長最短の符号 ( コンパクト符号 ) 構成法?

14 符号の分類符号語の長さによる分類等長符号非等長符号復号の可能性による分類可逆符号 - 瞬時符号 - 非瞬時符号非可逆符号

15 情報源符号化のタイプ ( 例 ) 各情報源記号ごとに符号語を割り当てる場合情報源記号符号 C C C3 C4 C5 C6 C7 A B C D E F 0 等長 / 非等長等長非等長非等長非等長非等長非等長非等長瞬時符号一意復号可能

16 瞬時性の判定情報源情報源符号化符号アルファベット {0, } 符号 : 一意復号可能, 非瞬時 A 0, B 0, C 0, D 情報源モデル情報源記号 {A, B, C, D} p(a)=0.6, p(b)=0. p(c)=0., p(d)=0. 符号 : 瞬時 A 0, B 0, C 0, D 平均符号長 = =.6

17 瞬時性の判定符号の木 : 符号化で使われる符号語の集合を構造的に表現したもの C ={00,00,0,0,0,} C ={0,0,00,0,}

18 瞬時性の判定符号の木で w i が w j の接頭 w i が w j の上流にある符号の木 t が接頭条件を満足する t のどの符号語も他の符号語の接頭になっていない. 符号化 C が瞬時符号である C に対する符号の木が接頭条件を満足している.

19 瞬時性の判定例 : 情報源記号 {A, A, A 3, A 4, A 5 } に対する元瞬時符号符号の木の原木瞬時符号 P 接頭条件を満たすように枝刈りする

20 瞬時性の判定例 : 情報源記号 {A, A, A 3, A 4, A 5 } に対する元瞬時符号瞬時符号 P 瞬時符号 Q 瞬時符号 R 符号長バッグ : {,, 3, 4, 5} 符号長バッグ : {3,, 3, 3, 4} 符号長バッグ : {4, 4, 5, 4, } 瞬時符号構成可能な符号語バッグの条件?

21 瞬時符号構成可能性クラフトの不等式 l, l,, l M c, c,, 長さの M 個の符号語をもつ q 元瞬時符号を構成できる. c M q l M q l q l 例題 : 長さ,,3,3 の 4 個の符号語をもつ元瞬時符号は構成可能か? 解答 :Yes!

22 瞬時符号構成可能性クラフトの不等式 l, l,, l M c, c,, 長さの M 個の符号語をもつ q 元瞬時符号を構成できる. c M q l M q l q l 直観的証明 : リソースという考え方を使う元符号の場合深さ( 長さ) 深さ( 長さ) 深さ3( 長さ3) - の重み - の重み -3 の重み長さの符号語 3 個 - 3 長さ 3 の符号語 3 個 -3 ここを足せばここを足せばここを足せば深さには個の符号語を割り当てられる.

23 一意復号可能な符号の構成可能性一意復号可能符号瞬時符号クラフトの不等式を満たす符号長をもつ符号を構成可能クラフトの不等式を満たさない符号長をもつ一意復元可能な符号を構成可能? NO! マクミランの不等式 l, l,, l M c, c,, c M 長さの M 個の符号語をもつ q 元一意復号可能な符号を構成できる. q l M q l q l

24 マクミランの不等式の証明という量に着目し, 一意に復元可能であるためには, でなければならないことを示す. という量について考えてみよう. はのなかの符号語を m 個つないでできるすべての系列 α について, を計算し, 加えたものに等しい. l n l l c c m c },,, { n c c c m c n=4, m=3 K(a ) K(a ) K(a 3 ) K(a 4 ) K(a ) K(a ) K(a 3 ) K(a 4 ) K(a ) K(a ) K(a 3 ) K(a 4 ) i i l l l N c 3 max 3 min ) ( ) ( ) ( ) ( 3 ) ( ) ( ) ( 一般には, i i m l m l l m N c max min m 3 n 4 ( 例 ) α=k(a ) K(a 4 ) K(a ) α =K(a ) K(a ) K(a 4 )

25 マクミランの不等式の証明所与の符号が一意復号可能であるためには, 長さ l になる系列の個数は, 長さ l の可能な l l 元符号語の個数を超えてはならない. つまり, Nl でなければならない. 従って, c l 前項で得られたN は,( 固定された l, l,, l に対して ) 任意のmについて成立しなければならない. m l mmin lmmax l i N i l mmin lmmax i l i l mmax( n i ) N l ここで m c m ( c ) m m m( c ) m( m )( c ) m ( m )( c ) であるので, c であればこの条件を満足できない. 従って, c でなければならない.

26 まとめ Shannon-Fano モデルいろいろな情報源情報源のモデル化情報源符号化平均符号長情報源符号の持つべき性質一意復号可能性, 瞬時性瞬時性の判定接頭条件瞬時符号構成可能性クラフトの不等式一意復号可能な符号の構成可能性マクミランの不等式残された課題 : 平均符号長はどこまで短くできるのか? 一意復号可能性の判定法? 平均符号長最短の符号の構成法?

Information Theory

Information Theory 前回の復習情報をコンパクトに表現するための符号化方式を考える情報源符号化における基礎的な性質一意復号可能性瞬時復号可能性クラフトの不等式 2 l 1 + + 2 l M 1 ハフマン符号の構成法 (2 元符号の場合 ) D. Huffman 1 前回の練習問題 : ハフマン符号符号木を再帰的に構成し, 符号を作る A B C D E F 確率 0.3 0.2 0.2 0.1 0.1 0.1