On the Asymptotic Redundancy of Lossless Block Coding With Two Codeword Lengths
Enrique Figueroa, Christian Houdré · IEEE Transactions on Information Theory · 2005
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/).