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

arXiv:2204.07435

Performance and Construction of Polar Codes: The Perspective of Bit Error Probability

Bolin Wu, Kai Niu, Jincheng Dai

Published Apr 15, 2022• 1 citation
arXivHTMLPDF

Abstract

Most existing works of polar codes focus on the analysis of block error probability. However, in many scenarios, bit error probability is also important for evaluating the performance of channel codes. In this paper, we establish a new framework to analyze the bit error probability of polar codes. Specifically, by revisiting the error event of bit-channel, we first introduce the conditional bit error probability as a metric to evaluate the reliability of bit-channel for both systematic and non-systematic polar codes. Guided by the concept of polar subcode, we then derive an upper bound on the conditional bit error probability of each bit-channel, and accordingly, an upper bound on the bit error probability of polar codes. Based on these, two types of construction metrics aiming at minimizing the bit error probability of polar codes are proposed, which are of linear computational complexity and explicit forms. Simulation results show that the polar codes constructed by the proposed methods can outperform those constructed by the conventional methods.

DOI
10.48550/arxiv.2204.07435

Related papers

A Lower Bound on the Probability of Error of Polar Codes over BMS Channels

Boaz Shuval, Ido Tal

Polar codes are a family of capacity-achieving codes that have explicit and low-complexity construction, encoding, and decoding algorithms. Decoding of polar codes is based on the successive-cancellation decoder, which decodes in a bit-wise manner. A decoding error occurs when at least one bit is erroneously decoded. The various codeword bits are correlated, yet performance analysis of polar codes ignores this dependence: the upper bound is based on the union bound, and the lower bound is based on the worst-performing bit. Improvement of the lower bound is afforded by considering error probabilities of two bits simultaneously. These are difficult to compute explicitly due to the large alphabet size inherent to polar codes. In this paper, we propose a method to lower-bound the error probabilities of bit pairs. We develop several transformations on pairs of synthetic channels that make the resultant synthetic channels amenable to alphabet reduction. Our method yields lower bounds that significantly improve upon currently known lower bounds for polar codes under successive-cancellation decoding.

arXiv:1701.01628•IEEE Transactions on Information Theory•Oct 12, 2018•9 citations

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

Mani Bastani Parizi

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.

•Jan 1, 2012•4 citations

Bit-Level Construction for Multiplicative-Repetition-Based Non-Binary Polar Codes

Rongchi Xu, Peiyao Chen, Ling Liu +2 more

In this paper, we discuss non-binary polar codes using a 2×2 matrix over a Galois field GF(2q) as the kernel. Conventional construction of non-binary polar codes divides the synthesized channels into frozen channels and information channels. Each information channel carries one symbol, i.e., q bits. However, there are many middle channels with insufficient polarization, which cannot carry one symbol of q bits but only i bits, 1≤i<q,i∈Z, at finite block length. In this paper, we consider bit-level construction for multiplicative repetition (MR)-based non-binary polar codes and propose a bit-level construction based on the two following methods. We first calculate the error probability and channel capacity lower bound of each synthesized channel based on the channel degradation method, and then determine both the number and index of the carried bits for each synthesized channel according to the symbol error probability and capacity. To reduce complexity, we also introduce a Monte-Carlo method. We compute the error probability of each synthesized channel carrying i information bits and select the optimal construction that can minimize the union bound of the error probability. Finally, an improved construction-based probabilistic shaping method for MR-based non-binary polar codes is considered. Simulation results show that the proposed construction significantly improved the decoding performance compared with the conventional construction scheme.

Entropy•Apr 2, 2025•2 citations

Construction of Polar Codes

Mohammad Rowshan, Emanuele Viterbo

The construction of polar codes is critical in determining their error correction performance, computational complexity, and suitability for diverse applications. This chapter explores various methods for constructing polar codes, focusing on their trade-offs in terms of computational complexity, accuracy, and error correction performance. It explores both channel-dependent approaches, such as density evolution and Gaussian approximation, and channel-independent methods, including partial orders and polarization weights. The chapter discusses the construction of concatenated codes, such as cyclic redundancy check-polar codes and polarization-adjusted convolutional codes, which have demonstrated enhanced performance in practical scenarios. It focuses on practical and low-complexity construction techniques suitable for real-world applications. By understanding the differences between the presented techniques, the readers will be equipped to select and implement the most suitable construction method for their specific decoders and application needs.

