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

Allerton Conference on Communication, Control, and Computing

On bit error rate performance of polar codes in finite regime

Ali Eslami, Hossein Pishro-Nik

Published Sep 1, 2010• 54 citations
Publisher

Abstract

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.

DOI
10.1109/allerton.2010.5706906

Related papers

Enhanced Belief Propagation Polar Decoder for Finite Lengths

Shajeel Iqbal, GoangSeog Choi

In this paper, we discuss the belief propagation decoding algorithm for polar codes. The performance of Polar codes for shorter lengths is not satisfactory. Motivated by this, we propose a novel technique to improve its performance at short lengths. We showed that the probability of messages passed along the factor graph of polar codes, can be increased by multiplying the current message of nodes with their previous message. This is like a feedback path in which the present signal is updated by multiplying with its previous signal. Thus the experimental results show that performance of belief propagation polar decoder can be improved using this proposed technique. Simulation results in binary-input additive white Gaussian noise channel (BI-AWGNC) show that the proposed belief propagation polar decoder can provide significant gain of 2 dB over the original belief propagation polar decoder with code rate 0.5 and code length 128 at the bit error rate (BER) of $10^{-4}$ .

Journal of the Korea Society of Digital Industry and Information Management•Sep 30, 2015•0 citations

Frozen bits selection for polar codes based on simulation and BP decoding

Jingbo Liu, Jin Sha

In the construction of polar code, the selection of frozen bits affects the error-correcting performance significantly. Several calculation-based algorithms have been proposed for general binary-input discrete memoryless channels (B-DMCs) like the additive white Gaussian noise (AWGN) channel. In this paper, a method for frozen bits selection based on Monte Carlo simulation and belief propagation (BP) decoding is proposed. The information bits are selected out one by one incrementally. The numerical results show that the proposed algorithm can effectively improve the bit error rate (BER) and frame error rate (FER) performance compared with the conventional selection method, especially in high signal noise ratio (SNR) region. Moreover, the algorithm can be used to construct polar codes with any rate through a complete iteration.

IEICE Electronics Express•Jan 1, 2017•13 citations

Analysis of decoding error probability for finite length LDPC codes

隆之 野崎

Low-density parity-check (LDPC) codes are linear codes defined by sparse parity check matrices.Due to the sparseness of the parity check matrices, LDPC codes are efficiently decoded by the belief propagation (BP) decoder.It is known that non-binary LDPC codes can outperform binary ones.However, the decoding complexity grows with the size of non-binary alphabets.Hence, there is a trade-off between performance and complexity.In this dissertation, we focus on both binary and non-binary LDPC codes.We analyze the decoding error probability for finite length LDPC codes under BP decoding.The curve of the decoding error probability for finite length LDPC codes, as a function of channel error probability, is divided into two regions called waterfall region and error floor region.We analyze the decoding error probability in the waterfall region for binary LDPC codes and in the error floor region for non-binary LDPC codes.The main results of this dissertation are summarized as follows:• We analyze the decoding erasure probabilities of waterfall regions for binary LDPC codes over binary erasure channels (BECs) without any assumptions by analytically solving the covariance evolution.• We propose a method to lower the decoding error rates in the error floors of non-binary LDPC codes defined over Galois field and general linear group transmitted over the BEC, the memoryless binary-input output-symmetric (MBIOS) channel and q-ary memoryless symmetric (q-MS) channel.Simulation results show that the decoding error rates of the codes designed by the proposed method outperform those of the codes designed by the conventional method proposed by Poulliat et al.• We give lower bounds of decoding error rates in the error floor regions for non-binary LDPC codes over the BEC, MBIOS channel and q-MS channel.Simulation results show that those lower bounds are tight.Moreover, we show that the decoding error rates for non-binary LDPC codes defined over general linear group have same decoding performance in the error floor regions with that for non-binary LDPC codes defined over Galois field.Furthermore, we show that this tight lower bound monotonically decreases, as the order of Galois field of non-binary LDPC code increases in the BEC and binary additive white Gaussian noise channel.iii • We derive the weight distribution of the decoding error patterns in the BP decoder for non-binary LDPC codes defined over general linear group transmitted over the BEC.

•Jan 1, 2012•0 citations

Finite-length analysis of turbo decoding on the binary erasure channel

Eirik Rosnes, Øyvind Ytrehus

