On the asymptotic redundancy of lossless block coding with two codeword lengths

摘要

With the additional constraint of requiring only two codeword lengths, lossless codes of blocks of size n generated by stationary memoryless binary sources are studied. For arbitrary /spl delta/>0, classical large-deviation inequalities imply the existence of codes attaining an expected redundancy of the order O(n/sup -1/2+/spl delta//). It is shown that it is not possible to construct lossless codes with two codeword lengths having rate of order better or equal to O(n/sup -1/2/).