Channel Polarization: A Method for Constructing Capacity-Achieving Codes for Symmetric Binary-Input Memoryless Channels

<para xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> A method is proposed, called channel polarization, to construct code sequences that achieve the symmetric capacity <emphasis emphasistype="italic"><formula formulatype="inline"><tex Notation="TeX">$I(W)$</tex></formula></emphasis> of any given binary-input discrete memoryless channel (B-DMC) <emphasis emphasistype="italic"><formula formulatype="inline"><tex Notation="TeX">$W$</tex></formula></emphasis>. The symmetric capacity is the highest rate achievable subject to using the input letters of the channel with equal probability. Channel polarization refers to the fact that it is possible to synthesize, out of <emphasis emphasistype="italic"><formula formulatype="inline"><tex Notation="TeX">$N$</tex></formula></emphasis> independent copies of a given B-DMC <emphasis emphasistype="italic"><formula formulatype="inline"> <tex Notation="TeX">$W$</tex></formula></emphasis>, a second set of <emphasis emphasistype="italic"><formula formulatype="inline"><tex Notation="TeX">$N$</tex> </formula></emphasis> binary-input channels <emphasis emphasistype="italic"><formula formulatype="inline"><tex Notation="TeX">$\{W_N^{(i)}:1\le i\le N\}$</tex> </formula></emphasis> such that, as <emphasis emphasistype="italic"><formula formulatype="inline"><tex Notation="TeX">$N$</tex></formula></emphasis> becomes large, the fraction of indices <emphasis emphasistype="italic"><formula formulatype="inline"> <tex Notation="TeX">$i$</tex></formula></emphasis> for which <emphasis emphasistype="italic"><formula formulatype="inline"><tex Notation="TeX">$I(W_N^{(i)})$</tex></formula></emphasis> is near <emphasis emphasistype="italic"><formula formulatype="inline"><tex Notation="TeX">$1$</tex> </formula></emphasis> approaches <emphasis emphasistype="italic"><formula formulatype="inline"><tex Notation="TeX">$I(W)$</tex></formula></emphasis> and the fraction for which <emphasis emphasistype="italic"><formula formulatype="inline"> <tex Notation="TeX">$I(W_N^{(i)})$</tex></formula></emphasis> is near <emphasis emphasistype="italic"><formula formulatype="inline"><tex Notation="TeX">$0$</tex> </formula></emphasis> approaches <emphasis emphasistype="italic"><formula formulatype="inline"><tex Notation="TeX">$1-I(W)$</tex></formula></emphasis>. The polarized channels <emphasis emphasistype="italic"><formula formulatype="inline"> <tex Notation="TeX">$\{W_N^{(i)}\}$</tex></formula></emphasis> are well-conditioned for channel coding: one need only send data at rate <emphasis emphasistype="italic"><formula formulatype="inline"><tex Notation="TeX">$1$</tex></formula></emphasis> through those with capacity near <emphasis emphasistype="italic"><formula formulatype="inline"> <tex Notation="TeX">$1$</tex></formula></emphasis> and at rate <emphasis emphasistype="italic"><formula formulatype="inline"><tex Notation="TeX">$0$</tex></formula></emphasis> through the remaining. Codes constructed on the basis of this idea are called polar codes. The paper proves that, given any B-DMC <emphasis emphasistype="italic"><formula formulatype="inline"><tex Notation="TeX">$W$</tex></formula></emphasis> with <emphasis emphasistype="italic"><formula formulatype="inline"><tex Notation="TeX">$I(W)&gt; 0$</tex></formula></emphasis> and any target rate <emphasis emphasistype="italic"><formula formulatype="inline"><tex Notation="TeX">$R ≪ I(W)$</tex></formula></emphasis>, there exists a sequence of polar codes <emphasis emphasistype="italic"><formula formulatype="inline"><tex Notation="TeX">$\{{\Fraktur {C}}_n;n\ge 1\}$</tex> </formula></emphasis> such that <emphasis emphasistype="italic"><formula formulatype="inline"> <tex Notation="TeX">${\Fraktur {C}}_n$</tex></formula></emphasis> has block-length <emphasis emphasistype="italic"><formula formulatype="inline"><tex Notation="TeX">$N=2^n$</tex> </formula></emphasis>, rate <emphasis emphasistype="italic"><formula formulatype="inline"> <tex Notation="TeX">$\ge R$</tex></formula></emphasis>, and probability of block error under successive cancellation decoding bounded as <emphasis emphasistype="italic"><formula formulatype="inline"><tex Notation="TeX">$P_{e}(N,R) \le O(N^{-{1\over 4}})$</tex> </formula></emphasis> independently of the code rate. This performance is achievable by encoders and decoders with complexity <emphasis emphasistype="italic"><formula formulatype="inline"><tex Notation="TeX">$O(N\log N)$</tex></formula></emphasis> for each. </para>