Ferkans — Interactive Telecom Tutor

Definition:
Channel Polarization

Channel polarization is the phenomenon discovered by Arikan (2009) in which $N$ independent copies of a binary-input discrete memoryless channel $W$ are transformed, through a recursive linear operation, into $N$ synthetic channels $W_N^{(i)}$ , $i = 1, \ldots, N$ , such that as $N \to \infty$ :

A fraction $I(W)$ of the synthetic channels become perfectly reliable (capacity $\to 1$ ).
The remaining fraction $1 - I(W)$ become completely noisy (capacity $\to 0$ ).

The transformation uses the $N \times N$ polarization matrix

$\mathbf{G}_N = \mathbf{B}_N \mathbf{F}^{\otimes n}$

where $\mathbf{F} = \begin{bmatrix} 1 & 0 \\ 1 & 1 \end{bmatrix}$ , $N = 2^n$ , $\mathbf{F}^{\otimes n}$ is the $n$ -th Kronecker power of $\mathbf{F}$ , and $\mathbf{B}_N$ is a bit-reversal permutation.

A polar code of rate $R_c$ transmits information on the $K = NR_c$ most reliable synthetic channels and sends frozen bits (known values, typically 0) on the remaining $N - K$ channels.

Polar codes are the first provably capacity-achieving codes with explicit construction and polynomial encoding/decoding complexity.

Channel Polarization Visualised

Visualises Arikan's channel polarization:

N = 8

identical channels are transformed into synthetic channels that polarise to capacity 0 or 1. The animation shows the bar chart of channel capacities morphing from uniform to polarised, followed by information/frozen bit assignment for polar code construction.

Channel polarization drives synthetic channel capacities to extremes, enabling polar code construction by selecting the most reliable channels for information bits.

Successive Cancellation (SC) Decoding

Successive cancellation decoding estimates the bits one at a

time in the order

u_1, u_2, \ldots, u_N

, using the channel

outputs and all previously decoded bits:

\hat{u}_i = \begin{cases} 0 & \text{if } i \in \mathcal{F} \text{ (frozen bit)} \\ 0 & \text{if } L_N^{(i)}(\mathbf{y}, \hat{u}_1^{i-1}) \geq 0 \\ 1 & \text{otherwise} \end{cases}

where

L_N^{(i)}

is the log-likelihood ratio computed recursively

using the butterfly structure of the polarization transform:

L_{2N}^{(2i-1)} = f(L_N^{(i)}, L_N^{(i)}) = 2\tanh^{-1}\!\left(\tanh\frac{L_N^{(i)}}{2} \cdot \tanh\frac{L_N^{(i)}}{2}\right)

L_{2N}^{(2i)} = g(L_N^{(i)}, L_N^{(i)}, \hat{u}_{2i-1}) = (-1)^{\hat{u}_{2i-1}} L_N^{(i)} + L_N^{(i)}

The complexity of SC decoding is

O(N \log N)

.

Theorem: Polar Codes Achieve Channel Capacity

For any binary-input discrete memoryless channel $W$ with capacity $I(W)$ , polar codes of rate $R < I(W)$ and block length $N = 2^n$ achieve vanishing block error probability under SC decoding:

$P_e(N) = O(2^{-N^\beta})$

for any $\beta < 1/2$ , as $N \to \infty$ .

Channel polarization drives the synthetic channel capacities to 0 or 1. By placing information bits only on the near-perfect channels and frozen bits on the useless channels, the code approaches capacity. The error probability decays super-exponentially in $N$ .

Proof

Polarization

The recursive channel splitting creates synthetic channels whose Bhattacharyya parameters $Z(W_N^{(i)})$ converge to either 0 (reliable) or 1 (unreliable). The fraction converging to 0 equals $I(W)$ .

Error bound

Under SC decoding, the block error probability is bounded by

$P_e \leq \sum_{i \in \mathcal{A}} Z(W_N^{(i)})$

where $\mathcal{A}$ is the information set. Since the selected channels have $Z(W_N^{(i)}) \to 0$ super-exponentially, the sum vanishes. $\blacksquare$

Example: Polar Code Construction for N = 8

Construct a rate-1/2 polar code for $N = 8$ over a binary erasure channel (BEC) with erasure probability $\epsilon = 0.5$ .

(a) Compute the Bhattacharyya parameters of all 8 synthetic channels.

(b) Select the 4 most reliable channels for information bits.

(c) Write the generator matrix.

Solution

Recursive computation

Starting from $Z(W) = \epsilon = 0.5$ , apply the polarization recursions:

