On the structure of optimal real-time encoders and decoders in noisy communication

The output of a discrete-time Markov source must be encoded into a sequence of discrete variables. The encoded sequence is transmitted through a noisy channel to a receiver that must attempt to reproduce reliably the source sequence. Encoding and decoding must be done in real-time and the distortion measure does not tolerate delays. The structure of real-time encoding and decoding strategies that jointly minimize an average distortion measure over a finite horizon is determined. The results are extended to the real-time broadcast problem and a real-time variation of the Wyner-Ziv problem. Index Terms--Markov chains, Markov decision theory, real-time decoding, real-time encoding.