Towards an Algebraic Network Information Theory: Simultaneous Joint Typicality Decoding

Abstract

Consider a receiver in a multi-user network that wishes to decode several messages. Simultaneous joint typicality decoding is one of the most powerful techniques for determining the fundamental limits at which reliable decoding is possible. This technique has historically been used in conjunction with random i.i.d. codebooks to establish achievable rate regions for networks. Recently, it has been shown that, in certain scenarios, nested linear codebooks in conjunction with "single-user" or sequential decoding can yield better achievable rates. For instance, the compute-forward problem examines the scenario of recovering $L\le K$ linear combinations of transmitted codewords over a $K$-user multiple-access channel (MAC), and it is well established that linear codebooks can yield higher rates. Here, we develop bounds for simultaneous joint typicality decoding used in conjunction with nested linear codebooks, and apply them to obtain a larger achievable region for compute-forward over a $K$-user discrete memoryless MAC. The key technical challenge is that competing codeword tuples that are linearly dependent on the true codeword tuple introduce statistical dependencies, which requires careful partitioning of the associated error events.

arXiv comment24 pages, 5 figures, submitted to IEEE Transactions on Information Theory

References in corpus (8)

• The Approximate Capacity of the Many-to-One and One-to-Many Gaussian Interference Channels
• Secure Degrees of Freedom of One-hop Wireless Networks
• Providing Secrecy With Structured Codes: Tools and Applications to Two-User Gaussian Channels
• Expanding the Compute-and-Forward Framework: Unequal Powers, Signal Levels, and Multiple Linear Combinations
• Gaussian Multiple Access via Compute-and-Forward
• Secure Compute-and-Forward in a Bidirectional Relay
• An Achievable rate region for the $3-$user interference channel based on coset codes
• Linear Coding Schemes for the Distributed Computation of Subspaces