ハフマン符号の性能との限界、その他の符号化

前回の復習

4元のハフマン符号
- 何種類か木の作りかたがある => どの作り方がいいんだろう、どうやったら作れるだろう
- 仮想的な点を作って3k + 1個の節点を容易してあげればいいんじゃないんだろうか

ハフマン符号の性能と限界

ハフマン符号は理解しやすくて、しかも性能がよい
- 性能がよいのはどれくらいよいのか?

通報一個に符号一個を割り当てる
平均符号長の限界定理
- 任意の符号について、平均符号長は必ず $L \geq H_1(S)$ となる
- どんな効率的な符号化でも、平均符号長は一次エントロピー以上になる
- かなり重要な定理!!

平均符号長が $L < H_1(S) + 1$ となるような符号を構成することができる

シャノンの補助定理

$\sum_{i =1}^M q_i \leq 1$ を満たす任意の正数 $q_1, q_m$ に対し、
$- \sum_{i =1}^M p_i \log_2 q_i \leq - \sum_{i =1}^M p_i \log_2 p_i = H_1(s)$
等号成立は $p_1 = q_1, \cdots, p_M = q_M$ のとき、かつそのときのみ。

クラフトの不等式とシャノンの補助定理を使うと上の定理が証明できる
ハフマン符号についてはもっと強いことが言えて、ハフマン符号よりも平均符号長の小さな瞬時符号は存在しない、ということまで言える
- 証明は略

ハフマン符号化の拡張

ハフマン符号は2元の情報源の符号化には向かない

複数の通報をまとめて符号化(ブロック化符号)を考える
- 通報あたりの平均符号長を1以下にできるかも
- 2元情報源の符号化にも使える...かも?

まず、通報の系列をブロック化する
ブロック化された通報の系列をハフマン符号化する
符号語の系列を得る

平均符号長は改善されたけど、2つずつでブロック化するとして、3つきたときとかはどうするの?
ブロック長を大きくすると一通報あたりの平均符号長は小さくなる

ブロック符号化と平均符号長

「ブロック長を大きくすると一通報あたりの平均符号長は小さくなる」はどこまでよくなるのか?
n個単位でブロク化した通報 = n次拡大情報源 $S^n$ の通報1個

情報源符号化定理

一通報当たりの平均符号長に換算すると $\frac{H_1(S_n)}{n} \leq \frac{L_n}{n} < \frac{H_1(S^n)}{n} + \frac{1}{n}$ という不等式を得る
nを無限大に飛ばした場合、極限エントロピーを使って、に持っていける
- シャノンの情報源符号化定理!!