Tight Bounds on the Redundancy of Huffman Codes\hbox{ H }\hbox{ H }

DOI10.1109/TIT.2012.2208580MaRDI QIDQ2989692zbMATH OpenOpenAlexFDO

Authors S. Mohajer, Payam Pakzad, A. Kakhbod

Publication date 8 June 2017

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/cs/0508039

Mathematics Subject Classification ID

Combinatorial codes (94B25)

Abstract: In this paper we study the redundancy of Huffman codes. In particular, we consider sources for which the probability of one of the source symbols is known. We prove a conjecture of Ye and Yeung regarding the upper bound on the redundancy of such Huffman codes, which yields in a tight upper bound. We also derive a tight lower bound for the redundancy under the same assumption. We further apply the method introduced in this paper to other related problems. It is shown that several other previously known bounds with different constraints follow immediately from our results.

Cited in

(5)

• scientific article; zbMATH DE number 4210045 (Why is no real title available?)
• On the redundancy of \(D\)-ary Fano codes
• Exact and Experimental Algorithms for a Huffman-Based Error Detecting Code
• A lower-bound for the maximin redundancy in pattern coding
• Redundancy-Related Bounds for Generalized Huffman Codes

This page was built for publication: Tight Bounds on the Redundancy of Huffman Codes\hbox{ H }\hbox{ H }

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2989692)