On the redundancy of optimal binary prefix-condition codes for finite and infinite sources (Corresp.)

Abstract

A new lower bound, which is the tightest possible, is obtained for the redundancy of optimal bimuy prefix-condition (OBPC) codes for a memoryless source for which the probability of the most likely source letter is known. It is shown that this bound, and upper bounds obtained by Gallager and Johnsen, hold for infinite as well as finite source alphabets. Also presented are bounds on the redundancy of OBPC codes for sources satisfying the condition that each of the first several probabilities in the list of source probabilities is sufficiently large relative to the sum of the remaining probabilities.