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

摘要

本稿では，定常無記憶情報源と一定でない伝送コストを有する有限状態無雑音通信路が与えられたとき，語頭符号において平均伝送コストの期待値の最小値を達成する符号の構成方法について考える．すなわち，GolinとRoteが示した伝送コストの期待値を最小とする構成法に対して，通信路における状態遷移関数が既知である場合への拡張を示す．その結果，通信路の各状態においてその状態から通信する場合，one-Shotの意味において伝送コストの期待値を最小とする語頭符号を情報源記号数に対して多項式時間オーダーを要する計算量とメモリ量で構成できる．%We consider a problem to build good prefix-free codes for stationary memoryless sources over finite-state noiseless channels with unequal symbol costs. The paper presents a shortest-path procedure in directed acyclic graphs to construct good prefix-free codes for the sources over the channels. The algorithm generalizes Golin and Rote's algorithm for constructing good prefix-free codes to the state dependent noiseless channel case by removing an assumption that codewords should begin and end at the same state. This algorithm runs in polynomial time for the size of the source alphabet when the costs are positive integers for each finite-state, and the state transition function is given.