Prospicient Real-Time Coding of Markov Sources over Burst Erasure Channels: Lossless Case

We introduce a framework to study fundamental limits of sequential coding of Markov sources under an error propagation constraint. An encoder sequentially compresses a sequence of vector-sources that are spatially i.i.d. but temporally correlated according to a Markov process. The channel erases up to B packets in a single burst, but reveals all other packets to the destination. The destination is required to reproduce all the source-vectors instantaneously and in a loss less manner, except those sequences that occur in a window of length B+W following the start of the erasure burst. We define a rate-recovery function R(B, W), the minimum compression rate that can be achieved in this framework, and develop upper and lower bounds for first-order Markov sources. For the special class of linear diagonally correlated deterministic sources, we propose a new coding technique -- prospicient coding -- that achieves the rate-recovery function. Finally, a lossy extension to the rate-recovery function is also studied for a class of Gaussian sources where the source is temporally and spatially i.i.d. and the decoder aims to recover a collection of past K sources with a quadratic distortion measure. The optimal rate-recovery function is compared with the sub-optimal techniques including forward error correction coding (FEC) and Wyner-Ziv coding, and performance gains are quantified.