For "bad" channel: $Z^- = 2Z - Z^2$

For "good" channel: $Z^+ = Z^2$

Level 1 ( $N=2$ ): $Z^- = 0.75$ , $Z^+ = 0.25$

Level 2 ( $N=4$ ): $Z_1 = 2(0.75) - 0.75^2 = 0.9375$ $Z_2 = 0.75^2 = 0.5625$ $Z_3 = 2(0.25) - 0.25^2 = 0.4375$ $Z_4 = 0.25^2 = 0.0625$

Level 3 ( $N=8$ ): continuing the recursion gives $Z_1 = 0.9961$ , $Z_2 = 0.8789$ , $Z_3 = 0.6836$ , $Z_4 = 0.3164$ , $Z_5 = 0.8086$ , $Z_6 = 0.1914$ , $Z_7 = 0.1211$ , $Z_8 = 0.0039$ .

Channel selection

Ranking by reliability (smallest $Z$ ): $i = 8$ ( $Z = 0.0039$ ), $i = 7$ ( $0.1211$ ), $i = 6$ ( $0.1914$ ), $i = 4$ ( $0.3164$ ).

Information set: $\mathcal{A} = \{4, 6, 7, 8\}$ .

Frozen set: $\mathcal{F} = \{1, 2, 3, 5\}$ (frozen to 0).

Generator matrix

The generator matrix consists of rows 4, 6, 7, 8 of $\mathbf{G}_8 = \mathbf{B}_8 \mathbf{F}^{\otimes 3}$ . The encoding is $\mathbf{x} = \mathbf{u} \mathbf{G}_8$ where $u_i = 0$ for $i \in \mathcal{F}$ and the information bits fill positions in $\mathcal{A}$ . $\blacksquare$

CRC-Aided Successive Cancellation List (CA-SCL) Decoding

Plain SC decoding has poor finite-length performance because a single bit error propagates to corrupt all subsequent decisions. Two key improvements address this:

SC List (SCL) decoding (Tal and Vardy, 2015): maintains a list of $L$ candidate paths through the decoding tree. At each information bit position, both hypotheses ( $u_i = 0$ and $u_i = 1$ ) are explored, and the list is pruned to the $L$ most likely paths. Complexity is $O(LN \log N)$ .

CRC-aided SCL (CA-SCL): Appends a CRC (e.g., 11 bits) to the information bits before polar encoding. After SCL decoding, the CRC selects the correct path from the list. This dramatically improves performance — a list size of $L = 8$ - $32$ with CRC makes polar codes competitive with LDPC and turbo codes at short-to-medium block lengths.

Quick Check

In polar code construction, which synthetic channels are used to carry information bits?

The channels with the highest Bhattacharyya parameter

The channels with the lowest Bhattacharyya parameter (most reliable)

Randomly selected channels

Alternating channels (odd-indexed)

Correction:

The channels with the lowest Bhattacharyya parameter (most reliable)

Information bits are placed on the most reliable synthetic channels (smallest $Z$ ), while frozen bits (known zeros) are placed on the unreliable channels.

Common Mistake: SC Decoding Has Poor Finite-Length Performance

Mistake:

Using plain successive cancellation decoding and expecting performance competitive with LDPC or turbo codes at practical block lengths (e.g., $N = 256$ to $8192$ ).

Correction:

SC decoding is capacity-achieving only asymptotically. At finite block lengths, it performs several dB worse than LDPC codes. CRC-aided SCL decoding (with list size $L = 8$ - $32$ ) is essential for competitive performance and is used in all practical polar code deployments, including 5G NR.

Why This Matters: Polar Codes in 5G NR Control Channels

Polar codes were adopted in 3GPP Release 15 (2018) for the 5G NR control channels:

PDCCH (Physical Downlink Control Channel): carries downlink control information (DCI) with block sizes 12-140 bits.
PUCCH (Physical Uplink Control Channel): carries uplink control information (UCI) for blocks $> 11$ bits.

The 5G NR polar code uses CRC-aided SCL decoding with distributed CRC bits and a rate-matching scheme based on puncturing, shortening, and repetition. The reliability sequence for channel selection is pre-computed and stored in the standard.

Channel Polarization

A phenomenon where recursive channel combining and splitting transforms $N$ identical channels into $N$ synthetic channels that are either nearly perfect or nearly useless, with the fraction of good channels equalling the original channel capacity.

Successive Cancellation Decoding

A sequential decoding algorithm for polar codes that estimates each bit in order, using the channel outputs and all previously decoded bits. Has $O(N \log N)$ complexity.

Polar Codes

Definition: Channel Polarization