準瞬時FV符号とその拡張符号

摘要

符号木を用いる情報源符号化において，一意復号可能なFV符号（fixed-to-variable length code)中で最小の平均符号長を達成できる最適な符号は，クラフトの定理とマクミランの定理から，ハフマン符号であると結論づけられていた.しかし，マクミランの定理は，1つの符号木を用いることを仮定しているため，定常無記憶情報源の場合でも，複数の符号木を用いるとハフマン符号より平均符号長の短い符号を構成できる可能性がある.実際，2個以上の符号木を用い，最大復号遅延を符号アルファベットが2元の場合は2ビット，K元(K ≥ 3)場合は1符号シンボル許す準瞬時FV符号（almost instantaneous fixed-to-variable length code, AIFV符号）は，ハフマン符号よりも短い平均符号長を達成することができる.本稿では，準瞬時FV符号の制約条件，符号化·復号化アルゴリズム，符号の構成法，準瞬時FV符号の拡張符号などについて紹介する.