On Delayed Sequential Coding of Correlated Sources

Nan Ma, Ye Wang, Prakash Ishwar

Abstract

Motivated by video coding applications, this paper investigates the sequential coding of correlated sources with encoding and/or decoding frame-delays. We derive the fundamental tradeoffs between individual frame rates, distortions, and delays using a single-letter information-theoretic characterization. For temporally Gauss-Markov video sources, our results demonstrate that causal sequential encoding with just a one-frame-delayed decoder can match the sum-rate-MSE performance of joint coding. This reveals that even minimal delay holds the potential for significant performance improvements in low-latency communication systems.

Introduction: The Latency-Efficiency Tradeoff

In video compression, sequences of highly correlated frames must be processed efficiently. Traditional systems often rely on Differential Predictive Coded Modulation (DPCM), a causal architecture where the encoder and decoder only utilize current and past frames to minimize latency. However, there is a fundamental tension between latency (delay) and efficiency (rate-distortion). While Joint Coding (JC)—processing all frames simultaneously—provides the theoretical upper bound for compression efficiency, it introduces delays that are prohibitive for real-time applications.

Correlated video frames and motion trajectory across time.

This paper explores the "middle ground" of delayed sequential coding. We investigate whether allowing a small, fixed delay at either the encoder or the decoder can bridge the performance gap between causal systems and the global optimum of joint coding.

System Architectures and Methodology

The study employs an information-theoretic approach to characterize the rate-distortion region for several architectures:

  1. Causal-Causal (C–C): Zero-delay encoding and decoding, typical of standard DPCM.
  2. Causal-Noncausal (C–NC): Causal encoding paired with delayed (noncausal) decoding.
  3. Noncausal-Causal (NC–C): Delayed encoding with causal decoding.
  4. Joint Coding (JC): The benchmark where all frames are available to both the encoder and decoder.
Comparison of (a) Causal-Causal, (b) Causal-Noncausal, and (c) Joint Coding architectures.

The analysis focuses on sources that are spatially stationary memoryless and temporally Gauss-Markov. By using directed information measures, the authors track information flow across time steps to derive "single-letter" characterizations—simplified mathematical expressions that define the performance limits of these complex sequential systems.

Key Insights: The Power of Minimal Delay

The research yields several surprising theoretical results:

  • Optimality of DPCM: For Gauss-Markov sources, an idealized version of DPCM is proven to be the information-theoretically optimal strategy for purely causal (C-C) systems.
  • The "Magic" of One-Frame Delay: For a $k$-th order Gauss-Markov source, a causal encoder with a $k$-frame delayed decoder can exactly match the sum-rate performance of joint coding for a significant range of distortion values. Remarkably, for many standard models ($k=1$), just a single frame of delay is sufficient to reach the global optimum.
  • Encoder-Decoder Delay Symmetry: A "performance equivalence" exists between delaying the encoder versus the decoder. If the total system delay is identical, the achievable sum-rate remains the same regardless of where the delay is introduced.
  • Directed Information: The authors demonstrate that directed information, which accounts for the causal direction of time, is the natural tool for analyzing sequential coding problems, superseding standard mutual information in this context.

Results and Implications

The paper provides the first complete single-letter characterization for $T$-stage sequential coding with arbitrary delays. For Gauss-Markov sources under Mean Squared Error (MSE) constraints, explicit formulas identify the "nontrivial" region where the performance gap between sequential and joint coding completely vanishes with minimal delay.

While these results rely on the Gauss-Markov assumption—a standard proxy for video innovations—they provide a rigorous theoretical foundation for next-generation low-latency video standards. They suggest that strategic, minimal delays in decoding can significantly enhance compression efficiency without the massive latency penalties of full joint processing.

Conclusion

This work demonstrates that the gap between practical causal coding and theoretical joint coding is narrower than previously thought. By proving that minimal delays can achieve global optimality in sum-rate performance, the authors provide a compelling case for the design of "near-causal" codecs that balance real-time requirements with high-efficiency compression.

Summary updated

Abstract

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.
BibTeX
@misc{ma2007delayed,
  author = {Nan Ma and Ye Wang and Prakash Ishwar},
  title = {{On Delayed Sequential Coding of Correlated Sources}},
  year = {2007},
  eprint = {cs/0701197},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/cs/0701197},
}
Figure