Polar code[1]

Description

In its basic version, a binary linear polar code encodes \(K\) message bits into \(N=2^n\) bits. The linear transformation that defines the code is given by the matrix \(G^{(n)}=B_N G^{\otimes n}\), where \(B_N\) is a certain \(N\times N\) permutation matrix, and \(G^{\otimes n}\) is the \(n\)th Kronecker power of the \(2\times 2\) kernel matrix \(G=\left[\begin{smallmatrix}1 & 0\\ 1 & 1 \end{smallmatrix}\right]\). To encode \(K\) message bits, one forms an \(N\)-vector \(u\) in which \(K\) coordinates represent the message bits. The remaining \(N-K\) coordinates are set to some fixed values and are said to be frozen. The codeword \(x \in \{0,1\}^N\) is obtained as \(x=u G^{\otimes n}\).

The choice of the frozen coordinates depends on the communication channel, and they correspond to the least reliable bits on the output of the channel under a particular decoding procedure called successive cancellation decoding. If the communication channel is input-symmetric, the values of the frozen bits can be set to zero.

There are multiple variants of the above basic construction, in particular relying on other kernel matrices. The codes can be defined for nonbinary alphabets, and they can be adjusted to support tasks such as lossless and lossy compression, successive refinement, communication over the mulitple access channel, communication over the wiretap channel, and many others.

Protection

Protects against various types of noise in the communication channel, for instance, errors, erasures, or other types of noise. Distance plays no role in the analysis of its properties, and is much lower than the largest possible value given \(K,N\).

Rate

Supports reliable transmission at rates \(K/N\) approaching the Shannon capacity of the channel.

Decoding

Successive cancellation decoder [1].Successive cancellation list (SCL) decoder [2] and a modification utilizing sequence repetition (SR-List) [3].

Threshold

Achieves Shannon capacity of the binary-input memoryless channel under successive cancellation decoder [1].

Realizations

Code control channels for the 5G NR (New Radio) interfaces [4].

Notes

For more details, see Ch. 32 of Ref. [5].

Parents

Cousins

Zoo code information

Internal code ID: polar

Your contribution is welcome!

on github.com (edit & pull request)

edit on this site

Zoo Code ID: polar

Cite as:
“Polar code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2022. https://errorcorrectionzoo.org/c/polar
BibTeX:
@incollection{eczoo_polar, title={Polar code}, booktitle={The Error Correction Zoo}, year={2022}, editor={Albert, Victor V. and Faist, Philippe}, url={https://errorcorrectionzoo.org/c/polar} }
Permanent link:
https://errorcorrectionzoo.org/c/polar

References

[1]
E. Arikan, “Channel Polarization: A Method for Constructing Capacity-Achieving Codes for Symmetric Binary-Input Memoryless Channels”, IEEE Transactions on Information Theory 55, 3051 (2009). DOI
[2]
I. Tal and A. Vardy, “List Decoding of Polar Codes”, IEEE Transactions on Information Theory 61, 2213 (2015). DOI
[3]
Yuqing Ren et al., “A Sequence Repetition Node-Based Successive Cancellation List Decoder for 5G Polar Codes: Algorithm and Implementation”. 2205.08857
[4]
3rd Generation Partnership Project (3GPP), Technical specification group radio access network, 3GPP TS 38.212 V.15.0.0, 2017.
[5]
W. C. Huffman, J.-L. Kim, and P. Solé, Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021). DOI

Cite as:

“Polar code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2022. https://errorcorrectionzoo.org/c/polar

Github: https://github.com/errorcorrectionzoo/eczoo_data/tree/main/codes/classical/bits/polar.yml.