arXiv:1209.4444•Wiley eBooks•Oct 27, 2025•7 citations

On bit error rate performance of polar codes in finite regime

Ali Eslami, Hossein Pishro-Nik

Polar codes have been recently proposed as the first low complexity class of codes that can provably achieve the capacity of symmetric binary-input memoryless channels. Here, we study the bit error rate performance of finite-length polar codes under Belief Propagation (BP) decoding. We analyze the stopping sets of polar codes and the size of the minimal stopping set, called “stopping distance”. Stopping sets, as they contribute to the decoding failure, play an important role in bit error rate and error floor performance of the code. We show that the stopping distance for binary polar codes, if carefully designed, grows as O(√N) where N is the code-length. We provide bit error rate (BER) simulations for polar codes over binary erasure and gaussian channels, showing no sign of error floor down to the BERs of 10-11. Our simulations asserts that while finite-length polar codes do not perform as good as LDPC codes in terms of bit error rate, they show superior error floor performance. Motivated by good error floor performance, we introduce a modified version of BP decoding employing a guessing algorithm to improve the BER performance of polar codes. Our simulations for this guessing algorithm show two orders of magnitude improvement over simple BP decoding for the binary erasure channel (BEC), and up to 0.3 dB improvement for the gaussian channel at BERs of 10-6.

Allerton Conference on Communication, Control, and Computing•Sep 1, 2010•54 citations

A Hybrid Reliability--Weight Framework for Construction of Polar Codes

Mohammad Rowshan, Vlad Drăgoi

Polar codes are usually constructed by ranking synthetic bit-channels according to reliability, which guarantees capacity-achieving behavior but can yield poor low-weight spectra at short and moderate lengths. Recent algebraic results express the contribution of individual bit-channels to the multiplicities of minimum and near-minimum weight codewords in closed form. In this work we combine these insights into a mixed (reliability--weight) bit-channel ordering. We define a per-bit cost whose distance term is derived from orbit enumeration of minimum-weight codewords and scaled by a Bhattacharyya-type factor, and show that the resulting mixed construction minimises a truncated SC/ML union-bound surrogate within a class of decreasing monomial codes. We relate the mixed metric to error events in SCL decoding via a pruning/ML decomposition, and prove that mixed designs act as local perturbations of reliability-based constructions whose asymptotic impact vanishes as code-length approaches infinity. Numerical results for short and moderate lengths on BPSK-AWGN, implemented via Gaussian approximation and closed-form weight contributions, illustrate the trade-off between pure reliability-based and mixed constructions in terms of minimum distance, multiplicity, and union-bound approximations. All proofs are deferred to the appendices.

