[Jump to code hierarchy]

Polar code[1,2]

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 [3]. 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.

The affine automorphism group of polar codes is the lower-triangular affine group [4,5].

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\). Polar codes often need to be tailored for a given channel, but universal constructions also exist [6].

Rate

Supports reliable transmission at rates \(K/N\) approaching the Shannon capacity of the channel under the successive cancellation decoder [2,7]; see also Refs. [8,9].

Decoding

Successive cancellation (SC) decoder [2].Successive cancellation list (SCL) decoder [10] and a modification utilizing sequence repetition (SR-List) [11].Soft cancellation (SCAN) decoder [12,13].Belief propagation (BP) decoder [14].Noisy quantum gate-based decoder [15].

Realizations

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

Notes

For more details, see Refs. [17,18].See Kaiserslautern database [19] and the pretty-good-codes database [20] for explicit representatives and benchmarking.Codes have been benchmarked using AFF3CT toolbox [21].Polar codes are also useful for source coding [22].

Cousins

  • Reed-Muller (RM) code— The generator matrices of RM and polar codes are different submatrices of Kronecker products of Hadamard matrices; see Ref. [23]. There are families interpolating between the two codes [24].
  • Polar c-q code— Quantum-classical polar codes generalize polar codes for transmission through channels with quantum output.
  • Cyclic redundancy check (CRC) code— CRC codes concataned with polar codes yield improved performance of the SCL polar-code decoder [10,25,26].
  • Quantum polar code— Without entanglement assistance, quantum polar codes are CSS codes constructed out of polar codes.
  • Branching MERA code— Classical versions of branching MERA codes can be thought of as extensions of polar codes [27,28].

Member of code lists

Primary Hierarchy

Classical Domain
Binary Kingdom
Binary codeECC
Binary group-orbit codeECC
Linear binary codeLinear \(q\)-ary Linear code over \(\mathbb{Z}_q\) ECC
Parents
Linear binary code
Generalized concatenated code (GCC)ECC
Polar codes can be represented as generalized concatenations of their kernels.
Polar code

References

[1]
Stolte, Norbert. Rekursive Codes mit der Plotkin-Konstruktion und ihre Decodierung. Diss. Darmstadt University of Technology, Germany, 2002.
[2]
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
[3]
S. B. Korada, E. Sasoglu, and R. Urbanke, “Polar Codes: Characterization of Exponent, Bounds, and Constructions”, IEEE Transactions on Information Theory 56, 6253 (2010) DOI
[4]
M. Bardet, V. Dragoi, A. Otmani, and J.-P. Tillich, “Algebraic properties of polar codes from a new polynomial formalism”, 2016 IEEE International Symposium on Information Theory (ISIT) (2016) arXiv:1601.06215 DOI
[5]
K. Ivanov and R. Urbanke, “Polar Codes Do Not Have Many Affine Automorphisms”, (2022) arXiv:2112.12495
[6]
S. H. Hassani and R. Urbanke, “Universal polar codes”, 2014 IEEE International Symposium on Information Theory (2014) DOI
[7]
N. Hussami, S. B. Korada, and R. Urbanke, “Performance of polar codes for channel and source coding”, 2009 IEEE International Symposium on Information Theory (2009) DOI
[8]
M. Mondelli, S. H. Hassani, and R. L. Urbanke, “Unified Scaling of Polar Codes: Error Exponent, Scaling Exponent, Moderate Deviations, and Error Floors”, IEEE Transactions on Information Theory 62, 6698 (2016) DOI
[9]
S. B. Korada, A. Montanari, E. Telatar, and R. Urbanke, “An empirical scaling law for polar codes”, 2010 IEEE International Symposium on Information Theory (2010) DOI
[10]
I. Tal and A. Vardy, “List Decoding of Polar Codes”, IEEE Transactions on Information Theory 61, 2213 (2015) DOI
[11]
Y. Ren, A. T. Kristensen, Y. Shen, A. Balatsoukas-Stimming, C. Zhang, and A. Burg, “A Sequence Repetition Node-Based Successive Cancellation List Decoder for 5G Polar Codes: Algorithm and Implementation”, IEEE Transactions on Signal Processing 70, 5592 (2022) arXiv:2205.08857 DOI
[12]
U. U. Fayyaz and J. R. Barry, “Low-Complexity Soft-Output Decoding of Polar Codes”, IEEE Journal on Selected Areas in Communications 32, 958 (2014) DOI
[13]
U. U. Fayyaz and J. R. Barry, “Polar codes for partial response channels”, 2013 IEEE International Conference on Communications (ICC) 4337 (2013) DOI
[14]
E. Arkan, “A performance comparison of polar codes and Reed-Muller codes”, IEEE Communications Letters 12, 447 (2008) DOI
[15]
S. Kasi, J. Kaewell, S. Hamidi-Rad, and K. Jamieson, “Decoding Polar Codes via Noisy Quantum Gates: Quantum Circuits and Insights”, (2022) arXiv:2210.10854
[16]
3rd Generation Partnership Project (3GPP), Technical specification group radio access network, 3GPP TS 38.212 V.15.0.0, 2017.
[17]
N. Presman, Simon Litsyn, "Polar codes." Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021) DOI
[18]
I. F. Blake, Essays on Coding Theory (Cambridge University Press, 2024) DOI
[19]
Michael Helmling, Stefan Scholl, Florian Gensheimer, Tobias Dietz, Kira Kraft, Stefan Ruzika, and Norbert Wehn. Database of Channel Codes and ML Simulation Results. URL, 2022.
[20]
G. Liva, F. Steiner. “pretty-good-codes.org: Online library of good channel codes”, URL: http://pretty-good-codes.org/
[21]
A. Cassagne et al., “AFF3CT: A Fast Forward Error Correction Toolbox!”, SoftwareX 10, 100345 (2019) DOI
[22]
S. B. Korada and R. L. Urbanke, “Polar Codes are Optimal for Lossy Source Coding”, IEEE Transactions on Information Theory 56, 1751 (2010) DOI
[23]
E. Arikan, “A survey of reed-muller codes from polar coding perspective”, IEEE Information Theory Workshop 2010 (ITW 2010) (2010) DOI
[24]
M. Mondelli, S. H. Hassani, and R. L. Urbanke, “From Polar to Reed-Muller Codes: A Technique to Improve the Finite-Length Performance”, IEEE Transactions on Communications 62, 3084 (2014) DOI
[25]
B. Li, H. Shen, and D. Tse, “An Adaptive Successive Cancellation List Decoder for Polar Codes with Cyclic Redundancy Check”, IEEE Communications Letters 16, 2044 (2012) DOI
[26]
L. Xiang, Z. B. Kaykac Egilmez, R. G. Maunder, and L. Hanzo, “CRC-Aided Logarithmic Stack Decoding of Polar Codes for Ultra Reliable Low Latency Communication in 3GPP New Radio”, IEEE Access 7, 28559 (2019) DOI
[27]
A. J. Ferris and D. Poulin, “Branching MERA codes: a natural extension of polar codes”, (2013) arXiv:1312.4575
[28]
A. J. Ferris and D. Poulin, “Branching MERA codes: A natural extension of classical and quantum polar codes”, 2014 IEEE International Symposium on Information Theory (2014) DOI
Page edit log

Your contribution is welcome!

on github.com (edit & pull request)— see instructions

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} }
Share via:
Twitter | Mastodon |  | E-mail
Permanent link:
https://errorcorrectionzoo.org/c/polar

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/edit/main/codes/classical/bits/polar.yml.