This paper is devoted to the finite-length analysis of turbo decoding over the binary erasure channel (BEC). The performance of iterative belief-propagation (BP) decoding of low-density parity-check (LDPC) codes over the BEC can be characterized in terms of stopping sets. In the first part we describe turbo decoding on the BEC which is simpler than turbo decoding on other channels. We then adapt the concept of stopping sets to turbo decoding and state an exact condition for decoding failure. Apply turbo decoding until the transmitted codeword has been recovered, or until the decoder fails to progress further. Then the set of erased positions that will remain when the decoder stops is equal to the unique maximum size turbo stopping set which is also a subset of the set of erased positions. In the second part we present some improvements of the basic turbo decoding algorithm on the BEC. The proposed improved turbo decoding algorithm has substantially better error performance as illustrated by the given simulation results

IEEE International Symposium on Information Theory (ISIT)•Jan 1, 2005•4 citations

Upper Bounding the Performance of Arbitrary Finite LDPC Codes on Binary Erasure Channels

Chih-chun Wang, Sanjeev R. Kulkarni, H. Vincent Poor

Assuming iterative decoding for binary erasure channels (BECs), a novel tree-based technique for upper bounding the bit error rates (BERs) of arbitrary, finite low-density parity-check (LDPC) codes is provided and the resulting bound can be evaluated for all operating erasure probabilities, including both the waterfall and the error floor regions. This upper bound can also be viewed as a narrowing search of stopping sets, which is an approach different from the stopping set enumeration used for lower bounding the error floor. When combined with optimal leaf-finding modules, this upper bound is guaranteed to be tight in terms of the asymptotic order. The Boolean framework proposed herein further admits a composite search for even tighter results. For comparison, a refinement of the algorithm is capable of exhausting all stopping sets of size les 13 for irregular LDPC codes of length n ap 500, which requires (13500) ap 1.67 times 1025trials if a brute force approach is taken. These experiments indicate that this upper bound can be used both as an analytical tool and as a deterministic worst-performance (error floor) guarantee, the latter of which is crucial to optimizing LDPC codes for extremely low BER applications, e.g., optical/satellite communications

arXiv:cs/0605086•IEEE International Symposium on Information Theory (ISIT)•Jul 1, 2006•9 citations

Belief Propagation With Permutated Graphs of Polar Codes

Liping Li, Liangliang Liu

The belief propagation (BP) decoding of polar codes provides better bit error rate (BER) and packet error rate (PER) performance than the successive cancelation (SC) decoding. It has been reported in the literature that the graph of BP decoding of polar codes can be permuted to provide even better decoding performance. In this paper, we theoretically prove that all permutations of the graph are equivalent in terms of the polar encoding. For BP decoding, it is shown that permutations of the layers of the graph also permute the bit channels. A principle which protects the weakest information bit channel is provided in the paper. Two parallel BP decoders, one employing the standard graph and the other selected based on the selection principle, are also proposed to work together. The simulation results show that when the total number of iterations is fixed, the proposed BP decoding can have the same performance as the existing permutation scheme while provides a higher throughput.