arXiv:2601.10376•Jan 15, 2026•0 citations
Most existing works of polar codes focus on the analysis of block error probability. However, in many scenarios, bit error probability is also important for evaluating the performance of channel codes. In this paper, we establish a new framework to analyze the bit error probability of polar codes. Specifically, by revisiting the error event of bit-channel, we first introduce the conditional bit error probability as a metric to evaluate the reliability of bit-channel for both systematic and non-systematic polar codes. Guided by the concept of polar subcode, we then derive an upper bound on the conditional bit error probability of each bit-channel, and accordingly, an upper bound on the bit error probability of polar codes. Based on these, two types of construction metrics aiming at minimizing the bit error probability of polar codes are proposed, which are of linear computational complexity and explicit forms. Simulation results show that the polar codes constructed by the proposed methods can outperform those constructed by the conventional methods.
Polar codes are a family of capacity-achieving codes that have explicit and low-complexity construction, encoding, and decoding algorithms. Decoding of polar codes is based on the successive-cancellation decoder, which decodes in a bit-wise manner. A decoding error occurs when at least one bit is erroneously decoded. The various codeword bits are correlated, yet performance analysis of polar codes ignores this dependence: the upper bound is based on the union bound, and the lower bound is based on the worst-performing bit. Improvement of the lower bound is afforded by considering error probabilities of two bits simultaneously. These are difficult to compute explicitly due to the large alphabet size inherent to polar codes. In this paper, we propose a method to lower-bound the error probabilities of bit pairs. We develop several transformations on pairs of synthetic channels that make the resultant synthetic channels amenable to alphabet reduction. Our method yields lower bounds that significantly improve upon currently known lower bounds for polar codes under successive-cancellation decoding.
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.
In this paper, we discuss non-binary polar codes using a 2×2 matrix over a Galois field GF(2q) as the kernel. Conventional construction of non-binary polar codes divides the synthesized channels into frozen channels and information channels. Each information channel carries one symbol, i.e., q bits. However, there are many middle channels with insufficient polarization, which cannot carry one symbol of q bits but only i bits, 1≤i<q,i∈Z, at finite block length. In this paper, we consider bit-level construction for multiplicative repetition (MR)-based non-binary polar codes and propose a bit-level construction based on the two following methods. We first calculate the error probability and channel capacity lower bound of each synthesized channel based on the channel degradation method, and then determine both the number and index of the carried bits for each synthesized channel according to the symbol error probability and capacity. To reduce complexity, we also introduce a Monte-Carlo method. We compute the error probability of each synthesized channel carrying i information bits and select the optimal construction that can minimize the union bound of the error probability. Finally, an improved construction-based probabilistic shaping method for MR-based non-binary polar codes is considered. Simulation results show that the proposed construction significantly improved the decoding performance compared with the conventional construction scheme.
The construction of polar codes is critical in determining their error correction performance, computational complexity, and suitability for diverse applications. This chapter explores various methods for constructing polar codes, focusing on their trade-offs in terms of computational complexity, accuracy, and error correction performance. It explores both channel-dependent approaches, such as density evolution and Gaussian approximation, and channel-independent methods, including partial orders and polarization weights. The chapter discusses the construction of concatenated codes, such as cyclic redundancy check-polar codes and polarization-adjusted convolutional codes, which have demonstrated enhanced performance in practical scenarios. It focuses on practical and low-complexity construction techniques suitable for real-world applications. By understanding the differences between the presented techniques, the readers will be equipped to select and implement the most suitable construction method for their specific decoders and application needs.
Polar codes have been recently proposed as the first low complexity class of codes that can provably achieve the capacity of symmetric binary-input memoryless channels. Here, we study the bit error rate performance of finite-length polar codes under Belief Propagation (BP) decoding. We analyze the stopping sets of polar codes and the size of the minimal stopping set, called “stopping distance”. Stopping sets, as they contribute to the decoding failure, play an important role in bit error rate and error floor performance of the code. We show that the stopping distance for binary polar codes, if carefully designed, grows as O(√N) where N is the code-length. We provide bit error rate (BER) simulations for polar codes over binary erasure and gaussian channels, showing no sign of error floor down to the BERs of 10-11. Our simulations asserts that while finite-length polar codes do not perform as good as LDPC codes in terms of bit error rate, they show superior error floor performance. Motivated by good error floor performance, we introduce a modified version of BP decoding employing a guessing algorithm to improve the BER performance of polar codes. Our simulations for this guessing algorithm show two orders of magnitude improvement over simple BP decoding for the binary erasure channel (BEC), and up to 0.3 dB improvement for the gaussian channel at BERs of 10-6.
Polar codes are usually constructed by ranking synthetic bit-channels according to reliability, which guarantees capacity-achieving behavior but can yield poor low-weight spectra at short and moderate lengths. Recent algebraic results express the contribution of individual bit-channels to the multiplicities of minimum and near-minimum weight codewords in closed form. In this work we combine these insights into a mixed (reliability--weight) bit-channel ordering. We define a per-bit cost whose distance term is derived from orbit enumeration of minimum-weight codewords and scaled by a Bhattacharyya-type factor, and show that the resulting mixed construction minimises a truncated SC/ML union-bound surrogate within a class of decreasing monomial codes. We relate the mixed metric to error events in SCL decoding via a pruning/ML decomposition, and prove that mixed designs act as local perturbations of reliability-based constructions whose asymptotic impact vanishes as code-length approaches infinity. Numerical results for short and moderate lengths on BPSK-AWGN, implemented via Gaussian approximation and closed-form weight contributions, illustrate the trade-off between pure reliability-based and mixed constructions in terms of minimum distance, multiplicity, and union-bound approximations. All proofs are deferred to the appendices.