Tight upper bounds on the redundancy of Huffman codes |
| |
Authors: | Capocelli RM De Santis A |
| |
Affiliation: | Dept. of Math., Rome Univ.; |
| |
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: | |
|
|