Paper Info
Title
Multilevel Diversity Coding Systems: Rate Regions, Codes, Computation, & Forbidden Minors.
Abstract
The rate regions of multilevel diversity coding systems (MDCSs), a sub-class of the broader family of multi-source multi-sink networks with special structure, are investigated in a systematic way. We enumerate all non-isomorphic MDCS instances with at most three sources and four encoders. Then, the exact rate region of every one of these more than 7000 instances is proven via computations showing that the Shannon outer bound matches with a custom constructed linear code-based inner bound. 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, and so on. Also, it is shown 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 of arbitrary size that they inspired is introduced and proved. In particular, a series of embedding operations that preserve the property of sufficiency of scalar or vector codes is presented. The utility of these operations is demonstrated by boiling the thousands of MDCS instances for which scalar binary (superposition) codes are insufficient down to 12 (26) forbidden the smallest embedded MDCS instances.
Year
DOI
Venue
2014
10.1109/TIT.2016.2628791
IEEE Trans. Information Theory
Keywords
Field
DocType
Decoding,Network coding,Linear codes,Computers,Binary codes
Discrete mathematics,Embedding,Binary code,Scalar (physics),Block code,Expander code,Theoretical computer science,Linear code,Diversity coding,Mathematics,Binary number
Journal
Volume
Issue
ISSN
abs/1407.5659
1
0018-9448
Citations 
PageRank 
References 
3
0.44
0
Authors
3
Name
Order
Citations
PageRank
Congduan Li1407.75
Steven Weber272453.55
John MacLaren Walsh310717.90