This paper considers the distribution of the optimum rate of fixed-to-variable lossless compression. It shows that in the non-asymptotic regime the fundamental limits of fixed-to-variable lossless compression with and without prefix constraints are tightly coupled. In addition to bounds in terms of the source information spectrum, it also gives an exact analysis of the fundamental limit for arbitrary sources. Gaussian approximations to the distribution of the optimum rate, and the concept of source dispersion are also characterized. Together with the entropy rate, the varentropy rate serves to tightly approximate the fundamental non-asymptotic limits for all but very small blocklengths.
展开▼
