Minimum expected length of fixed-to-variable lossless compression of memoryless sources
Wojciech Szpankowski, Sergio Verdú · 2009
Conventional wisdom states that the minimum expected length for fixed-to-variable length encoding of an n-block memoryless source with entropy H grows as nH+O(1). However, this performance is obtained under the constraint that the code assigned to the whole n-block is a prefix code. Dropping this unnecessary constraint we show that the minimum expected length grows as nH - 1/2 log n + O(1) unless the source is equiprobable.