Polar codes for broadcast channels

Building on polar code constructions proposed by the authors for deterministic broadcast channels, two theorems are introduced in the present paper for noisy two-user broadcast channels. The theorems establish polar code constructions for two important information-theoretic broadcast strategies: (1) Cover´s superposition strategy; (2) Marton´s construction. One aspect of the polar code constructions is the alignment of polarization indices via constraints placed on the auxiliary and channel-input distributions. The codes achieve capacity-optimal rates for several classes of broadcast channels (e.g., binary-input stochastically degraded channels). Applying Arıkan´s original matrix kernel for polarization, it is shown that the average probability of error in decoding two private messages at the broadcast receivers decays as O(2(-n^β)) where 0 <; β <; 1/2 and n is the code length. The encoding and decoding complexities remain O(n log n). The error analysis is made possible by defining new polar code ensembles for broadcast channels.