定常無記憶情報源と（d, k）制約通信路に対する結合符号のMonge propertyを用いた動的計画法

摘要

定常無記憶情報源からの出力系列を各情報源記号毎に語頭符号を用いて，（d，k）制約を有する無雑普通進路を介して誤りなく伝送することを考える．ここでは定常無記憶情報源と状態遷移関数が既知である有限状態を有する正整数の伝送コスト付き無雑音通信路の結合符号化としてを考える．小文では，定常無記憶情報源と（d，k）制約を有する有限状態無雑音通進路が与えられたとき，語頭符号において平均伝送コストの期待値を小さくする符号の構成方法について考察する．その結果，（d, k）制約を有する無雑音通進路の各状態においてその状態から通信する場合，one-shotの意味において伝送コストの期待値を最小とする語頭符号が動的計画法においてMongeの行列を考慮することにより，情報源記号数nに対して計算量O（n~(∑(c_(max,s)) (s∈S)) ）で構成できることを述べる．ここで，Sは通信路における各状態sの集合であり，c_(max,s)は状態sにおける最大コストである．