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

IEEE International Wireless Symposium

A simplified belief propagation decoder for polar codes

Yingxian Zhang, Qingshuang Zhang, Xiaofei Pan, Zhan Ye, Chao Gong

Published Mar 1, 2014• 26 citations
Publisher

Abstract

In this paper, we propose a simplified belief propagation(SBP) decoder for the polar codes, where the update calculation for the messages of the so-called frozen nodes is replaced by setting these nodes' messages by prior probabilities during the BP procedure. Numerical results show that the derived SBP yields almost the same performance as the BP decoders in the literature, while the computational complexity is reduced significantly, which make our SBP more suitable for practical application as compared to the existing BP decoders.

DOI
10.1109/ieee-iws.2014.6864206

Related papers

Study of Adaptive Reweighted Sparse Belief Propagation Decoders for Polar Codes

Robert M. Oliveira, Rodrigo C. de Lamare

In this paper, we present an adaptive reweighted sparse belief propagation (AR-SBP) decoder for polar codes. The AR-SBP technique is inspired by decoders that employ the sum-product algorithm for low-density parity-check codes. In particular, the AR-SBP decoding strategy introduces reweighting of the exchanged log-likelihood-ratio in order to refine the message passing, improving the performance of the decoder and reducing the number of required iterations. An analysis of the convergence of AR-SBP is carried out along with a study of the complexity of the analyzed decoders. Numerical examples show that the AR-SBP decoder outperforms existing decoding algorithms for a reduced number of iterations, enabling low-latency applications.

arXiv:2404.04674•Apr 6, 2024•0 citations

Adaptive Reweighted Sparse Belief Propagation Decoding for Polar Codes

Robert M. Oliveira, Rodrigo C. de Lamare

In this paper, we present an adaptive reweighted sparse belief propagation (AR-SBP) decoder for polar codes. The AR-SBP technique is inspired by decoders that employ the sum-product algorithm for low-density parity-check codes. In particular, the AR-SBP decoding strategy introduces reweighting of the exchanged log-likelihood-ratio in order to refine the message passing, improving the performance of the decoder and reducing the number of required iterations. An analysis of the convergence of AR-SBP is carried out along with a study of the complexity of the analyzed decoders. Numerical examples show that the AR-SBP decoder outperforms existing decoding algorithms for a reduced number of iterations, enabling low-latency applications.

IEEE International Conference on Acoustics Speech and Signal Processing•Mar 18, 2024•0 citations

A Modified BP for Polar Codes

Zhang Qing-shuan

This paper proposes a modified belief propagation( MBP) decoder for polar codes,in which the log-likelihood ratios( LLRs) associated with the frozen nodes would be revised by a selective correction parameter when the LLRs of frozen nodes are wrongly calculated. By using the Gaussian approximation,an appropriate parameter is obtained creatively. The principles of log-domain BP decoder and corresponding modified decoding algorithm are described in this paper. Finally,computational complexity analysis and performance simulation are given. Data results indicate that compared with the existing BP decoder,the modified BP decoder can obtain a better bit error performance of about 0. 2 dB at the cost of a little computational complexity.

Communications technology•Jan 1, 2014•0 citations

Sparse Graphs for Belief Propagation Decoding of Polar Codes

Sebastian Cammerer, Moustafa Ebada, Ahmed Elkelesh +1 more

We describe a novel approach to interpret a polar code as a low-density parity-check (LDPC)-like code with an underlying sparse decoding graph. This sparse graph is based on the encoding factor graph of polar codes and is suitable for conventional belief propagation (BP) decoding. We discuss several pruning techniques based on the check node decoder (CND) and variable node decoder (VND) update equations, significantly reducing the size (i.e., decoding complexity) of the parity-check matrix. As a result, iterative polar decoding can then be conducted on a sparse graph, akin to the traditional well-established LDPC decoding, e.g., using a fully parallel sum-product algorithm (SPA). This facilitates the systematic analysis and design of polar codes using the well-established tools known from analyzing LDPC codes. We show that the proposed iterative polar decoder has a negligible performance loss for short-to-intermediate codelengths compared to Arikan's original BP decoder. Finally, the proposed decoder is shown to benefit from both reduced complexity and reduced memory requirements and, thus, is more suitable for hardware implementations.

arXiv:1712.08538•IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2018•58 citations

Computational Complexity Reduced Belief Propagation Algorithm for Polar Code Decoders

Arvid B. van den Brink, Marco J.G. Bekooij

The belief propagation algorithm is desirable for a polar code based decoder, because of the potentially low latency and the ability of integration in digital signal processing units or other multi-core processor systems to parallelize the computations. Although belief propagation polar code decoder algorithms have the ability for a highly parallelized imple-mentation, the algorithms require many iterations to achieve a comparable frame error rate and bit error rate with respect to a successive cancellation polar code algorithm. The iterative nature of the belief propagation algorithms also result in a higher computational complexity, i.e. O(IN(2log_{2} N-1)) compared to the computational complexity O(Nlog_{2}N) of the successive cancellation decoder algorithm. In this paper we propose several simplifications for a simplified belief propagation algorithm for polar code decoders, where the arithmetic complexity of the nodes is reduced. The proposed belief propagation algorithm shows preliminary results of a net reduction of the arithmetic complexity of ≈ 13%. This reduction is a result of the reduced number of arithmetic operations, i.e., additions, compares, and multiplications, without a lost in error-correcting performance.

•Feb 3, 2021•0 citations

XJ-BP: Express Journey Belief Propagation Decoding for Polar Codes

