Polar code (coding theory)

Last updated

In information theory, polar codes are a 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 channel capacity for symmetric binary-input, discrete, memoryless channels (B-DMC) with polynomial dependence on the gap to capacity. [1] Polar codes were developed by Erdal Arikan, a professor of electrical engineering at Bilkent University.

Contents

Notably, polar codes have modest encoding and decoding complexity 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 O(nε polylog n) factor for any ε > 0. [2]

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

In October 2016, Huawei announced that it had achieved 27 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. [4]

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. [5] [6]

PAC codes

In 2019, 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. [7] 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, [8] resulting in the improvement of block error rates under near maximum likelihood (ML) decoding algorithm such as Fano decoding and list decoding. [9] Fano decoding is a tree search algorithm that determines the transmitted codeword by utilizing an optimal metric function to efficiently guide the search process. [10] PAC codes are also equivalent to post-transforming polar codes with certain cyclic codes. [11] At short blocklengths, such codes outperform both convolutional codes and CRC-aided list decoding of conventional polar codes. [12] [13]

Neural Polar Decoders

Neural Polar Decoders (NPDs) [14] 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, [15] whose complexity is determined by the channel model and are typically used for finite-state channels (FSCs). The computational complexity of NPDs is , where is the number of hidden units in the neural networks, is the dimension of the embedding, and is the block length. In contrast, the computational complexity of SC trellis decoders is , where is the state space of the channel model.

NPDs can be integrated into SC decoding [1] schemes such as SC list decoding and CRC-aided SC decoding. [16] They are also compatible with non-uniform and i.i.d. input distributions by integrating them into the Honda-Yamamoto scheme. [17] This flexibility allows NPDs to be used in various decoding scenarios, improving error correction performance while maintaining manageable computational complexity.

Related Research Articles

In telecommunication, a convolutional code is a type of error-correcting code that generates parity symbols via the sliding application of a boolean polynomial function to a data stream. The sliding application represents the 'convolution' of the encoder over the data, which gives rise to the term 'convolutional coding'. The sliding nature of the convolutional codes facilitates trellis decoding using a time-invariant trellis. Time invariant trellis decoding allows convolutional codes to be maximum-likelihood soft-decision decoded with reasonable complexity.

<span class="mw-page-title-main">Coding theory</span> Study of the properties of codes and their fitness

Coding theory is the study of the properties of codes and their respective fitness for specific applications. Codes are used for data compression, cryptography, error detection and correction, data transmission and data storage. Codes are studied by various scientific disciplines—such as information theory, electrical engineering, mathematics, linguistics, and computer science—for the purpose of designing efficient and reliable data transmission methods. This typically involves the removal of redundancy and the correction or detection of errors in the transmitted data.

In information theory, turbo codes are a class of high-performance forward error correction (FEC) codes developed around 1990–91, but first published in 1993. They were the first practical codes to closely approach the maximum channel capacity or Shannon limit, a theoretical maximum for the code rate at which reliable communication is still possible given a specific noise level. Turbo codes are used in 3G/4G mobile communications and in satellite communications as well as other applications where designers seek to achieve reliable information transfer over bandwidth- or latency-constrained communication links in the presence of data-corrupting noise. Turbo codes compete with low-density parity-check (LDPC) codes, which provide similar performance. Until the patent for turbo codes expired, the patent-free status of LDPC codes was an important factor in LDPC's continued relevance.

In information theory, a low-density parity-check (LDPC) code is a linear error correcting code, a method of transmitting a message over a noisy transmission channel. An LDPC code is constructed using a sparse Tanner graph. LDPC codes are capacity-approaching codes, which means that practical constructions exist that allow the noise threshold to be set very close to the theoretical maximum for a symmetric memoryless channel. The noise threshold defines an upper bound for the channel noise, up to which the probability of lost information can be made as small as desired. Using iterative belief propagation techniques, LDPC codes can be decoded in time linear in their block length.

In coding theory, decoding is the process of translating received messages into codewords of a given code. There have been many common methods of mapping messages to codewords. These are often used to recover messages sent over a noisy channel, such as a binary symmetric channel.

