A One-to-One Code and Its Anti-Redundancy
Wojciech Szpankowski · IEEE Transactions on Information Theory · 2008
One-to-one codes are ldquoone-shotrdquo codes that assign a distinct codeword to source symbols and are not necessarily prefix codes (more generally, uniquely decodable). Interestingly, as Wyner proved in 1972, for such codes the average code length can besmallerthan the source entropy. By how much? We call this difference theanti-redundancy. Various authors over the years have shown that the anti-redundancy can be as big as minus the logarithm of the source entropy. However, to the best of our knowledge precise estimates do not exist. In this note, we consider a block code of lengthngenerated for a binary memoryless source, and prove that the average anti-redundancy is -1/2 log2n+C+F(n)+o(1) whereCis a constant and eitherF(n) = 0 if log2(1-p)/pis irrational (wherepis the probability of generating a ldquo0rdquo) orF(n) is a fluctuating function as the code length increases. This relatively simple finding requires a combination of analytic tools such as precise evaluation of Bernoulli sums, the saddle point method, and theory of distribution of sequences modulo 1.