AIFV-m符号の反復構成法における最適性

摘要

Yamamoto，Tsuchihashi，Hondaが提案した2元AIFV符号（almost instantaneous fixed-to-variable length code）は，復号において最大2ビットの遅延を許容し，符号木の葉のみならず不完全内節点にも情報源記号を割り当て，複数の符号木を用いることでパフマン符号より優れた圧縮性能を実現している．さらに，Hu，Yamamoto，Hondaは，2元AIFV符号の拡張として，復号において最大mビットの遅延を許容し，m個の符号木を用いる2元AIFV-m符号を提案し，m≦4に対して最悪冗長度が1／mビットであることを証明した．Iwata，Yamamotoは，情報源に対して最良の平均符号長を達成するAIFV-m符号の構成法として反復構成法を一般化した．本稿では，AIFV-m符号における平均性能に対する最適化問題の一般化として，定常分布を有する有限マルコフシステムにおける平均性能に対する最適化問題を考え，反復構成法により最適な有限マルコフシステムが与えられることを示す．