A timeline of events related to  information theory,  quantum information theory and statistical physics,  data compression,  error correcting codes and related subjects.

In computing, telecommunication, information theory, and coding theory, forward error correction (FEC) or channel coding is a technique used for controlling errors in data transmission over unreliable or noisy communication channels.

An autoencoder is a type of artificial neural network used to learn efficient codings of unlabeled data. An autoencoder learns two functions: an encoding function that transforms the input data, and a decoding function that recreates the input data from the encoded representation. The autoencoder learns an efficient representation (encoding) for a set of data, typically for dimensionality reduction, to generate lower-dimensional embeddings for subsequent use by other machine learning algorithms.

In coding theory, concatenated codes form a class of error-correcting codes that are derived by combining an inner code and an outer code. They were conceived in 1966 by Dave Forney as a solution to the problem of finding a code that has both exponentially decreasing error probability with increasing block length and polynomial-time decoding complexity. Concatenated codes became widely used in space communications in the 1970s.

In coding theory, list decoding is an alternative to unique decoding of error-correcting codes for large error rates. The notion was proposed by Elias in the 1950s. The main idea behind list decoding is that the decoding algorithm instead of outputting a single possible message outputs a list of possibilities one of which is correct. This allows for handling a greater number of errors than that allowed by unique decoding.

<span class="mw-page-title-main">MIMO</span> Use of multiple antennas in radio

In radio, multiple-input and multiple-output (MIMO) is a method for multiplying the capacity of a radio link using multiple transmission and receiving antennas to exploit multipath propagation. MIMO has become an essential element of wireless communication standards including IEEE 802.11n, IEEE 802.11ac, HSPA+ (3G), WiMAX, and Long Term Evolution (LTE). More recently, MIMO has been applied to power-line communication for three-wire installations as part of the ITU G.hn standard and of the HomePlug AV2 specification.

Algebraic signal processing (ASP) is an emerging area of theoretical signal processing (SP). In the algebraic theory of signal processing, a set of filters is treated as an (abstract) algebra, a set of signals is treated as a module or vector space, and convolution is treated as an algebra representation. The advantage of algebraic signal processing is its generality and portability.

Quantum block codes are useful in quantum computing and in quantum communications. The encoding circuit for a large block code typically has a high complexity although those for modern codes do have lower complexity.

In digital communications, a turbo equalizer is a type of receiver used to receive a message corrupted by a communication channel with intersymbol interference (ISI). It approaches the performance of a maximum a posteriori (MAP) receiver via iterative message passing between a soft-in soft-out (SISO) equalizer and a SISO decoder. It is related to turbo codes in that a turbo equalizer may be considered a type of iterative decoder if the channel is viewed as a non-redundant convolutional code. The turbo equalizer is different from classic a turbo-like code, however, in that the 'channel code' adds no redundancy and therefore can only be used to remove non-gaussian noise.

A convolutional neural network (CNN) is a regularized type of feed-forward neural network that learns features by itself via filter optimization. This type of deep learning network has been applied to process and make predictions from many different types of data including text, images and audio. Convolution-based networks are the de-facto standard in deep learning-based approaches to computer vision and image processing, and have only recently have been replaced -- in some cases -- by newer deep learning architectures such as the transformer. Vanishing gradients and exploding gradients, seen during backpropagation in earlier neural networks, are prevented by using regularized weights over fewer connections. For example, for each neuron in the fully-connected layer, 10,000 weights would be required for processing an image sized 100 × 100 pixels. However, applying cascaded convolution kernels, only 25 neurons are required to process 5x5-sized tiles. Higher-layer features are extracted from wider context windows, compared to lower-layer features.

Erdal Arıkan is a Turkish professor in Electrical and Electronics Engineering Department at Bilkent University, Ankara, Turkey. He is known for his invention of polar codes, which is a key component of 5G technologies.

Sudoku codes are non-linear forward error correcting codes following rules of sudoku puzzles designed for an erasure channel. Based on this model, the transmitter sends a sequence of all symbols of a solved sudoku. The receiver either receives a symbol correctly or an erasure symbol to indicate that the symbol was not received. The decoder gets a matrix with missing entries and uses the constraints of sudoku puzzles to reconstruct a limited amount of erased symbols.