IEEE Access•Jan 1, 2020•8 citations
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.
In this paper, we discuss the belief propagation decoding algorithm for polar codes. The performance of Polar codes for shorter lengths is not satisfactory. Motivated by this, we propose a novel technique to improve its performance at short lengths. We showed that the probability of messages passed along the factor graph of polar codes, can be increased by multiplying the current message of nodes with their previous message. This is like a feedback path in which the present signal is updated by multiplying with its previous signal. Thus the experimental results show that performance of belief propagation polar decoder can be improved using this proposed technique. Simulation results in binary-input additive white Gaussian noise channel (BI-AWGNC) show that the proposed belief propagation polar decoder can provide significant gain of 2 dB over the original belief propagation polar decoder with code rate 0.5 and code length 128 at the bit error rate (BER) of 10−410^{-4}10−4 .
In the construction of polar code, the selection of frozen bits affects the error-correcting performance significantly. Several calculation-based algorithms have been proposed for general binary-input discrete memoryless channels (B-DMCs) like the additive white Gaussian noise (AWGN) channel. In this paper, a method for frozen bits selection based on Monte Carlo simulation and belief propagation (BP) decoding is proposed. The information bits are selected out one by one incrementally. The numerical results show that the proposed algorithm can effectively improve the bit error rate (BER) and frame error rate (FER) performance compared with the conventional selection method, especially in high signal noise ratio (SNR) region. Moreover, the algorithm can be used to construct polar codes with any rate through a complete iteration.
Low-density parity-check (LDPC) codes are linear codes defined by sparse parity check matrices.Due to the sparseness of the parity check matrices, LDPC codes are efficiently decoded by the belief propagation (BP) decoder.It is known that non-binary LDPC codes can outperform binary ones.However, the decoding complexity grows with the size of non-binary alphabets.Hence, there is a trade-off between performance and complexity.In this dissertation, we focus on both binary and non-binary LDPC codes.We analyze the decoding error probability for finite length LDPC codes under BP decoding.The curve of the decoding error probability for finite length LDPC codes, as a function of channel error probability, is divided into two regions called waterfall region and error floor region.We analyze the decoding error probability in the waterfall region for binary LDPC codes and in the error floor region for non-binary LDPC codes.The main results of this dissertation are summarized as follows:• We analyze the decoding erasure probabilities of waterfall regions for binary LDPC codes over binary erasure channels (BECs) without any assumptions by analytically solving the covariance evolution.• We propose a method to lower the decoding error rates in the error floors of non-binary LDPC codes defined over Galois field and general linear group transmitted over the BEC, the memoryless binary-input output-symmetric (MBIOS) channel and q-ary memoryless symmetric (q-MS) channel.Simulation results show that the decoding error rates of the codes designed by the proposed method outperform those of the codes designed by the conventional method proposed by Poulliat et al.• We give lower bounds of decoding error rates in the error floor regions for non-binary LDPC codes over the BEC, MBIOS channel and q-MS channel.Simulation results show that those lower bounds are tight.Moreover, we show that the decoding error rates for non-binary LDPC codes defined over general linear group have same decoding performance in the error floor regions with that for non-binary LDPC codes defined over Galois field.Furthermore, we show that this tight lower bound monotonically decreases, as the order of Galois field of non-binary LDPC code increases in the BEC and binary additive white Gaussian noise channel.iii • We derive the weight distribution of the decoding error patterns in the BP decoder for non-binary LDPC codes defined over general linear group transmitted over the BEC.
This paper is devoted to the finite-length analysis of turbo decoding over the binary erasure channel (BEC). The performance of iterative belief-propagation (BP) decoding of low-density parity-check (LDPC) codes over the BEC can be characterized in terms of stopping sets. In the first part we describe turbo decoding on the BEC which is simpler than turbo decoding on other channels. We then adapt the concept of stopping sets to turbo decoding and state an exact condition for decoding failure. Apply turbo decoding until the transmitted codeword has been recovered, or until the decoder fails to progress further. Then the set of erased positions that will remain when the decoder stops is equal to the unique maximum size turbo stopping set which is also a subset of the set of erased positions. In the second part we present some improvements of the basic turbo decoding algorithm on the BEC. The proposed improved turbo decoding algorithm has substantially better error performance as illustrated by the given simulation results
Assuming iterative decoding for binary erasure channels (BECs), a novel tree-based technique for upper bounding the bit error rates (BERs) of arbitrary, finite low-density parity-check (LDPC) codes is provided and the resulting bound can be evaluated for all operating erasure probabilities, including both the waterfall and the error floor regions. This upper bound can also be viewed as a narrowing search of stopping sets, which is an approach different from the stopping set enumeration used for lower bounding the error floor. When combined with optimal leaf-finding modules, this upper bound is guaranteed to be tight in terms of the asymptotic order. The Boolean framework proposed herein further admits a composite search for even tighter results. For comparison, a refinement of the algorithm is capable of exhausting all stopping sets of size les 13 for irregular LDPC codes of length n ap 500, which requires (13500) ap 1.67 times 1025trials if a brute force approach is taken. These experiments indicate that this upper bound can be used both as an analytical tool and as a deterministic worst-performance (error floor) guarantee, the latter of which is crucial to optimizing LDPC codes for extremely low BER applications, e.g., optical/satellite communications
The belief propagation (BP) decoding of polar codes provides better bit error rate (BER) and packet error rate (PER) performance than the successive cancelation (SC) decoding. It has been reported in the literature that the graph of BP decoding of polar codes can be permuted to provide even better decoding performance. In this paper, we theoretically prove that all permutations of the graph are equivalent in terms of the polar encoding. For BP decoding, it is shown that permutations of the layers of the graph also permute the bit channels. A principle which protects the weakest information bit channel is provided in the paper. Two parallel BP decoders, one employing the standard graph and the other selected based on the selection principle, are also proposed to work together. The simulation results show that when the total number of iterations is fixed, the proposed BP decoding can have the same performance as the existing permutation scheme while provides a higher throughput.