有限状態無雑音通信路に適した語頭符号の構成法

摘要

本稿では，定常無記憶情報源と一定でない伝送コストを有する有限状態無雑音通信路が与えられたとき，語頭符号において平均伝送コストの期待値の最小値を達成する符号の構成方法について考える．すなわち，GolinとRoteが示した伝送コストの期待値を最小とする構成法に対して，通信路における状態遷移関数が既知である場合への拡張を示す．その結果，通信路の各状態においてその状態から通信する場合，one-Shotの意味において伝送コストの期待値を最小とする語頭符号を情報源記号数に対して多項式時間オーダーを要する計算量とメモリ量で構成できる．