research-article

Tight bounds on the redundancy of Huffman codes

Author:

D. ManstettenAuthors Info & Claims

IEEE Transactions on Information Theory, Volume 38, Issue 1

Pages 144 - 151

https://doi.org/10.1109/18.108260

Published: 01 September 2006 Publication History

Abstract

A method for deriving optimal upper bounds on the redundancy of binary Huffman codes in terms of the probability p ₁ of the most likely source letter is presented. This method will be used to compute bounds for all p ₁ý1/127, which were previously known only for a few special cases. Furthermore, the known optimal lower bound for binary Huffman codes is generalized to arbitrary code alphabets and some upper bounds for D -ary Huffman codes, 2ý D <ý, are given, which are the tightest possible for all p ₁ý1/2

Cited By

View all

Zahabi SNarimani HKhosravifard M(2023)On the Shortest Codeword of the Optimal RVLCIEEE Transactions on Information Theory10.1109/TIT.2023.325384369:7(4740-4745)Online publication date: 1-Jul-2023
https://dl.acm.org/doi/10.1109/TIT.2023.3253843
Javad-Kalbasi MKhosravifard M(2020)Some Tight Lower Bounds on the Redundancy of Optimal Binary Prefix-Free and Fix-Free CodesIEEE Transactions on Information Theory10.1109/TIT.2020.298730966:7(4419-4430)Online publication date: 18-Jun-2020
https://dl.acm.org/doi/10.1109/TIT.2020.2987309
Moffat A(2019)Huffman CodingACM Computing Surveys10.1145/334255552:4(1-35)Online publication date: 30-Aug-2019
https://dl.acm.org/doi/10.1145/3342555
Show More Cited By

Tight bounds on the redundancy of Huffman codes

Recommendations

Bounds on the redundancy of Huffman codes

New upper bounds on the redundancy of Huffman codes are provided. A bound that for 2/9 leq P_{1} leq 0.4 is sharper than the bound of Gallager, when the probability of the most likely source letter P_{1} is the only known probability is presented. The ...
Tight upper bounds on the redundancy of Huffman codes

Bounds on the redundancy of Huffman codes in terms of the probability p ₁ of the most likely source letter are provided. In particular, upper bounds are presented that are sharper than the bounds given recently by R.G. Gallager (ibid., vol.IT-24, no.6, ...
Tight Bounds on the Redundancy of Huffman Codes \hbox{ H }\hbox{ H }

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 ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

IEEE Transactions on Information Theory Volume 38, Issue 1

January 1992

228 pages

ISSN:0018-9448

Issue’s Table of Contents

Publisher

IEEE Press

Publication History

Published: 01 September 2006

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

9
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 01 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Zahabi SNarimani HKhosravifard M(2023)On the Shortest Codeword of the Optimal RVLCIEEE Transactions on Information Theory10.1109/TIT.2023.325384369:7(4740-4745)Online publication date: 1-Jul-2023
https://dl.acm.org/doi/10.1109/TIT.2023.3253843
Javad-Kalbasi MKhosravifard M(2020)Some Tight Lower Bounds on the Redundancy of Optimal Binary Prefix-Free and Fix-Free CodesIEEE Transactions on Information Theory10.1109/TIT.2020.298730966:7(4419-4430)Online publication date: 18-Jun-2020
https://dl.acm.org/doi/10.1109/TIT.2020.2987309
Moffat A(2019)Huffman CodingACM Computing Surveys10.1145/334255552:4(1-35)Online publication date: 30-Aug-2019
https://dl.acm.org/doi/10.1145/3342555
Dagan YFilmus YGabizon AMoran SHatami HMcKenzie PKing V(2017)Twenty (simple) questionsProceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing10.1145/3055399.3055422(9-21)Online publication date: 19-Jun-2017
https://dl.acm.org/doi/10.1145/3055399.3055422
Hu WYamamoto HHonda J(2017)Worst-case Redundancy of Optimal Binary AIFV Codes and Their Extended CodesIEEE Transactions on Information Theory10.1109/TIT.2017.269401763:8(5074-5086)Online publication date: 12-Jul-2017
https://dl.acm.org/doi/10.1109/TIT.2017.2694017
Kheradmand SKhosravifard MAaron Gulliver T(2015)The Redundancy of an Optimal Binary Fix-Free Code Is Not Greater Than 1 bitIEEE Transactions on Information Theory10.1109/TIT.2015.242540561:6(3549-3558)Online publication date: 15-May-2015
https://dl.acm.org/doi/10.1109/TIT.2015.2425405
Navarro GBrisaboa N(2005)New bounds on D-ary optimal codesInformation Processing Letters10.5555/1119488.111949396:5(178-184)Online publication date: 16-Dec-2005
https://dl.acm.org/doi/10.5555/1119488.1119493
Moffat ANeal RWitten I(1998)Arithmetic coding revisitedACM Transactions on Information Systems10.1145/290159.29016216:3(256-294)Online publication date: 1-Jul-1998
https://dl.acm.org/doi/10.1145/290159.290162
Moffat AZobel JSharman N(1997)Text Compression for Dynamic Document DatabasesIEEE Transactions on Knowledge and Data Engineering10.1109/69.5914549:2(302-313)Online publication date: 1-Mar-1997
https://dl.acm.org/doi/10.1109/69.591454

Abstract

Cited By

Recommendations

Bounds on the redundancy of Huffman codes

Tight upper bounds on the redundancy of Huffman codes