Jingwei Xu, Tiben Che, Gwan Choi

This paper presents a novel belief propagation (BP) based decoding algorithm for polar codes. The proposed algorithm facilitates belief propagation by utilizing the specific constituent codes that exist in the factor graph, which results in an express journey (XJ) for belief information to propagate in each decoding iteration. In addition, this XJ-BP decoder employs a novel round-trip message passing scheduling method for the increased efficiency. The proposed method simplifies min-sum (MS) BP decoder by 40.6%. Along with the round-trip scheduling, the XJ-BP algorithm reduces the computational complexity of MS BP decoding by 90.4%; this enables an energy-efficient hardware implementation of BP decoding in practice.

Globecom•Dec 1, 2015•44 citations
In this paper, we propose a simplified belief propagation(SBP) decoder for the polar codes, where the update calculation for the messages of the so-called frozen nodes is replaced by setting these nodes' messages by prior probabilities during the BP procedure. Numerical results show that the derived SBP yields almost the same performance as the BP decoders in the literature, while the computational complexity is reduced significantly, which make our SBP more suitable for practical application as compared to the existing BP decoders.
In this paper, we present an adaptive reweighted sparse belief propagation (AR-SBP) decoder for polar codes. The AR-SBP technique is inspired by decoders that employ the sum-product algorithm for low-density parity-check codes. In particular, the AR-SBP decoding strategy introduces reweighting of the exchanged log-likelihood-ratio in order to refine the message passing, improving the performance of the decoder and reducing the number of required iterations. An analysis of the convergence of AR-SBP is carried out along with a study of the complexity of the analyzed decoders. Numerical examples show that the AR-SBP decoder outperforms existing decoding algorithms for a reduced number of iterations, enabling low-latency applications.
In this paper, we present an adaptive reweighted sparse belief propagation (AR-SBP) decoder for polar codes. The AR-SBP technique is inspired by decoders that employ the sum-product algorithm for low-density parity-check codes. In particular, the AR-SBP decoding strategy introduces reweighting of the exchanged log-likelihood-ratio in order to refine the message passing, improving the performance of the decoder and reducing the number of required iterations. An analysis of the convergence of AR-SBP is carried out along with a study of the complexity of the analyzed decoders. Numerical examples show that the AR-SBP decoder outperforms existing decoding algorithms for a reduced number of iterations, enabling low-latency applications.
This paper proposes a modified belief propagation( MBP) decoder for polar codes,in which the log-likelihood ratios( LLRs) associated with the frozen nodes would be revised by a selective correction parameter when the LLRs of frozen nodes are wrongly calculated. By using the Gaussian approximation,an appropriate parameter is obtained creatively. The principles of log-domain BP decoder and corresponding modified decoding algorithm are described in this paper. Finally,computational complexity analysis and performance simulation are given. Data results indicate that compared with the existing BP decoder,the modified BP decoder can obtain a better bit error performance of about 0. 2 dB at the cost of a little computational complexity.
We describe a novel approach to interpret a polar code as a low-density parity-check (LDPC)-like code with an underlying sparse decoding graph. This sparse graph is based on the encoding factor graph of polar codes and is suitable for conventional belief propagation (BP) decoding. We discuss several pruning techniques based on the check node decoder (CND) and variable node decoder (VND) update equations, significantly reducing the size (i.e., decoding complexity) of the parity-check matrix. As a result, iterative polar decoding can then be conducted on a sparse graph, akin to the traditional well-established LDPC decoding, e.g., using a fully parallel sum-product algorithm (SPA). This facilitates the systematic analysis and design of polar codes using the well-established tools known from analyzing LDPC codes. We show that the proposed iterative polar decoder has a negligible performance loss for short-to-intermediate codelengths compared to Arikan's original BP decoder. Finally, the proposed decoder is shown to benefit from both reduced complexity and reduced memory requirements and, thus, is more suitable for hardware implementations.
The belief propagation algorithm is desirable for a polar code based decoder, because of the potentially low latency and the ability of integration in digital signal processing units or other multi-core processor systems to parallelize the computations. Although belief propagation polar code decoder algorithms have the ability for a highly parallelized imple-mentation, the algorithms require many iterations to achieve a comparable frame error rate and bit error rate with respect to a successive cancellation polar code algorithm. The iterative nature of the belief propagation algorithms also result in a higher computational complexity, i.e. O(IN(2log_{2} N-1)) compared to the computational complexity O(Nlog_{2}N) of the successive cancellation decoder algorithm. In this paper we propose several simplifications for a simplified belief propagation algorithm for polar code decoders, where the arithmetic complexity of the nodes is reduced. The proposed belief propagation algorithm shows preliminary results of a net reduction of the arithmetic complexity of ≈ 13%. This reduction is a result of the reduced number of arithmetic operations, i.e., additions, compares, and multiplications, without a lost in error-correcting performance.
This paper presents a novel belief propagation (BP) based decoding algorithm for polar codes. The proposed algorithm facilitates belief propagation by utilizing the specific constituent codes that exist in the factor graph, which results in an express journey (XJ) for belief information to propagate in each decoding iteration. In addition, this XJ-BP decoder employs a novel round-trip message passing scheduling method for the increased efficiency. The proposed method simplifies min-sum (MS) BP decoder by 40.6%. Along with the round-trip scheduling, the XJ-BP algorithm reduces the computational complexity of MS BP decoding by 90.4%; this enables an energy-efficient hardware implementation of BP decoding in practice.