Tight bounds on the AUH codes

Soheil Mohajer, Ali Kakhbod

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

4 Scopus citations

Abstract

In this paper we consider the class of anti-uniform Huffman codes and derive tight lower and upper bounds on the average length, entropy, and redundancy of such codes in terms of the alphabet size of the source. Also an upper bound on the entropy of AUH codes Is also presented in terms of the average cost of the code. The Fibonacci distributions are introduced which play a fundamental role in AUH codes. It is shown that such distributions maximize the average length and the entropy of the code for a given alphabet size. Another previously known bound on the entropy for given average length follows immediately from our results.

Original languageEnglish (US)
Title of host publicationCISS 2008, The 42nd Annual Conference on Information Sciences and Systems
Pages1010-1014
Number of pages5
DOIs
StatePublished - Sep 22 2008
EventCISS 2008, 42nd Annual Conference on Information Sciences and Systems - Princeton, NJ, United States
Duration: Mar 19 2008Mar 21 2008

Publication series

NameCISS 2008, The 42nd Annual Conference on Information Sciences and Systems

Other

OtherCISS 2008, 42nd Annual Conference on Information Sciences and Systems
CountryUnited States
CityPrinceton, NJ
Period3/19/083/21/08

Keywords

  • AUH codes
  • Average cost
  • Average length
  • Entropy
  • Fibonacci distributions
  • Redundancy

Fingerprint Dive into the research topics of 'Tight bounds on the AUH codes'. Together they form a unique fingerprint.

Cite this