情報数理

2012年度
情報数理
～ Huffmanの符号化法Ⅱ ～
担当教員：幸山直人
2012年度情報数理
符号理論（講義前半）
符号理論（広義の符号理論）
＊統計・確率論
・情報量（ビットの導入） ⇒ 様々なデジタル情報
誤り訂正符号理論
暗号理論
圧縮理論
・・・
・情報の正確性
・情報の秘密性
・情報の効率性
2012年度情報数理
補助定理2.1の補足１（等号が成り立つ場合）
例として（生起確率が1/rkの形をしている場合）
s1
S＝ 1/2
s2
1/4
s3
1/4
s1 1/2
0
1/2
s2 1/4
1
1
0
1
s3 1/4
平均符号長 L＝1×1/2＋2×1/4＋2×1/4＝3/2
s1
(0)
s2
(10)
s3
(11)
2012年度情報数理
補助定理2.1の補足２（等号が成り立つ場合）
1/2
1/2
(s1,s1) 1/4
1/4
1/4
1/4
(s1,s2) 1/8
0
1
(s1,s3) 1/8
(s2,s1) 1/8
0
1
(s3,s1) 1/8
1/8
1/8
(s2,s2) 1/16
0
1
(s2,s3) 1/16
(s3,s2) 1/16
(s3,s3) 1/16
0
1
0
1
0
1
0
1
1
0
1
(s1,s1)
(s1,s2)
(s1,s3)
(s2,s1)
(s3,s1)
(s2,s2)
(s2,s3)
(s3,s2)
(s3,s3)
平均符号長 L＝2×1/4＋4×(3×1/8)＋ 4×(4×1/16) ＝3
１文字あたりの平均符号長（L/2）は3/2 ⇔ 最も短い符号
(00)
(010)
(011)
(100)
(101)
(1100)
(1101)
(1110)
(1111)
2012年度情報数理
これまでのまとめ
役立つ符号
特異でない
一意
瞬時
Kraftの不等式
瞬時に復号可能な符号の存在性
符号の木
コンパクト符号
Huffmanの符号化法Ⅰ
Huffmanの符号化法Ⅱ
平均符号長の下限
情報量

Download Report