Title :
Tight upper bounds on the redundancy of Huffman codes
Author :
Capocelli, Renato M. ; De Santis, Alfredo
Author_Institution :
Dept. of Math., Rome Univ., Italy
fDate :
9/1/1989 12:00:00 AM
Abstract :
Bounds on the redundancy of Huffman codes in terms of the probability p1 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, p.668-74, Nov.1978) and by R.M. Capocelli et al. (ibid., vol. IT-32, no.6, p.854-857, Nov. 1986) for an interval 2/(2l+1+1)<p1<1/(2l-1), l⩾2. It is shown that the new bounds are the tightest possible for these intervals
Keywords :
codes; encoding; probability; redundancy; Huffman codes; most likely source letter; probability; redundancy; tight upper bounds; Encoding; Entropy; Information theory; Upper bound;
Journal_Title :
Information Theory, IEEE Transactions on
