Universal Zero-Delay Joint Source-Channel Coding

We consider zero-delay joint source-channel coding of individual source sequences for a general known channel. Given an arbitrary finite set of schemes with finite-memory (not necessarily time-invariant) decoders, a scheme is devised that does essentially as well as the best in the set on all individual source sequences. Using this scheme, we construct a universal zero-delay joint source-channel coding scheme that is guaranteed to achieve, asymptotically, the performance of the best zero-delay encoding-decoding scheme with a finite-state encoder and a Markov decoder, on all individual sequences. For the case where the channel is a DMC, we construct an implementable zero-delay joint source-channel coding scheme that is based on the “follow the perturbed leader ” scheme of György et al. for lossy source coding of individual sequences. Our scheme is guaranteed to attain asymptotically the performance of the best in the set of all encoding-decoding schemes with a “symbol by symbol ” decoder (and arbitrary encoder), on all individual sequences. Key words and phrases: Discrete memoryless channel (DMC), Finite-state encoder/decoder, Individual sequences, Joint source-channel coding, Markov encoder/decoder, Zero-delay schemes.