The Explicit Coding Rate Region of Symmetric Multilevel Diversity Coding

Tao Guo, Raymond W. Yeung

TL;DR

This paper tackles the challenge of explicitly defining the achievable rates for a complex communication system called Symmetric Multilevel Diversity Coding (SMDC). The authors provide a practical, closed-form set of linear inequalities to precisely characterize this rate region, making it feasible to determine if a given communication rate is achievable, a task previously computationally prohibitive.

What Problem Does This Paper Address?

In communication systems, especially those dealing with multiple independent data streams (sources) that need to be transmitted efficiently and reliably, understanding the theoretical limits of achievable data rates is crucial. Symmetric Multilevel Diversity Coding (SMDC) is one such system where multiple sources are encoded and then decoded at different "levels" of quality or completeness. While it was known that a specific coding strategy called "superposition coding" is optimal for SMDC, its rate region was described by an infinite, implicit set of inequalities. This made it impossible to practically determine if a desired set of rates was achievable. The problem was akin to having a complex, unwritten rulebook that was too vast and vague to use. This paper aims to create a clear, finite, and explicit rulebook for SMDC.

Methods

The core of the paper's contribution lies in deriving an explicit, closed-form solution for a key function, $f_\alpha(\lambda)$, which was previously defined implicitly through a linear optimization problem. By solving this optimization problem, the authors were able to identify a finite subset of inequalities that fully characterize the SMDC rate region. Furthermore, they leverage the inherent symmetry of the SMDC problem to significantly reduce the number of inequalities that actually need to be checked for achievability. They also introduce a simplified "subset entropy inequality" that aids in proving the optimality of superposition coding.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • From Infinite to Finite: The most significant insight is transforming an uncountable set of implicit inequalities into a finite, explicit set. This is a major step towards practical analysis and design of SMDC systems.
  • Symmetry as a Shortcut: The paper demonstrates how exploiting the symmetry of the SMDC problem dramatically reduces the computational burden of checking rate achievability. This is a common theme in information theory, but its application here is particularly impactful.
  • Complexity Revealed: While the number of inequalities is reduced, the paper highlights that the complexity of these inequalities still grows exponentially with the number of levels ($L$), underscoring the inherent difficulty of SMDC for a large number of levels.
  • Simplified Proofs: The introduction of a weaker subset entropy inequality simplifies the proof of superposition coding's optimality, making the theoretical underpinnings more accessible.

Key Results

  • Explicit Rate Region Characterization: The paper provides a finite set of linear inequalities that precisely define the achievable rate region for SMDC for any number of levels $L$.
  • Reduced Verification Set: For a given rate tuple, the authors identify a significantly smaller subset of these inequalities that are sufficient for checking achievability, leveraging the problem's symmetry.
  • Complexity Bounds: The paper provides bounds on the size of this smaller set of inequalities, showing it grows at least exponentially with $L$.
  • Computational Feasibility: The explicit characterization makes checking rate achievability computationally feasible for practical values of $L$, unlike previous implicit methods.

Limitations and Future Work

The paper acknowledges that even with the reduced set of inequalities, the complexity of listing them grows exponentially with $L$, becoming unmanageable for $L > 15$. While the authors have made checking achievability more practical, they suggest that further research could explore polynomial-time algorithms for this task, given the structured nature of the inequalities. The results are also noted as potentially extensible to more general settings of multilevel diversity coding.

Summary updated

Abstract

It is well known that superposition coding, namely separately encoding the independent sources, is optimal for symmetric multilevel diversity coding (SMDC) (Yeung-Zhang 1999) for any L ≥ 2, where L is the number of levels of the coding system. However, the characterization of the coding rate region therein involves uncountably many linear inequalities and the constant term (i.e., the lower bound) in each inequality is given in terms of the solution of a linear optimization problem. Thus this implicit characterization of the coding rate region does not enable the determination of the achievability of a given rate tuple. In principle, the achievability of a given rate tuple can be determined by direct computation, but the complexity is prohibitive even for L = 5. In this paper, for any fixed L, we obtain in closed form a finite set of linear inequalities for characterizing the coding rate region. We further show by the symmetry of the problem that only a much smaller subset of this finite set of inequalities needs to be verified in determining the achievability of a given rate tuple. Yet, the cardinality of this smaller set grows at least exponentially fast with L. We also present a subset entropy inequality, which together with our explicit characterization of the coding rate region, is sufficient for proving the optimality of superposition coding.
BibTeX
@inproceedings{guo2018explicit,
  author = {Tao Guo and Raymond W. Yeung},
  title = {{The Explicit Coding Rate Region of Symmetric Multilevel Diversity Coding}},
  booktitle = {ISIT},
  year = {2018},
  doi = {10.1109/isit.2018.8437867},
}

Loading related content...

Figure