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 -