Field Guide · algorithm

Also known as: polar code, Arikan code

A polar code is a linear block code that, as the block length grows, provably achieves channel capacity using a strikingly simple construction: combine many copies of a channel so they polarize into some that become almost perfectly reliable and some that become almost useless, then send data only on the reliable ones.1 Introduced by Erdal Arıkan in 2009, polar codes were the first codes with a rigorous proof of capacity-achievement and a low-complexity decoder, and they were adopted for the control channels of 5G NR.2

identical channels polarized bit-channels reliable → data reliable → data weak → frozen (0) weak → frozen (0)
Recursive combining polarizes identical channels: data rides the bit-channels that became reliable, while the weak ones are frozen to known values.

How it works

Take two copies of a channel and combine their inputs with a single XOR before transmission. Decoded jointly, one of the two resulting bit-channels comes out better than the original and the other worse. Apply this butterfly recursively across N = 2ⁿ copies and the effect compounds: the bit-channels split into two extremes — a fraction essentially noiseless and the rest essentially useless — with almost nothing in between. That is channel polarization.

The code then writes itself:

  • Rank the N synthetic bit-channels by reliability (computed for the target channel and SNR).
  • Put the K information bits on the K most reliable bit-channels.
  • Freeze the remaining N−K bit-channels to fixed, known values (usually 0). Encoder and decoder agree on which indices are frozen.

Decoding is successive cancellation (SC): process bit-channels in order, and for each one either read off the frozen value (known in advance) or make a soft decision using the channel observations and all previously decided bits. Because each decision leans on the earlier ones, SC is sequential, with complexity O(N log N).

Variants

Plain SC only approaches capacity at very long block lengths and makes irreversible early mistakes. Two refinements fixed that for practical short blocks:

  • SC List (SCL) keeps the L most likely partial-decode paths instead of committing to one, choosing the best survivor at the end — much stronger at a modest cost.
  • CRC-aided SCL appends a CRC to the data; the decoder picks the list path whose CRC checks out, which sharply lowers the error rate and is the form standardized in 5G.

Polar codes are also closely related to Reed–Muller codes, which use the same recursive transform but choose the information positions differently.

Relevance to SDR

Polar codes protect the 5G NR control channels (PBCH broadcast, and the PDCCH/PUCCH downlink/uplink control), where messages are short and reliability is paramount; the data channels use LDPC instead, and earlier 3G/4G used turbo codes. They are a landmark in forward error correction as the first provably capacity-achieving construction. The land-mobile and aviation formats GopherTrunk decodes do not use polar coding, so GT does not implement a polar decoder; it is documented here as a cornerstone of modern cellular coding theory.

Sources

  1. Polar code (coding theory) — Wikipedia, for channel polarization, frozen bits, and successive-cancellation decoding. ↩

  2. Channel polarization: a method for constructing capacity-achieving codes — E. Arıkan, IEEE Trans. Information Theory (2009), the founding paper. ↩

See also