New Bounds on the Expected Length of One-to-One Codes

In this correspondence we provide new bounds on the expected length L of a binary one-to-one code for a discrete random variable X with entropy H . We prove that L H \Gamma log(H + 1) \Gamma H log(1 + 1=H). This bound improves on previous results. Furthermore, we provide upper bounds on the expected length of the best code as function of H and the most likely source letter probability. Index Terms -- Source coding, one-to-one codes, non-prefix codes. 1 Introduction Let X be a discrete random variable which assumes values on a countable support set X . A binary encoding for X is a function that maps each element of X to a binary codeword. Without loss of generality, assume that X = f1; 2; :::; Ng, where N can be infinite. The probability that X takes the value i is p i . Throughout this paper we assume, without loss of generality, that p i p i+1 . Given an encoding, the expected length of the encoding is L(X) = N X i=1 p i n i (1) where n i is the length of the codeword used t..