Redundancy Estimates for the Literal Encoding of Messages Generated by a Bernoulli Source

The efficiency of an encoding is estimated by its redundancy $R$, and its complexity by the average delay $\overline N$. In the article literal codes are constructed for which $R\lesssim N^{-5/3}$. Thus a literal encoding can acquire the same redundancy as the block type, but with a significantly lower complexity. Also considered are output-uniform codes, an advantage of which is the absence of a running synchronization error. For such codes $\overline{N^{-1}}\lesssim R\lesssim\overline{N^{-1}}$, except for the case in which all input letters are equally probable, whereupon $R\leqslant\overline{N^{-2}}$ for infinitely many $\overline{N}$.