View source for Polar code (coding theory)

{{Short description|Type of error correcting code}}
In [[information theory]], '''polar codes''' are a [[linear block code|linear block]] [[error-correcting codes]]. The code construction is based on a multiple recursive concatenation of a short kernel code which transforms the physical channel into virtual outer channels. When the number of recursions becomes large, the virtual channels tend to either have high reliability or low reliability (in other words, they polarize or become sparse), and the data bits are allocated to the most reliable channels. It is the first code with an explicit construction to provably achieve the [[Noisy-channel coding theorem|channel capacity]] for symmetric binary-input, discrete, [[memorylessness|memoryless]] channels (B-DMC) with polynomial dependence on the gap to capacity.<ref name=":0">{{Cite journal |last=Arikan |first=Erdal |date=2009 |title=Channel Polarization: A Method for Constructing Capacity-Achieving Codes for Symmetric Binary-Input Memoryless Channels |url=https://ieeexplore.ieee.org/document/5075875 |journal=IEEE Transactions on Information Theory |volume=55 |issue=7 |pages=3051–3073 |doi=10.1109/TIT.2009.2021379 |arxiv=0807.3917 |issn=0018-9448}}</ref> Polar codes were developed by [[Erdal Arıkan|Erdal Arikan]], a professor of electrical engineering at [[Bilkent University]].

Notably, polar codes have modest encoding and decoding complexity {{math|''O''(''n'' log ''n'')}}, which renders them attractive for many applications. Moreover, the encoding and decoding energy complexity of generalized polar codes can reach the fundamental lower bounds for energy consumption of two dimensional circuitry to within an {{math|''O''(''n''{{sup|ε}} polylog ''n'')}} factor for any {{math|ε > 0}}.<ref>{{Cite web|url=https://tspace.library.utoronto.ca/bitstream/1807/78035/3/Blake_Christopher_G_201706_PhD_thesis.pdf|title=Energy Consumption of Error Control Coding Circuits|last=Blake|first=Christopher G.|date=2017|website=[[University of Toronto]]|access-date=2019-10-18}}</ref>

== Industrial applications ==
Polar codes have some limitations when used in industrial applications. Primarily, the original design of the polar codes achieves capacity when block sizes are asymptotically large with a successive cancellation decoder. However, with the block sizes used in industry, the performance of the successive cancellation is poor compared to well-defined and implemented coding schemes such as [[low-density parity-check code]] (LDPC) and [[turbo code]]. Polar performance can be improved with successive cancellation list decoding, but its usability in real applications is still questionable due to very poor implementation efficiencies caused by the iterative approach.<ref name=":1">{{cite arXiv | eprint=1504.03916 | last1=Arikan | first1=Erdal | author2=Najeeb ul Hassan | last3=Lentmaier | first3=Michael | last4=Montorsi | first4=Guido | last5=Sayir | first5=Jossy | title=Challenges and some new directions in channel coding | date=2015 | class=cs.IT }}</ref>

In October 2016, [[Huawei]] announced that it had achieved 27&nbsp;Gbit/s in [[5G]] field trial tests using polar codes for channel coding. The improvements have been introduced so that the channel performance has now almost closed the gap to the [[Shannon limit]], which sets the bar for the maximum rate for a given bandwidth and a given noise level.<ref name=":2">{{Cite news|url=http://www.telecomasia.net/content/huawei-achieves-27gbps-5g-speeds-polar-code?section=TOP+STORIES&mkt_tok=eyJpIjoiTUdRMk5XWTBZVGhsWkdFNSIsInQiOiJcL2ppUWkzSWhzQURsWDR6QVNLRkhlTTBqM1U5NnNPVGtJcDRxSU9hZDFXTm5LdlNqRlwvS0pqVlZMeXYzSFRtOU1BaHIza2NWd3NnSXBqdkptQytDWXFqNWJudCtadnJkUXdZQXNSTGNUSGpvPSJ9|title=Huawei achieves 27Gbps 5G speeds with Polar Code|access-date=2016-10-10}}</ref>

In November 2016, [[3GPP]] agreed to adopt polar codes for the eMBB (Enhanced Mobile Broadband) control channels for the 5G NR (New Radio) interface. At the same meeting, 3GPP agreed to use LDPC for the corresponding data channel.<ref name=":3">{{cite web|title=3GPP RAN1 meeting #87 final report|url=http://www.3gpp.org/ftp/tsg_ran/WG1_RL1/TSGR1_87/Report/Final_Minutes_report_RAN1%2387_v100.zip|publisher=3GPP|accessdate=31 August 2017}}{{dead link|date=July 2020|bot=medic}}{{cbignore|bot=medic}}</ref><ref>M. Rowshan, M. Qiu, Y. Xie, X. Gu and J. Yuan, "Channel Coding Toward 6G: Technical Overview and Outlook," in ''IEEE Open Journal of the Communications Society'', vol. 5, pp. 2585-2685, 2024, doi: [https://ieeexplore.ieee.org/abstract/document/10502324 10.1109/OJCOMS.2024.3390000]. </ref>
==PAC codes==
In 2019, [[Erdal Arıkan|Arıkan]] suggested to employ a convolutional pre-transformation before polar coding. These pre-transformed variant of polar codes were dubbed polarization-adjusted convolutional (PAC) codes.<ref>E. Arıkan, "From sequential decoding to channel polarization and back again", 2019, '''arXiv:[[arxiv:1908.09594|1908.09594]]'''</ref> It was shown that the pre-transformation can effectively improve the distance properties of polar codes by reducing the number of minimum-weight and in general small-weight codewords,<ref>M. Rowshan and J. Yuan, "On the Minimum Weight Codewords of PAC Codes: The Impact of Pre-Transformation," in ''IEEE Journal on Selected Areas in Information Theory'', vol. 4, pp. 487-498, 2023, doi: [https://ieeexplore.ieee.org/abstract/document/10246271 10.1109/JSAIT.2023.3312678].</ref> resulting in the improvement of block error rates under near maximum likelihood (ML) decoding algorithm such as Fano decoding and list decoding.<ref>M. Rowshan, A. Burg and E. Viterbo, "Polarization-Adjusted Convolutional (PAC) Codes: Sequential Decoding vs List Decoding," in ''IEEE Transactions on Vehicular Technology'', vol. 70, no. 2, pp. 1434-1447, Feb. 2021, doi: [https://ieeexplore.ieee.org/abstract/document/9328621 10.1109/TVT.2021.3052550].</ref> Fano decoding is a tree search algorithm that determines the transmitted codeword by utilizing an optimal metric function to efficiently guide the search process.<ref>M. Moradi, "On Sequential Decoding Metric Function of Polarization-Adjusted Convolutional (PAC) Codes," IEEE Transactions on Communications, vol. 69, no. 12, pp. 7913-7922, 2021, doi: 10.1109/TCOMM.2021.3111018.</ref> PAC codes are also equivalent to post-transforming polar codes with certain cyclic codes.<ref>M. Moradi, "Polarization-adjusted convolutional (PAC) codes as a concatenation of inner cyclic and outer polar- and Reed-Muller-like codes," Finite Fields and Their Applications, vol. 93, p. 102321, 2024, doi: https://doi.org/10.1016/j.ffa.2023.102321.</ref> At [[Finite Blocklength Information Theory|short blocklengths]], such codes outperform both [[convolutional code]]s and CRC-aided list decoding of conventional polar codes.<ref name=":4">{{cite arXiv | eprint=2012.04990 | last1=Moradi | first1=Mohsen | last2=Mozammel | first2=Amir | last3=Qin | first3=Kangjian | last4=Arikan | first4=Erdal | title=Performance and Complexity of Sequential Decoding of PAC Codes | date=2020 | class=cs.IT }}</ref><ref>{{Cite journal |arxiv=2005.13711|doi=10.3390/e23070841|doi-access=free|title=List Decoding of Arıkan's PAC Codes|year=2021|last1=Yao|first1=Hanwen|last2=Fazeli|first2=Arman|last3=Vardy|first3=Alexander|author-link3=Alexander Vardy|journal=Entropy|volume=23|issue=7|page=841|pmid=34209050|pmc=8303677|bibcode=2021Entrp..23..841Y }}</ref>

== Neural Polar Decoders ==
Neural Polar Decoders (NPDs)<ref>{{cite arXiv |last1=Aharoni |first1=Ziv |title=Data-Driven Neural Polar Codes for Unknown Channels With and Without Memory |date=2023-09-06 |eprint=2309.03148 |last2=Huleihel |first2=Bashar |last3=Pfister |first3=Henry D. |last4=Permuter |first4=Haim H.|class=cs.IT }}</ref> are an advancement in channel coding that combine neural networks (NNs) with polar codes, providing unified decoding for channels with or without memory, without requiring an explicit channel model. They use four neural networks to approximate the functions of polar decoding: the embedding (E) NN, the check-node (F) NN, the bit-node (G) NN, and the embedding-to-LLR (H) NN. The weights of these NNs are determined by estimating the mutual information of the synthetic channels. By the end of training, the weights of the NPD are fixed and can then be used for decoding.

The computational complexity of NPDs is determined by the parameterization of the neural networks, unlike successive cancellation (SC) trellis decoders,<ref>{{Cite book |last1=Wang |first1=Runxin |last2=Honda |first2=Junya |last3=Yamamoto |first3=Hirosuke |last4=Liu |first4=Rongke |last5=Hou |first5=Yi |chapter=Construction of polar codes for channels with memory |date=2015 |title=2015 IEEE Information Theory Workshop - Fall (ITW) |chapter-url=https://ieeexplore.ieee.org/document/7360760 |publisher=IEEE |pages=187–191 |doi=10.1109/ITWF.2015.7360760 |isbn=978-1-4673-7852-9}}</ref> whose complexity is determined by the channel model and are typically used for finite-state channels (FSCs). The computational complexity of NPDs is <math display="inline">O(kdN \log_2 N)</math>, where <math>k</math> is the number of hidden units in the neural networks, <math>d</math> is the dimension of the embedding, and <math>N</math> is the block length. In contrast, the computational complexity of SC trellis decoders is <math>O(|\mathcal{S}|^3N\log_2 N)</math>, where <math>\mathcal{S}</math> is the state space of the channel model.

NPDs can be integrated into SC decoding<ref name=":0" /> schemes such as SC list decoding and CRC-aided SC decoding.<ref>{{Cite journal |last1=Tal |first1=Ido |last2=Vardy |first2=Alexander |date=2015 |title=List Decoding of Polar Codes |url=https://ieeexplore.ieee.org/document/7055304 |journal=IEEE Transactions on Information Theory |volume=61 |issue=5 |pages=2213–2226 |doi=10.1109/TIT.2015.2410251 |issn=0018-9448|arxiv=1206.0050 }}</ref> They are also compatible with non-uniform and i.i.d. input distributions by integrating them into the Honda-Yamamoto scheme.<ref>{{Cite journal |last1=Honda |first1=Junya |last2=Yamamoto |first2=Hirosuke |date=2013 |title=Polar Coding Without Alphabet Extension for Asymmetric Models |url=https://ieeexplore.ieee.org/document/6601656 |journal=IEEE Transactions on Information Theory |volume=59 |issue=12 |pages=7829–7838 |doi=10.1109/TIT.2013.2282305 |issn=0018-9448}}</ref> This flexibility allows NPDs to be used in various decoding scenarios, improving error correction performance while maintaining manageable computational complexity.

== References ==
<references />

==External links==
* [https://aff3ct.github.io AFF3CT home page: A Fast Forward Error Correction Toolbox for high speed polar code simulations in software]

[[Category:Error detection and correction]]
[[Category:Coding theory]]
[[Category:Capacity-achieving codes]]
[[Category:Capacity-approaching codes]]