On the cost of worst case coding length constraints

Dror Baron, Andrew C. Singer

Research output: Contribution to journalArticlepeer-review


We investigate the redundancy that arises from adding a worst case length constraint to uniquely decodable fixed-to-variable codes over achievable Huffman codes. This is in contrast to the traditional metric of the redundancy over the entropy. We show that the cost for adding constraints on the worst case coding length is small, and that the resulting bound is related to the Fibonacci numbers.

Original languageEnglish (US)
Pages (from-to)3088-3090
Number of pages3
JournalIEEE Transactions on Information Theory
Issue number7
StatePublished - Nov 2001


  • Data compression
  • Fibonacci numbers
  • Huffman coding
  • Redundancy
  • Source coding
  • Uniquely decodable

ASJC Scopus subject areas

  • Information Systems
  • Computer Science Applications
  • Library and Information Sciences


Dive into the research topics of 'On the cost of worst case coding length constraints'. Together they form a unique fingerprint.

Cite this