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

DOI10.1109/TIT.2012.2208580zbMATH Open1364.94680arXivcs/0508039OpenAlexW2066846147MaRDI QIDQ2989692FDOQ2989692

Authors: S. Mohajer, Payam Pakzad, A. Kakhbod 

Publication date: 8 June 2017

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

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.

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

Mathematics Subject Classification ID

Combinatorial codes (94B25)

Cited In (5)

• Exact and Experimental Algorithms for a Huffman-Based Error Detecting Code
• On the redundancy of \(D\)-ary Fano codes
• Redundancy-Related Bounds for Generalized Huffman Codes
• A lower-bound for the maximin redundancy in pattern coding
• Title not available (Why is that?)

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)