Multilevel Diversity Coding Systems: Rate Regions, Codes, Computation, & Forbidden Minors
From MaRDI portal
Publication:2979097
DOI10.1109/TIT.2016.2628791zbMATH Open1359.94428arXiv1407.5659OpenAlexW2962901739MaRDI QIDQ2979097FDOQ2979097
Authors: Congduan Li, Steven Weber, John MacLaren Walsh 
Publication date: 2 May 2017
Published in: IEEE Transactions on Information Theory (Search for Journal in Brave)
Abstract: The rate regions of multilevel diversity coding systems (MDCS), a sub-class of the broader family of multi-source multi-sink networks with special structure, are investigated. After showing how to enumerate all non-isomorphic MDCS instances of a given size, the Shannon outer bound and several achievable inner bounds based on linear codes are given for the rate region of each non-isomorphic instance. For thousands of MDCS instances, the bounds match, and hence exact rate regions are proven. Results gained from these computations are summarized in key statistics involving aspects such as the sufficiency of scalar binary codes, the necessary size of vector binary codes, etc. Also, it is shown how to generate computer aided human readable converse proofs, as well as how to construct the codes for an achievability proof. Based on this large repository of rate regions, a series of results about general MDCS cases that they inspired are introduced and proved. In particular, a series of embedding operations that preserve the property of sufficiency of scalar or vector codes are presented. The utility of these operations is demonstrated by boiling the thousands of MDCS instances for which binary scalar codes are insufficient down to 12 forbidden smallest embedded MDCS instances.
Full work available at URL: https://arxiv.org/abs/1407.5659
Cited In (1)
This page was built for publication: Multilevel Diversity Coding Systems: Rate Regions, Codes, Computation, & Forbidden Minors
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2979097)
