Channel polarization: A method for constructing capacity-achieving codes for symmetric binary-input memoryless channels

A method is proposed, called channel polarization, to construct code sequences that achieve the symmetric capacity $I(W)$ of any given binary-input discrete memoryless channel (B-DMC) $W$. The symmetric capacity $I(W)$ is the highest rate achievable subject to using the input letters of the channel equiprobably and equals the capacity $C(W)$ if the channel has certain symmetry properties. Channel polarization refers to the fact that it is possible to synthesize, out of $N$ independent copies of a given B-DMC $W$, a different set of $N$ binary-input channels such that the capacities of the latter set, except for a negligible fraction of them, are either near 1 or near zero. This second set of $N$ channels are well-conditioned for channel coding: one need only send data at full rate through channels with capacity near 1 and at zero rate through the others. The main coding theorem proved in the paper states that, given any B-DMC $W$ with $I(W)>0$ and any fixed $0< \delta < I(W)$, there exists a sequence of polarization codes $\{{\mathscr C}_n;n\ge 1\}$ such that ${\mathscr C}_n$ has block length $N_n=2^n$, rate $R_n$ approaching $I(W)-\delta$, and probability of block decoding error $P_{e,n} \le \bigoh(2^{-n/4})$. The complexities of the encoder and decoder for ${\cal C}_n$ are each bounded by $\bigoh(n2^n)$, independently of the code rate. For channels with certain symmetries, the code construction is explicit, and for the binary erasure channel can be carried out in $\bigoh(n 2^n)$ complexity.