Skip to content
Back to search results

Polar Codes with Successive Cancellation Decoding

Introduced by
Erdal Arikan
Year
2009
Type
recursive error-correcting code
Family
Coding theory
Font size

What does it do?

Polar codes, introduced by Erdal Arikan in 2009, are the first constructive family of codes proven to achieve the Shannon capacity of symmetric binary-input memoryless channels.

They use recursive construction and successive cancellation decoding, a simple greedy algorithm with theoretical guarantees. Polar codes were adopted in 5G NR for control channel coding and are studied for future 6G systems. Unlike turbo and LDPC codes (which are empirical), polar codes provide rigorous theoretical foundations.

The intuition behind the method

Polar codes are based on the concept of channel polarization: applying a specific recursive transformation to a set of independent identical channels creates a new set where some channels become effectively noiseless (capacity 1) and others effectively useless (capacity 0). Information bits are placed on the noiseless channels; frozen bits (known to receiver) fill the useless channels. Decoding uses successive cancellation: decode bit-by-bit in order, using previously decoded bits to refine estimates of remaining bits. The recursive structure ensures that decoding complexity is linear in code length, and the polarization property guarantees asymptotic capacity-achieving performance.

History

Arikan's 2009 paper on channel polarization was transformative: for the first time, a constructive code family was proven capacity-achieving with polynomial complexity. Subsequent research developed practical decoders (belief propagation, list decoding) to address the error floor at moderate SNR. Polar codes were adopted in 3GPP 5G NR Release 15 for control channels (e.g., PBCH, DCI), replacing turbo codes. For data channels, LDPC was chosen due to better empirical performance at moderate blocklengths. Arikan won the IEEE Information Theory Society paper award, and polar codes remain active research.

When to use it

Polar codes are ideal for short-to-moderate packet lengths (100-1000 bits) and strict latency requirements (no iterative decoding). Use polar codes for control channels in 5G/6G or any scenario prioritizing provable capacity-achieving guarantees. Avoid polar codes for very long codewords (>10k bits) where LDPC's flexibility is preferred. Polar codes excel in block-fading channels; in flat fading, no particular advantage over LDPC.

Limitations and considerations

  • Successive cancellation has exponential error propagation at low SNR (error floor)
  • Frozen bit design requires knowing channel SNR in advance; adaptation is needed
  • Performance at short blocklengths is inferior to LDPC/turbo without clever modifications
  • Belief propagation or list decoding (to mitigate error floor) adds complexity, approaching LDPC
  • Less mature implementation ecosystem compared to turbo and LDPC codes

Source conditions do not replace independent scientific review or validation by an analysis engine.

Strengths

  • First code family with constructive proof of Shannon capacity achievement
  • Simple successive cancellation decoding; linear time complexity O(N log N)
  • Recursive structure enables hardware-efficient implementation
  • No iterative processing; deterministic latency (important for real-time systems)
  • Theoretical framework for analyzing performance and optimizing code construction
  • Inherent adaptation via frozen bit selection for different SNR and blocklengths

Applications

  • 5G NR control channels (PBCH, DCI): short-packet reliable transmission with strict latency constraints
  • Satellite communications: structured coding with deterministic decoding latency for mission-critical links
  • Quantum key distribution: theoretical security combined with practical error correction
  • Aerospace telemetry: spacecraft communication with ultra-high reliability and bounded decoding delay
  • Optical communications: short reach but high-speed links where fast deterministic decoding is essential

How it works

How it works

1

Information bits (plus frozen bits) form the codeword via a generator matrix constructed recursively (Kronecker product structure).

2

The generator matrix G is built by repeated Kronecker products of [[1,0],[1,1]]; this creates the recursive polarization structure.

3

Encoded bits are transmitted; received bits are soft values (log-likelihood ratios from the channel).

4

Successive cancellation decoder processes bits sequentially: for bit i, it computes the conditional log-likelihood ratio given all previous decoded bits and the channel observation.

5

Each bit is decoded by slicing its LLR (positive -> 1, negative -> 0). If bit i is frozen, the known value is used. Decoded bits feed forward to refine LLR estimates for remaining bits.

Common pitfalls

  • Using basic successive cancellation at low SNR; belief propagation or list decoding is necessary for reasonable BER
  • Designing frozen bit set for wrong channel condition; performance degrades if actual SNR differs from design SNR
  • Assuming linear decoding complexity means fast decoding; each bit still requires LLR computation, summing to O(N log N) total
  • Neglecting quantization effects; fixed-point LLR quantization (especially branching decisions) impacts error floor
  • Not exploiting adaptivity; frozen bit re-selection based on CSI feedback can significantly improve performance

Frequently asked questions

What is channel polarization and how does it enable capacity-achieving codes?

Channel polarization transforms N identical channels into N channels with polarized capacities: some approach 1 (noiseless), others approach 0 (useless). Information bits on high-capacity channels are protected; low-capacity channels are frozen. As N grows, the fraction of high-capacity channels approaches the Shannon capacity. This structure allows simple successive cancellation decoding to achieve capacity.

Why does successive cancellation have an error floor at low SNR?

Successive cancellation greedily decodes one bit at a time using previous bit estimates. If an early bit is decoded incorrectly, the error propagates to all downstream bits, causing a cascade of errors. This error floor arises from the dependence on past decisions. Belief propagation or list decoding mitigates this by exploring alternatives and deferring hard decisions.

How are frozen bits chosen?

Frozen bits are placed on channels with low estimated mutual information (low capacity). One method is to simulate the polarization process for the target SNR and blocklength, ranking channels by their capacity, then freezing the K lowest-capacity channels. This requires knowing SNR in advance. Adaptive polar codes can update the frozen bit set based on feedback or CSI estimation.

What is list decoding for polar codes?

Instead of making a single hard decision at each step, list decoding maintains a list of candidate partial codewords and explores multiple paths. After processing all bits, the best path (by likelihood) is selected. This reduces error floor significantly but increases complexity to O(L N log N) where L is list size. List size 8-32 is typical; a good balance between performance and complexity.

Related methods

Sources

  1. Arikan, E. (2009). Channel polarization: A method for constructing capacity-achieving codes for symmetric binary-input memoryless channels. IEEE Transactions on Information Theory, 55(7), 3051-3073.

    Open DOI reference
    Copied.
  2. Sasoglu, E., Telatar, I., & Yildirim, E. (2011). Polarization for arbitrary discrete memoryless channels. In Proceedings of the IEEE Information Theory Workshop (ITW), 144-148.

    Open publication reference
    Copied.