Cumulant generating function of codeword lengths in optimal lossless compression

Thomas A. Courtade, Sergio Verdu

Research output: Chapter in Book/Report/Conference proceedingConference contribution

31 Scopus citations

Abstract

This paper analyzes the distribution of the codeword lengths of the optimal lossless compression code without prefix constraints both in the non-asymptotic regime and in the asymptotic regime. The technique we use is based on upper and lower bounding the cumulant generating function of the optimum codeword lengths. In the context of prefix codes, the normalized version of this quantity was proposed by Campbell in 1965 as a generalized average length. We then use the one-shot bounds to analyze the large deviations (reliability function) and small deviations (normal approximation) of the asymptotic fundamental limit in the case of memoryless sources. In contrast to other approaches based on the method of types or the Berry-Esséen inequality, we are able to deal with sources with infinite alphabets.

Original languageEnglish (US)
Title of host publication2014 IEEE International Symposium on Information Theory, ISIT 2014
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages2494-2498
Number of pages5
ISBN (Print)9781479951864
DOIs
StatePublished - Jan 1 2014
Event2014 IEEE International Symposium on Information Theory, ISIT 2014 - Honolulu, HI, United States
Duration: Jun 29 2014Jul 4 2014

Publication series

NameIEEE International Symposium on Information Theory - Proceedings
ISSN (Print)2157-8095

Other

Other2014 IEEE International Symposium on Information Theory, ISIT 2014
Country/TerritoryUnited States
CityHonolulu, HI
Period6/29/147/4/14

All Science Journal Classification (ASJC) codes

  • Applied Mathematics
  • Modeling and Simulation
  • Theoretical Computer Science
  • Information Systems

Fingerprint

Dive into the research topics of 'Cumulant generating function of codeword lengths in optimal lossless compression'. Together they form a unique fingerprint.

Cite this