一般情報源に対する可変長符号化定理#12539;可変長乱数生成問題

摘要

本論文では無記憶性や定常エルゴード性を仮定しない一般の情報源に対する可変長符号化の問題，及び一般の情報源を決定的な写像を用いて一様乱数に変換する方法を，情報スペクトル的な立場から論じる．本論文ではまず，情報スペクトルの分野でよく用いられる一般情報源や一様可積分性の概念を説明する．次に一般情報源Xの可変長符号化の問題を定式化し，達成可能な最小の平均符号語長の限界R_v（X）について述べる．更に，一般情報源から可変長の一様乱数を生成する問題を定式化し，達成可能な最大の平均出力長S_v（X）を明らかにする．最後に，R_v（X）＝S_v（X）を満たす一般情報源に対しては，R_v（X）を達成するある最適な可変長符号が，S_v（X）を達成する最適な可変長一様乱数生成器ともみなせることを述べる．