Abstract: This paper presents polar coding schemes for the 2-user discrete memoryless broadcast channel (DM-BC) which achieve Marton's region with both common and private messages. This is the best achievable rate region known to date, and it is tight for all classes of 2-user DM-BCs whose capacity regions are known. To accomplish this task, we first construct polar codes for both the superposition as well as the binning strategy. By combining these two schemes, we obtain Marton's region with private messages only. Finally, we show how to handle the case of common information. The proposed coding schemes possess the usual advantages of polar codes, i.e., they have low encoding and decoding complexity and a super-polynomial decay rate of the error probability. We follow the lead of Goela, Abbe, and Gastpar, who recently introduced polar codes emulating the superposition and binning schemes. In order to align the polar indices, for both schemes, their solution involves some degradedness constraints that are assumed to hold between the auxiliary random variables and the channel outputs. To remove these constraints, we consider the transmission of $k$ blocks and employ a chaining construction that guarantees the proper alignment of the polarized indices. The techniques described in this work are quite general, and they can be adopted to many other multi-terminal scenarios whenever there polar indices need to be aligned.
Introduction
In information theory, a broadcast channel involves one sender transmitting information to multiple receivers. Determining the absolute capacity region—the maximum rates at which information can be reliably sent—for a general broadcast channel remains a significant open problem. Currently, the best known achievable rate region is "Marton's region" (or the Marton-Gelfand-Pinsker/MGP region when a common message is included).
Polar codes are highly attractive for these problems because they can achieve channel capacity with low computational complexity. Previous work by Goela, Abbe, and Gastpar successfully applied polar codes to broadcast channels using standard strategies like superposition coding and binning. However, to ensure the "reliable" polarized bit indices for different users aligned correctly, they had to assume specific "degradedness" conditions. This artificial constraint strictly limited the achievable rate region. This paper introduces a novel polar coding scheme that achieves the full Marton's region without needing these restrictive assumptions.
Methods: Index Alignment and Chaining
The core challenge in multi-user polar coding is that the subsets of polarized (reliable) bit indices differ for each user. If User 1's reliable bits do not naturally overlap with User 2's, standard polar coding fails to achieve optimal rates.
To remove the degradedness constraints, the authors introduce a block Markov encoding technique called chaining. Instead of sending a single isolated block of length $n$, they transmit $k$ consecutive blocks. Because the channels aren't degraded, some bit indices might be reliable for User 1 but noisy for User 2, and vice versa. To ensure both users can decode the necessary information, the encoder takes the "problematic" bits from one block and repeats (chains) them in specific, reliable positions in an adjacent block.
This chaining forces a specific, asymmetric decoding schedule:
- User 1 decodes "forward": Starting from block 1 and moving to block $k$.
- User 2 decodes "backwards": Waiting for all blocks to arrive, then starting at block $k$ and moving down to block 1.
The rate penalty incurred by repeating bits at the boundaries of the blocks scales as $1/k$. By letting the number of blocks $k \to \infty$, this penalty vanishes, allowing the scheme to achieve the theoretical maximum rates.
Key Results
The authors successfully constructed polar codes that achieve the full information-theoretic Bergmans' superposition region and the binning region, strictly improving upon previous designs for non-degraded channels. By combining these with three distinct chaining constructions, they achieved Marton's region for private messages and extended it to the full MGP region for common information.
As shown in the figure above, the proposed scheme (blue line) reaches the full information-theoretic region, whereas previous polar coding approaches (red dashed line) were limited by degradedness constraints, especially visible as $\epsilon$ increases. These schemes maintain the highly desirable properties of standard polar codes: $O(n \log n)$ encoding/decoding complexity per block and a block error probability that decays super-polynomially.
Conclusion and Future Work
While the current mathematical exposition focuses on binary auxiliary random variables, the chaining constructions used to align polarized indices are highly general. The block chaining approach does introduce some latency, as the "backward" decoding user must wait for all $k$ blocks to arrive. Future work involves adapting these techniques to other multi-user scenarios, such as $K$-user broadcast channels or interference networks, where index alignment is a critical bottleneck.
Summary updated