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

復習

定理3.2,3.2は重要
シャノンの符号化

ファノの符号化法

情報源のシンボルをなるべく等確率になるように二つに分けることを繰り返す。（言いたいことはわかるけどなるべく等確率になるようにの判断が難しいな…）

ハフマン符号

省略させてください
ハフマン符号はコンパクト符号になる
ハフマン符号は一意に決定できるわけではないが、どのように構成しても平均符号長は等しくなる。
r元符号ならr個ずつセットでやればよい。r元の場合は、(r-1)n+1の葉ができるので、これに当てはまらない符号の個数だった時は生起確率0の符号を適当に追加する。