Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Polar Codes: Finite Length Implementation, Error Correlations and Multilevel Modulation

Mani Bastani Parizi

Published Jan 1, 2012• 4 citations
OpenAlex

Abstract

Shannon, in his seminal work, formalized the transmission of data over a communication channel and determined its fundamental limits. He characterized the relation between communication rate and error probability and showed that as long as the communication rate is below the capacity of the channel, error probability can be made as small as desirable by using appropriate coding over the communication channel and letting the codeword length approach infinity. He provided the formula for capacity of discrete memoryless channel. However, his proposed coding scheme was too complex to be practical in communication systems. Polar codes, recently introduced by Arikan, are the first practical codes that are known to achieve the capacity for a large class of channel and have low encoding and decoding complexity. The original polar codes of Arikan achieve a block error probability decaying exponentially in the square root of the block length as it goes to infinity. However, it is interesting to investigate their performance in finite length as this is the case in all practical communication schemes. In this dissertation, after a brief overview on polar codes, we introduce a practical framework for simulation of error correcting codes in general. We introduce the importance sampling concept to efficiently evaluate the performance of polar codes with finite bock length. Next, based on simulation results, we investigate the performance of different genie aided decoders to mitigate the poor performance of polar codes in low to moderate block length and propose single-error correction methods to improve the performance dramatically in expense of complexity of decoder. In this context, we also study the correlation between error events in a successive cancellation decoder. Finally, we investigate the performance of polar codes in non-binary channels. We compare the code construction of Sasoglu for Q-ary channels and classical multilevel codes. We construct multilevel polar codes for Q-ary channels and provide a thorough comparison of complexity and performance of two methods in finite length.

Related papers

Convolutional Polar Codes

Andrew J. Ferris, Christoph Hirche, David Poulin

Arikan's Polar codes attracted much attention as the first efficiently decodable and capacity achieving codes. Furthermore, Polar codes exhibit an exponentially decreasing block error probability with an asymptotic error exponent upper bounded by 1/2. Since their discovery, many attempts have been made to improve the error exponent and the finite block-length performance, while keeping the bloc-structured kernel. Recently, two of us introduced a new family of efficiently decodable error-correction codes based on a recently discovered efficiently-contractible tensor network family in quantum many-body physics, called branching MERA. These codes, called branching MERA codes, include Polar codes and also extend them in a non-trivial way by substituting the bloc-structured kernel by a convolutional structure. Here, we perform an in-depth study of a particular example that can be thought of as a direct extension to Arikan's Polar code, which we therefore name Convolutional Polar codes. We prove that these codes polarize and exponentially suppress the channel's error probability, with an asymptotic error exponent log_2(3)/2 which is provably better than for Polar codes under successive cancellation decoding. We also perform finite block-size numerical simulations which display improved error-correcting capability with only a minor impact on decoding complexity.

arXiv:1704.00715•Apr 3, 2017•23 citations

Graph-theoretic Aspects of Polar Codes

Jessalyn Bolkema

In 2008, Arikan introduced a powerful family of polar codes, which are the first codes to demonstrably achieve Shannon capacity. Polar codes are built on (and named for) the phenomenon of channel polarization: a mechanism for synthetically increasing and decreasing the reliabilities of a set of channels until some fraction are perfectly noiseless and the remaining channels are completely noisy. In Arikan’s initial publication, this is achieved with a simple recursive binary transform, and shortly thereafter, it was shown by Korada et al. that polarization is a very general phenomenon achieved by many different (not necessarily binary) recursive transforms. Transmission is straightforward once the reliable channels have been identified, but this task is difficult, both computationally and theoretically. Moreover, the guarantees of polar code performance come to fruition only as the code length goes to infinity. Polar codes do not compare favorably to, e.g., low-density parity-check codes at finite block lengths. Motivated by these concerns, this dissertation investigates graph-theoretic properties of polar codes in the context of belief propagation decoding. We first define the class of encoding trellises applicable to the polar coding framework and give a graph- theoretic criterion for polarization. A fundamental contribution is the introduction of the tensor-like join of trellises: a graph product which supplies a direct connection to the matrix construction of polar codes. We leverage the tensor-like join throughout as a mechanism for understanding both graph-theoretic structures and decoding outcomes. We build up a family of acyclic auxiliary graphs, called computation graphs, in order to study belief propagation analytically. In this context, we show that the tensor-like join is sufficient as a construction mechanism and moreover, that such constructions endow computation graphs with powerful structural properties. Following Wiberg, we extend the notion of a deviation as an indicator for decoding failure in the polar computation graph framework. We provide a recursive characterization of the deviation set for Arikan’s polar codes. Finally, looking to the future, we focus on further applications of the tools developed herein.

