We consider the problem of bounding the average length of an optimal (Huffman) source code when only limited knowledge of the source symbol probability distribution is available. For instance, we provide tight upper and lower bounds on the average length of optimal source codes when only the largest or the smallest source symbol probability is known. Our results rely on basic results of majorization theory and on the Schur concavity of the minimum average length of variable-length source codes for discrete memoryless sources. In the way to prove our main result we also give closed formula expressions for the average length of Huffman codes for several classes of probability distributions.

Bounding the Average Length of Optimal Source Codes via Majorization Theory

CICALESE, Ferdinando;VACCARO, Ugo
2004-01-01

Abstract

We consider the problem of bounding the average length of an optimal (Huffman) source code when only limited knowledge of the source symbol probability distribution is available. For instance, we provide tight upper and lower bounds on the average length of optimal source codes when only the largest or the smallest source symbol probability is known. Our results rely on basic results of majorization theory and on the Schur concavity of the minimum average length of variable-length source codes for discrete memoryless sources. In the way to prove our main result we also give closed formula expressions for the average length of Huffman codes for several classes of probability distributions.
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11386/1000484
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 13
  • ???jsp.display-item.citation.isi??? 14
social impact