Lower Bounds on the Redundancy of Huffman Codes with Known and Unknown Probabilities

Ian Blanes, Miguel Hernandez-Cabronero, Joan Serra-Sagrista, Michael W. Marcellin

Research output: Contribution to journalArticlepeer-review

5 Scopus citations

Abstract

In this paper, we provide a method to obtain tight lower bounds on the minimum redundancy achievable by a Huffman code when the probability distribution underlying an alphabet is only partially known. In particular, we address the case where the occurrence probabilities are unknown for some of the symbols in an alphabet. Bounds can be obtained for alphabets of a given size, for alphabets of up to a given size, and alphabets of arbitrary size. The method operates on a computer algebra system, yielding closed-form numbers for all results. Finally, we show the potential of the proposed method to shed some light on the structure of the minimum redundancy achievable by the Huffman code.

Original languageEnglish (US)
Article number8782526
Pages (from-to)115857-115870
Number of pages14
JournalIEEE Access
Volume7
DOIs
StatePublished - 2019
Externally publishedYes

Keywords

  • Huffman code
  • lower bounds
  • redundancy

ASJC Scopus subject areas

  • General Computer Science
  • General Materials Science
  • General Engineering

Fingerprint

Dive into the research topics of 'Lower Bounds on the Redundancy of Huffman Codes with Known and Unknown Probabilities'. Together they form a unique fingerprint.

Cite this