TY - JOUR
T1 - A unified graphical approach to random coding for single-hop networks
AU - Rini, Stefano
AU - Goldsmith, Andrea
N1 - Funding Information:
This work was supported in part by the National Science Foundation through the Center for Science of Information under Grant CCF-0939370 and in part by the Taiwanese Ministry of Science and Technology under Grant 103-2218-E-009-014-MY2. This paper was presented at the 2013 IEEE Information Theory and Applications Workshop. The authors would like to thank the Associate Editor and the reviewers for their detailed comments and suggestions on the manuscript, which served to greatly improve its presentation and clarity. They would also like to thank Professor Emre Teletar for his suggestions to include non-unique decoding in the analysis.
Publisher Copyright:
© 2015 IEEE.
PY - 2016/1/1
Y1 - 2016/1/1
N2 - A unified graphical approach to random coding for any memoryless, single-hop, K-user channel with or without common information is defined through two steps. The first step is user virtualization. Each user is divided into multiple virtual sub-users according to a chosen rate-splitting strategy. This results in an enhanced channel with a possibly larger number of users for which more coding possibilities are available and for which common messages to any subset of users can be encoded. Following user virtualization, the message of each user in the enhanced model is coded using a chosen combination of coded time-sharing, superposition coding, and joint binning. A graph is used to represent the chosen coding strategies. Nodes in the graph represent codewords, while edges represent coding operations. This graph is used to construct a graphical Markov model, which illustrates the statistical dependence among codewords that can be introduced by the superposition coding or joint binning. Using this statistical representation of the overall codebook distribution, the error probability of the code is shown to vanish through a unified analysis. The rate bounds that define the achievable rate region are obtained by linking the error analysis to the properties of the graphical Markov model. This proposed framework makes it possible to numerically obtain an achievable rate region by specifying a user virtualization strategy and describing a set of coding operations. The union of these rate regions defines the maximum achievable rate region of our unified coding strategy. The achievable rates obtained based on this unified graphical approach to random coding encompass the best random coding achievable rates for all memoryless single-hop networks known to date, including broadcast, multiple access, interference, and cognitive radio channels, as well as new results for topologies not previously studied, as we illustrate with several examples.
AB - A unified graphical approach to random coding for any memoryless, single-hop, K-user channel with or without common information is defined through two steps. The first step is user virtualization. Each user is divided into multiple virtual sub-users according to a chosen rate-splitting strategy. This results in an enhanced channel with a possibly larger number of users for which more coding possibilities are available and for which common messages to any subset of users can be encoded. Following user virtualization, the message of each user in the enhanced model is coded using a chosen combination of coded time-sharing, superposition coding, and joint binning. A graph is used to represent the chosen coding strategies. Nodes in the graph represent codewords, while edges represent coding operations. This graph is used to construct a graphical Markov model, which illustrates the statistical dependence among codewords that can be introduced by the superposition coding or joint binning. Using this statistical representation of the overall codebook distribution, the error probability of the code is shown to vanish through a unified analysis. The rate bounds that define the achievable rate region are obtained by linking the error analysis to the properties of the graphical Markov model. This proposed framework makes it possible to numerically obtain an achievable rate region by specifying a user virtualization strategy and describing a set of coding operations. The union of these rate regions defines the maximum achievable rate region of our unified coding strategy. The achievable rates obtained based on this unified graphical approach to random coding encompass the best random coding achievable rates for all memoryless single-hop networks known to date, including broadcast, multiple access, interference, and cognitive radio channels, as well as new results for topologies not previously studied, as we illustrate with several examples.
KW - Achievable
KW - Binning
KW - Chain graph
KW - Coded time-sharing
KW - Gelfand-Pinsker coding
KW - Graphical Markov model
KW - Random coding
KW - Rate region
KW - Rate-splitting
KW - Superposition coding
KW - User virtualization
KW - Wireless network
UR - http://www.scopus.com/inward/record.url?scp=84959220415&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84959220415&partnerID=8YFLogxK
U2 - 10.1109/TIT.2015.2484073
DO - 10.1109/TIT.2015.2484073
M3 - Article
AN - SCOPUS:84959220415
SN - 0018-9448
VL - 62
SP - 56
EP - 88
JO - IEEE Transactions on Information Theory
JF - IEEE Transactions on Information Theory
IS - 1
M1 - 7283625
ER -