•Jan 1, 2018•0 citations

From Polar to Reed-Muller Codes: A Technique to Improve the Finite-Length Performance

Marco Mondelli, Hamed Hassani, Rudiger L. Urbanke

We explore the relationship between polar and RM codes and we describe a coding scheme which improves upon the performance of the standard polar code at practical block lengths. Our starting point is the experimental observation that RM codes have a smaller error probability than polar codes under MAP decoding. This motivates us to introduce a family of codes that “interpolates” between RM and polar codes, call this family Cinter= {Cα: α ∈ [0, 1j}, where Cα|α=1is the original polar code, and Cα|α=0is an RM code. Based on numerical observations, we remark that the error probability under MAP decoding is an increasing function of α. MAP decoding has in general exponential complexity, but empirically the performance of polar codes at finite block lengths is boosted by moving along the family Cinter even under low-complexity decoding schemes such as, for instance, belief propagation or successive cancellation list decoder. We demonstrate the performance gain via numerical simulations for transmission over the erasure channel as well as the Gaussian channel.

arXiv:1401.3127•IEEE Transactions on Communications•Aug 1, 2014•138 citations

From polar to Reed-Muller codes: A technique to improve the finite-length performance

Marco Mondelli, Hamed Hassani, Rudiger L. Urbanke

We explore the relationship between polar and RM codes and we describe a coding scheme which improves upon the performance of the standard polar code at practical block lengths. Our starting point is the experimental observation that RM codes have a smaller error probability than polar codes under MAP decoding. This motivates us to introduce a family of codes that “interpolates” between RM and polar codes, call this family Cinter= {Cα: α ∈ [0, 1]}, where Cα|α=1is the original polar code, and Cα|α=0is an RM code. Based on numerical observations, we remark that the error probability under MAP decoding is an increasing function of α. MAP decoding has in general exponential complexity, but empirically the performance of polar codes at finite block lengths is boosted by moving along the family Cintereven under low-complexity decoding schemes such as, for instance, belief propagation or successive cancellation list decoder. We demonstrate the performance gain via numerical simulations for transmission over the erasure channel as well as the Gaussian channel.

IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2014•14 citations

Robust decoding schemes for polar coding over compound channels

Mine Alsan, Vincent Y. F. Tan

We consider the problem of designing robust and low complexity decoding schemes for polar coding over a given finite class of channels. We propose two schemes based on multiple runs of the polar successive cancellation decoder, where at each run a different metric adapted to a channel in the class is used in the decoder's decision procedure. The first scheme is a modified polar coding scheme which accommodates Cyclic Redundancy Check bits to help the decoder eliminate the estimates that do not pass the test. We show that this scheme achieves the symmetric capacity of the channel with a vanishing rate loss of O(1√N), where N is the blocklength of the code. The second scheme involves a polar decoding algorithm which implements a generalized likelihood ratio test. We show that over classes of channels which satisfy certain mild conditions, this scheme achieves the symmetric capacity of the channel. The analyses reveal that the decay of the error probability of both schemes is exponential in the square root of the blocklength, which is similar to the polar successive cancellation decoder operating with the knowledge of the true channel. Finally, we compare the schemes in terms of their performances and complexity, and discuss the extension to infinite classes of channels.

IEEE Information Theory Workshop (ITW)•Nov 1, 2017•0 citations

Log-Logarithmic Time Pruned Polar Coding

Hsin-Po Wang, Iwan Duursma

A pruned variant of polar coding is proposed for binary erasure channel (BEC). Fix any BEC. For sufficiently small ε > 0, we construct a series of capacity achieving codes with block length N = ε-4.9, code rate R = Capacity - O(ε), block error probability P = ε, and encoding and decoding time complexity bC = O(log|log ε|) per information bit. The given per-bit complexity bC is log-logarithmic in N, in Capacity - R, and in P. Beyond BEC, there is a generalization: Fix a prime q and fix a symmetric, q-ary-input, discrete-output memoryless channel. For sufficiently small ε > 0, we construct a series of error correction codes with block length N = ε-constant, code rate R = Capacity - O(ε), block error probability P = ε, and encoding and decoding time complexity bC = O(log|log ε|) per information bit. Over general channels, this family of codes has the lowest per-bit time complexity among all capacity-achieving codes known to date.

arXiv:1812.08106•IEEE Transactions on Information Theory•Dec 1, 2020•9 citations
Shannon, in his seminal work, formalized the transmission of data over a communication channel and determined its fundamental limits. He characterized the relation between communication rate and error probability and showed that as long as the communication rate is below the capacity of the channel, error probability can be made as small as desirable by using appropriate coding over the communication channel and letting the codeword length approach infinity. He provided the formula for capacity of discrete memoryless channel. However, his proposed coding scheme was too complex to be practical in communication systems. Polar codes, recently introduced by Arikan, are the first practical codes that are known to achieve the capacity for a large class of channel and have low encoding and decoding complexity. The original polar codes of Arikan achieve a block error probability decaying exponentially in the square root of the block length as it goes to infinity. However, it is interesting to investigate their performance in finite length as this is the case in all practical communication schemes. In this dissertation, after a brief overview on polar codes, we introduce a practical framework for simulation of error correcting codes in general. We introduce the importance sampling concept to efficiently evaluate the performance of polar codes with finite bock length. Next, based on simulation results, we investigate the performance of different genie aided decoders to mitigate the poor performance of polar codes in low to moderate block length and propose single-error correction methods to improve the performance dramatically in expense of complexity of decoder. In this context, we also study the correlation between error events in a successive cancellation decoder. Finally, we investigate the performance of polar codes in non-binary channels. We compare the code construction of Sasoglu for Q-ary channels and classical multilevel codes. We construct multilevel polar codes for Q-ary channels and provide a thorough comparison of complexity and performance of two methods in finite length.
Arikan's Polar codes attracted much attention as the first efficiently decodable and capacity achieving codes. Furthermore, Polar codes exhibit an exponentially decreasing block error probability with an asymptotic error exponent upper bounded by 1/2. Since their discovery, many attempts have been made to improve the error exponent and the finite block-length performance, while keeping the bloc-structured kernel. Recently, two of us introduced a new family of efficiently decodable error-correction codes based on a recently discovered efficiently-contractible tensor network family in quantum many-body physics, called branching MERA. These codes, called branching MERA codes, include Polar codes and also extend them in a non-trivial way by substituting the bloc-structured kernel by a convolutional structure. Here, we perform an in-depth study of a particular example that can be thought of as a direct extension to Arikan's Polar code, which we therefore name Convolutional Polar codes. We prove that these codes polarize and exponentially suppress the channel's error probability, with an asymptotic error exponent log_2(3)/2 which is provably better than for Polar codes under successive cancellation decoding. We also perform finite block-size numerical simulations which display improved error-correcting capability with only a minor impact on decoding complexity.
In 2008, Arikan introduced a powerful family of polar codes, which are the first codes to demonstrably achieve Shannon capacity. Polar codes are built on (and named for) the phenomenon of channel polarization: a mechanism for synthetically increasing and decreasing the reliabilities of a set of channels until some fraction are perfectly noiseless and the remaining channels are completely noisy. In Arikan’s initial publication, this is achieved with a simple recursive binary transform, and shortly thereafter, it was shown by Korada et al. that polarization is a very general phenomenon achieved by many different (not necessarily binary) recursive transforms. Transmission is straightforward once the reliable channels have been identified, but this task is difficult, both computationally and theoretically. Moreover, the guarantees of polar code performance come to fruition only as the code length goes to infinity. Polar codes do not compare favorably to, e.g., low-density parity-check codes at finite block lengths. Motivated by these concerns, this dissertation investigates graph-theoretic properties of polar codes in the context of belief propagation decoding. We first define the class of encoding trellises applicable to the polar coding framework and give a graph- theoretic criterion for polarization. A fundamental contribution is the introduction of the tensor-like join of trellises: a graph product which supplies a direct connection to the matrix construction of polar codes. We leverage the tensor-like join throughout as a mechanism for understanding both graph-theoretic structures and decoding outcomes. We build up a family of acyclic auxiliary graphs, called computation graphs, in order to study belief propagation analytically. In this context, we show that the tensor-like join is sufficient as a construction mechanism and moreover, that such constructions endow computation graphs with powerful structural properties. Following Wiberg, we extend the notion of a deviation as an indicator for decoding failure in the polar computation graph framework. We provide a recursive characterization of the deviation set for Arikan’s polar codes. Finally, looking to the future, we focus on further applications of the tools developed herein.
We explore the relationship between polar and RM codes and we describe a coding scheme which improves upon the performance of the standard polar code at practical block lengths. Our starting point is the experimental observation that RM codes have a smaller error probability than polar codes under MAP decoding. This motivates us to introduce a family of codes that “interpolates” between RM and polar codes, call this family Cinter= {Cα: α ∈ [0, 1j}, where Cα|α=1is the original polar code, and Cα|α=0is an RM code. Based on numerical observations, we remark that the error probability under MAP decoding is an increasing function of α. MAP decoding has in general exponential complexity, but empirically the performance of polar codes at finite block lengths is boosted by moving along the family Cinter even under low-complexity decoding schemes such as, for instance, belief propagation or successive cancellation list decoder. We demonstrate the performance gain via numerical simulations for transmission over the erasure channel as well as the Gaussian channel.
We explore the relationship between polar and RM codes and we describe a coding scheme which improves upon the performance of the standard polar code at practical block lengths. Our starting point is the experimental observation that RM codes have a smaller error probability than polar codes under MAP decoding. This motivates us to introduce a family of codes that “interpolates” between RM and polar codes, call this family Cinter= {Cα: α ∈ [0, 1]}, where Cα|α=1is the original polar code, and Cα|α=0is an RM code. Based on numerical observations, we remark that the error probability under MAP decoding is an increasing function of α. MAP decoding has in general exponential complexity, but empirically the performance of polar codes at finite block lengths is boosted by moving along the family Cintereven under low-complexity decoding schemes such as, for instance, belief propagation or successive cancellation list decoder. We demonstrate the performance gain via numerical simulations for transmission over the erasure channel as well as the Gaussian channel.
We consider the problem of designing robust and low complexity decoding schemes for polar coding over a given finite class of channels. We propose two schemes based on multiple runs of the polar successive cancellation decoder, where at each run a different metric adapted to a channel in the class is used in the decoder's decision procedure. The first scheme is a modified polar coding scheme which accommodates Cyclic Redundancy Check bits to help the decoder eliminate the estimates that do not pass the test. We show that this scheme achieves the symmetric capacity of the channel with a vanishing rate loss of O(1√N), where N is the blocklength of the code. The second scheme involves a polar decoding algorithm which implements a generalized likelihood ratio test. We show that over classes of channels which satisfy certain mild conditions, this scheme achieves the symmetric capacity of the channel. The analyses reveal that the decay of the error probability of both schemes is exponential in the square root of the blocklength, which is similar to the polar successive cancellation decoder operating with the knowledge of the true channel. Finally, we compare the schemes in terms of their performances and complexity, and discuss the extension to infinite classes of channels.
A pruned variant of polar coding is proposed for binary erasure channel (BEC). Fix any BEC. For sufficiently small ε > 0, we construct a series of capacity achieving codes with block length N = ε-4.9, code rate R = Capacity - O(ε), block error probability P = ε, and encoding and decoding time complexity bC = O(log|log ε|) per information bit. The given per-bit complexity bC is log-logarithmic in N, in Capacity - R, and in P. Beyond BEC, there is a generalization: Fix a prime q and fix a symmetric, q-ary-input, discrete-output memoryless channel. For sufficiently small ε > 0, we construct a series of error correction codes with block length N = ε-constant, code rate R = Capacity - O(ε), block error probability P = ε, and encoding and decoding time complexity bC = O(log|log ε|) per information bit. Over general channels, this family of codes has the lowest per-bit time complexity among all capacity-achieving codes known to date.