<span class="mw-page-title-main">Attention (machine learning)</span> Machine learning technique

Attention is a machine learning method that determines the relative importance of each component in a sequence relative to the other components in that sequence. In natural language processing, importance is represented by "soft" weights assigned to each word in a sentence. More generally, attention encodes vectors called token embeddings across a fixed-width sequence that can range from tens to millions of tokens in size.

A graph neural network (GNN) belongs to a class of artificial neural networks for processing data that can be represented as graphs.

<span class="mw-page-title-main">Vision transformer</span> Variant of Transformer designed for vision processing

A vision transformer (ViT) is a transformer designed for computer vision. A ViT breaks down an input image into a series of patches, serialises each patch into a vector, and maps it to a smaller dimension with a single matrix multiplication. These vector embeddings are then processed by a transformer encoder as if they were token embeddings.

References

  1. 1 2 Arikan, Erdal (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. arXiv: 0807.3917 . doi:10.1109/TIT.2009.2021379. ISSN   0018-9448.
  2. ↑ Blake, Christopher G. (2017). "Energy Consumption of Error Control Coding Circuits" (PDF). University of Toronto . Retrieved 2019-10-18.
  3. ↑ Arikan, Erdal; Najeeb ul Hassan; Lentmaier, Michael; Montorsi, Guido; Sayir, Jossy (2015). "Challenges and some new directions in channel coding". arXiv: 1504.03916 [cs.IT].
  4. ↑ "Huawei achieves 27Gbps 5G speeds with Polar Code" . Retrieved 2016-10-10.
  5. ↑ "3GPP RAN1 meeting #87 final report". 3GPP. Retrieved 31 August 2017.[ dead link ]
  6. ↑ 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: 10.1109/OJCOMS.2024.3390000.
  7. ↑ E. Arıkan, "From sequential decoding to channel polarization and back again", 2019, arXiv:1908.09594
  8. ↑ 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: 10.1109/JSAIT.2023.3312678.
  9. ↑ 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: 10.1109/TVT.2021.3052550.
  10. ↑ 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.
  11. ↑ 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.
  12. ↑ Moradi, Mohsen; Mozammel, Amir; Qin, Kangjian; Arikan, Erdal (2020). "Performance and Complexity of Sequential Decoding of PAC Codes". arXiv: 2012.04990 [cs.IT].
  13. ↑ Yao, Hanwen; Fazeli, Arman; Vardy, Alexander (2021). "List Decoding of Arıkan's PAC Codes". Entropy. 23 (7): 841. arXiv: 2005.13711 . Bibcode:2021Entrp..23..841Y. doi: 10.3390/e23070841 . PMC   8303677 . PMID   34209050.
  14. ↑ Aharoni, Ziv; Huleihel, Bashar; Pfister, Henry D.; Permuter, Haim H. (2023-09-06). "Data-Driven Neural Polar Codes for Unknown Channels With and Without Memory". arXiv: 2309.03148 [cs.IT].
  15. ↑ Wang, Runxin; Honda, Junya; Yamamoto, Hirosuke; Liu, Rongke; Hou, Yi (2015). "Construction of polar codes for channels with memory". 2015 IEEE Information Theory Workshop - Fall (ITW). IEEE. pp. 187–191. doi:10.1109/ITWF.2015.7360760. ISBN   978-1-4673-7852-9.
  16. ↑ Tal, Ido; Vardy, Alexander (2015). "List Decoding of Polar Codes". IEEE Transactions on Information Theory. 61 (5): 2213–2226. arXiv: 1206.0050 . doi:10.1109/TIT.2015.2410251. ISSN   0018-9448.
  17. ↑ Honda, Junya; Yamamoto, Hirosuke (2013). "Polar Coding Without Alphabet Extension for Asymmetric Models". IEEE Transactions on Information Theory. 59 (12): 7829–7838. doi:10.1109/TIT.2013.2282305. ISSN   0018-9448.
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.