東京大学 大学院新領域創成科学研究科 複雑理工学専攻

Hiroki KOGA and Hiorsuke YAMAMOTO

IEEE Trans. on Information Theory, Vol. 51, No.4, pp.1546-1555, April 2005

• This correspondence is concerned with asymptotic properties on the codeword length of a fixed-to-variable length code (FV code) for a general source $\{X^n\}_{n=1}^{\infty}$ with a finite or countably infinite alphabet. Suppose that for each $n\geq 1$, $X^n$ is encoded to a binary codeword $phi_n(X^n))$ of length $l(phi_n(X^n))$. Letting $\varepsilon$denote the decoding error probability, we consider the following two criteria on FV codes: i) $\varepsilon= 0$ for all $n\geq 1$ and ii) $\limsup_{n\rightarrow\infty} \varepsilon_n \leq \varepsilon$ for an arbitrarily given $\varepsilon\in[0 1)$. Under criterion i), we show that, if is encoded by an arbitrary prefix-free FV code asymptotically achieving the entropy, $$ \frac{1}{n}l(\phi(_n(X^n))-frac{1}{n}\log_2 \frac{1}{P_{X^N}(X^N) \right arrow 0 $$ in probability as $n\rightarrow \infty$ under a certain condition, where $P_{X^N}$ denotes the probability distribution of $X^n$. Under criterion ii), we first determine the minimum rate achieved by FVcodes. Next, we showthat $\frac{1}{n}l(\phi (X^n))$ of an arbitrary FV code achieving the minimum rate in a certain sense has a property similar to the lossless case.
• Index Terms―Asymptotic optimality, convergence in distribution, fixed-to-variable length coding, general source, information spectrum.
• DOI: 10.1109/TIT.2005.844098