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

3.2 符号の基本的性質

クラフトの定理
長さl1,l2,...,lMとなるM個の符号語を持つr元符号（r個のシンボルを用いた符号）が瞬時符号となりうるための必要十分条件は
$r^{-l_1}+r^{-l_2}+...+r^{-l_M}\le 1$
十分性の証明
長さiの符号語がni個あって、全体でlグループM個の符号語があるとすると、
$n_1r^{-1}+n_2r^{-2}+...+n_lr^{-l}\le 1$
$n_1r^{l-2}+n_2r^{l-3}+...+n_{-1}r^{-1} \le r^{l-1}$
nは必ず正なので
$n_1r^{l-2}+n_2r^{l-3}+...+n_{-2}r^{-2} \le r^{l-1}$
これを繰り返すと
$n_1 \le r$
となる。これは、符号の木の葉に符号語が必ず割り当てることができることを示している。
必要性の証明P50参照

非瞬時符号に対しても、この定理は成り立つ。
ただしこの定理では、一意復号不可能であるかどうかは判断できるが、一意復号可能であるかどうかは実際に符号語を検討しないと判断できない。

3.3 平均符号長の限界

平均符号長lを最小にする瞬時符号をコンパクト符号という

定理3.2
無記憶情報元LのエントロピーをH(L)としたとき、一意復号可能な符号語の平均符号長lに対して
$l \ge \frac{H(L)}{\log r}$
が成立する。
(証明は教科書参照)

定理3.3
無記憶情報元LのエントロピーをH(L)としたとき、一意復号可能な符号語の平均符号長lに対して
$l \lt \frac{H(L)}{\log r}+1$
を満たすr元瞬時符号が構成できる
(証明は教科書参照)

シャノンの符号化

各シンボルの生起確率Piを大きい順に並べる。
各符号に対し、その符号までの累積確率を求める。
累積確率を２進化したものを符合とする。ただし-log(Pa)桁目で打ち切る。

情報源符号化定理
無記憶情報源Lに対して拡大を繰り返すことにより、
$l=\frac{H(L)}{\log r}$ にいくらでも近づけることができる。

マルコフ情報源については
$\frac{H(L)}{\log r}+\frac{e_m}{n}\le \frac{l^n}{n} \lt\frac{H(L)}{\log r}+\frac{e_m}{n}+\frac{1}{n}$