Variable-length encoding of fixed-rate Markov sources for fixed-rate channels
F. Jelinek, K. Schneider · IEEE Transactions on Information Theory · 1974
The problem of buffer overflow in variable-length-to-block and block-to-variable-length coding of fixed-rate finite-state homogeneous Markov sources for transmission through fixed:rate noiseless channels is investigated. Asymptotically optimal converging upper and lower bounds on the probability of overflow are derived. They decrease exponentially with the buffer sizeB. The least ratesR(\gamma)that achieve exponents\gammafor both coding methods are obtained, as are the corresponding optimal word assignments. It is shown that for the class of state-calculable sources, variable-length-to-block and block-to-variable-length ratesR(\gamma)are equal.