  Motivated by video coding applications, the problem of sequential coding of
correlated sources with encoding and/or decoding frame-delays is studied. The
fundamental tradeoffs between individual frame rates, individual frame
distortions, and encoding/decoding frame-delays are derived in terms of a
single-letter information-theoretic characterization of the rate-distortion
region for general inter-frame source correlations and certain types of
potentially frame specific and coupled single-letter fidelity criteria. The
sum-rate-distortion region is characterized in terms of generalized directed
information measures highlighting their role in delayed sequential source
coding problems. For video sources which are spatially stationary memoryless
and temporally Gauss-Markov, MSE frame distortions, and a sum-rate constraint,
our results expose the optimality of idealized differential predictive coding
among all causal sequential coders, when the encoder uses a positive rate to
describe each frame. Somewhat surprisingly, causal sequential encoding with
one-frame-delayed noncausal sequential decoding can exactly match the
sum-rate-MSE performance of joint coding for all nontrivial MSE-tuples
satisfying certain positive semi-definiteness conditions. Thus, even a single
frame-delay holds potential for yielding significant performance improvements.
Generalizations to higher order Markov sources are also presented and
discussed. A rate-distortion performance equivalence between, causal sequential
encoding with delayed noncausal sequential decoding, and, delayed noncausal
sequential encoding with causal sequential decoding, is also established.
