情報通信システム 其の三 20170427

命題「ハフマン符号化法によりコンパクト符号になる(2元)」の証明

　まず補助定理を証明して本筋に適用する

　・コンパクト符号の符号の木の性質

　　①根から最も遠い位置にある葉は二つある

　　②この二つの葉に生起確率の小さいものから二つが割り当てられている

　　①の証明

　　　二つ無い場合(葉が一つの場合)を考える。この時、葉のない片方の枝は無視することができるので平均符号長を短くすることができる。つまり、これはこの符号がコンパクト符号であることであるという前提と矛盾が生じる。したがって①は真。

　　②の証明

　　　生起確率の小さいものが割り当てられていないと仮定する。この場合、ほかの葉にあるもっと生起確率の小さな事象と交換することによって平均符号長を短くすることができる。これは、この符号がコンパクト符号であるという前提と矛盾が生じる。したがって②は真。

　・命題の証明

　　帰納法と背理法により証明する。画像で乗っけます。

n次の拡大情報源s^n

　nこの情報源記号をまとめて一つの情報源記号(個数はM^n)とみなした情報源

　・ブロック符号化：拡大情報源s^nの符号化

　　例は画像で

　　これは各符号の生起確率の偏りが大きいほど威力を発揮する。

　しかし、nの値を増やしていけば無限に平均符号長が短くなるわけではない

　　⇒平均符号長の限界が存在する

情報源符号化定理

　　

　ただし、エントロピー

　　

　で表される値Lまで平均符号長を短くすることができる。さっきの例でいくと

　　

　となり、0.72程で限界が来てしまうことがわかる。