情報通信システム　其の四　20170511 - マエカワの備忘録的な何か

前回出てきた平均符号長の限界値であるエントロピー．なぜそうなるのかの証明．

命題

平均符号長は

　 $\displaystyle -\sum_{i=1}^Mp_i\log_rp_i$

まで短くすることができる．

補助定理2.2
　 $\displaystyle q_1+q_2+...+q_M\le1$

を満たすとき、

　 $\displaystyle -\sum_{i=1}^Mp_i\log_rq_i\ge-\sum_{i=1}^Mp_i\log_rp_i=H(s)$

が成立．等号は

　 $\displaystyle q_i=p_i (i=1,2,...,M)$

証明(補助定理2.2)

　 $\displaystyle -\sum_{i=1}^Mp_i\log_rq_i+\sum_{i=1}^Mp_i\log_rp_i=-\sum_{i=1}^Mp_i\log_r\frac{q_i}{p_i}$

指数関数 $\displaystyle e^x$ のマクローリン展開から得られる $\displaystyle \ln x\le x-1$ と低の変換公式より

　 $\displaystyle -\sum_{i=1}^Mp_i\log_r\frac{q_i}{p_i}\ge\sum_{i=1}^M\frac{p_i}{\ln r}\left(1-\frac{q_i}{p_i}\right)$

　 $\displaystyle \sum_{i=1}^M\frac{p_i}{\ln r}\left(1-\frac{q_i}{p_i}\right)=\frac{1}{\ln r}\left(\sum_{i=1}^Mp_i-\sum_{i=1}^Mq_i\right)$

　 $\displaystyle \frac{1}{\ln r}\left(\sum_{i=1}^Mp_i-\sum_{i=1}^Mq_i\right)=\frac{1}{\ln r}\left(1-\sum_{i=1}^Mq_i\right)\ge1$

よって証明．

補助定理2.3(シャノン符号の平均符号長)

情報源の生起確率が $\displaystyle p(s_1),p(s_2),...,p(s_M)$ である情報源 $\displaystyle s$ の平均符号長は次の性質を持ち、さらに平均符号長 $\displaystyle L$ じは左辺よりも短くすることはできない．

　 $\displaystyle H(s)\le L\le H(s)+1$

証明(補助定理2.3)

　 $\displaystyle L=\sum_{i=1}^Ml_ip(s_i)$

　 $\displaystyle \log_r\frac{1}{p(s_i)}\le l_i\le \log_r\frac{1}{p(s_i)}+1$

とおく．この不等式の左側について考えると、

　 $\displaystyle \frac{1}{p(s_i)}\le r^{l_i}$

　 $\displaystyle r^{-l_i}\le p(s_i)$

　 $\displaystyle \sum_{i=1}^Mr^{-l_i}\le\sum_{i=1}^Mp(s_i)=1$

となり、この不等式はクラフトの不等式になることがわかる．本題の証明は子の不等式自体の変形．

　 $\displaystyle p(s_i)\log_r\frac{1}{p(s_i)}\le p(s_i)l_i \le p(s_i)\left(\log_r\frac{1}{p(s_i)}+1\right)$

　 $\displaystyle \sum_{i=1}^Mp(s_i)\log_r\frac{1}{p(s_i)}\le \sum_{i=1}^Mp(s_i)l_i \le \sum_{i=1}^Mp(s_i)\left(\log_r\frac{1}{p(s_i)}+1\right)$

　 $\displaystyle \sum_{i=1}^Mp(s_i)\log_r\frac{1}{p(s_i)}\le \sum_{i=1}^Mp(s_i)l_i \le \sum_{i=1}^Mp(s_i)\log_r\frac{1}{p(s_i)}+\sum_{i=1}^Mp(s_i)$

　 $\displaystyle H(s)\le L \le H(s)+1$

次に、平均符号長は左辺よりも短くできないということを示していく．

　 $\displaystyle \begin{eqnarray} H(s)-L&=&-\sum_{i=1}^Mp(s_i)\log_rp(s_i)-\sum_{i=1}^Ml_ip(s_i)\\&=&-\sum_{i=1}^Mp(s_i)\log_rp(s_i)+\sum_{i=1}^Mp(s_i)\log_rr^{-l_i} \end{eqnarray}$
　 $\displaystyle \sum_{i=1}^Mr^{-l_i}\le 1$
と補助定理2.2より
　 $\displaystyle \left|\sum_{i=1}^Mp(s_i)\log_rp(s_i)\right|\le\left|\sum_{i=1}^Mp(s_i)\log_rr^{-l_i}\right|$
であることがわかるため
　 $\displaystyle H(s)-L\ge 0$
よって証明．と一緒に、命題も証明できた．

補助定理2.4(拡大情報源のエントロピー)
　 $\displaystyle H(s^n)=nH(s)$

　 $\displaystyle H(s)\le L\le H(s)+\frac{1}{n}$

第1式の証明は割愛
第2式の証明

　 $\displaystyle H(s^n)\le L^* \le H(s^n)+1$

　 $\displaystyle nH(s)\le nL\le nH(s)+1$

　 $\displaystyle H(s)\le L\le H(s)+\frac{1}{n}$

で証明できた．

　つまり、この第2式からいえることは $n\to\infty$ にすれば、 $L\to H(s)$ になるということ．
　　⇒しかし、場合によっては $n$ が大きくなりすぎて非効率
　　　⇒比等長情報源系列の登場

比等長情報源系列

　2種類の方法があるが、実質1種類みたいなもの．
　　①タンストール符号化
　　②ランレングスハフマン符号化
　これらの方法は、系列数を一定に保ちながら平均符号長を短くする(平均系列長を長くする)方法．

　まずタンストールから
　　例として $p(1)=0.2,p(0)=0.8$ で語数4の情報源を考えていく．
　　　step1:符号の木を確立が大きい方をつなげていく感じで書いていく
　　　step2:平均系列長 $\overline{n}$ と末端の数字についてハフマン符号化を行った際の平均符号長 $\acute{L}$ を計算する
　　　step3:1情報源あたりの平均符号長を $\displaystyle L=\frac{\acute{L}}{\overline{n}}$ より求める