Minimum Expected Length of Fixed-to-Variable Lossless Compression Without Prefix Constraints

作者：Szpankowski Wojciech^*; Verdu Sergio

来源：IEEE Transactions on Information Theory, 2011, 57(7): 4017-4025.

DOI：10.1109/TIT.2011.2145590

• Analytic information theory
• fixed-to-variable lossless compression
• memoryless sources
• one-to-one codes
• Shannon theory
• source coding

The minimum expected length for fixed-to-variable length encoding of an n-block memoryless source with entropy H grows as nH + O(1), where the term O(1) lies between 0 and 1. However, this well-known performance is obtained under the implicit constraint that the code assigned to the whole n-block is a prefix code. Dropping the prefix constraint, which is rarely necessary at the block level, we show that the minimum expected length for a finite-alphabet memoryless source with known distribution grows as
nH - 1/2 log n + O(1)
unless the source is equiprobable. We also refine this result up to o(1) for those memoryless sources whose log probabilities do not reside on a lattice.

• 出版日期2011-7