TY - JOUR

T1 - Minimum expected length of fixed-to-variable lossless compression without prefix constraints

AU - Szpankowski, Wojciech

AU - Verdú, Sergio

N1 - Funding Information:
Manuscript received July 30, 2009; revised January 17, 2011; accepted January 17, 2011. Date of current version June 22, 2011. This work was supported by the Science and Technology NSF Center for Science of Information under Grant CCF-0939370 and by the NSF under Grants CCF-0830140, CCF-0939370, and CCF-1016625. W. Szpankowski is with the Department of Computer Science, Purdue University, West Lafayette, IN 47907 USA (e-mail: [email protected]). S. Verdú is with the Department of Electrical Engineering, Princeton University, Princeton, NJ 08544 USA (e-mail: [email protected]). Communicated by E. Ordentlich, Associate Editor for Source Coding. Color versions of one or more of the figures in this paper are available online at http://ieeexplore.ieee.org. Digital Object Identifier 10.1109/TIT.2011.2145590

PY - 2011/7

Y1 - 2011/7

N2 - The minimum expected length for fixed-to-variable length encoding of an n -block memoryless source with entropy H grows as n H + 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 n H - 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.

AB - The minimum expected length for fixed-to-variable length encoding of an n -block memoryless source with entropy H grows as n H + 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 n H - 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.

KW - Analytic information theory

KW - Shannon theory

KW - fixed-to-variable lossless compression

KW - memoryless sources

KW - one-to-one codes

KW - source coding

UR - http://www.scopus.com/inward/record.url?scp=79959571406&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=79959571406&partnerID=8YFLogxK

U2 - 10.1109/TIT.2011.2145590

DO - 10.1109/TIT.2011.2145590

M3 - Article

AN - SCOPUS:79959571406

SN - 0018-9448

VL - 57

SP - 4017

EP - 4025

JO - IEEE Transactions on Information Theory

JF - IEEE Transactions on Information Theory

IS - 7

M1 - 5895099

ER -