On the Redundancy Rate of FF and VF Source Codes for General Sources

摘要

本稿では，有限もしくは可算無限アルファベットの一般情報源に対する固定長符号の冗長度レートについて議論する．固定長ブロック凋定長符号語（FF）符号および可変長ブロック-固定長符号語（VF）符号に対して（i）符号化レートと上エントロピーレートの差，および（ii）符号化レートと自己情報量レートの差，という2種類の冗長度レートを考える．まず，固定長符号のクラスをFF符号のみに制限した場合に，定義（i）では冗長度レート0が達成可能であるが，定義（ii）では正となる場合があることを示す．次に，固定長符号のクラスをVF符号まで含むように広げると，定義（ii）の冗長度レートを0にできることを示す．%This paper is concerned with the redundancy rate of fixed length source code for a general source with a countably infinite alphabet. We evaluate the minimum achievable redundancy rate R of fixed-to-fixed length (FF) and variable-to-fixed length (VF) codes with two definitions of redundancy rates, which are (i) the difference between the coding rate and the spectral sup-entropy rate and (ii) the difference between the coding rate and the self information rate. First we show that, when we restrict the fixed-length code class within the class of FF codes, R with definition (i) is zero, but R with definition (ii) can be positive. Next we show that, by taking the VF codes into account, R with definition (ii) can be decreased to zero.