TY - GEN
T1 - Minimum expected length of fixed-to-variable lossless compression of memoryless sources
AU - Szpankowski, Wojciech
AU - Verdú, Sergio
PY - 2009
Y1 - 2009
N2 - 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 logn + O(1) unless the source is equiprobable.
AB - 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 logn + O(1) unless the source is equiprobable.
UR - http://www.scopus.com/inward/record.url?scp=70449495897&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=70449495897&partnerID=8YFLogxK
U2 - 10.1109/ISIT.2009.5205737
DO - 10.1109/ISIT.2009.5205737
M3 - Conference contribution
AN - SCOPUS:70449495897
SN - 9781424443130
T3 - IEEE International Symposium on Information Theory - Proceedings
SP - 369
EP - 373
BT - 2009 IEEE International Symposium on Information Theory, ISIT 2009
T2 - 2009 IEEE International Symposium on Information Theory, ISIT 2009
Y2 - 28 June 2009 through 3 July 2009
ER -