• DocumentCode
    1162012
  • Title

    Tight bounds on the redundancy of Huffman codes

  • Author

    Manstetten, Dietrich

  • Author_Institution
    Lehrstuhl fuer Angewandte Math. Insbesondere Inf., RWTH Aachen, Germany
  • Volume
    38
  • Issue
    1
  • fYear
    1992
  • fDate
    1/1/1992 12:00:00 AM
  • Firstpage
    144
  • Lastpage
    151
  • Abstract
    A method for deriving optimal upper bounds on the redundancy of binary Huffman codes in terms of the probability p1 of the most likely source letter is presented. This method will be used to compute bounds for all p1⩾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 p1⩾1/2
  • Keywords
    codes; redundancy; D-ary codes; Huffman codes; arbitrary code alphabets; binary codes; most likely source letter probability; optimal lower bound; optimal upper bounds; redundancy; tight bounds; Codes; Entropy; Probability distribution; Upper bound;
  • fLanguage
    English
  • Journal_Title
    Information Theory, IEEE Transactions on
  • Publisher
    ieee
  • ISSN
    0018-9448
  • Type

    jour

  • DOI
    10.1109/18.108260
  • Filename
    108260
    • Link To Document
    https://search.isc.ac/dl/search/defaultta.aspx?DTC=49&DC=1162012