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

Enhanced Loop-weakened Belief Propagation Algorithm for Performance Enhanced Polar Code Decoders

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

Published Feb 3, 2022• 0 citations
OpenAlex

Abstract

A polar code decoder based on the belief propagation algorithm is desirable because of the potentially low latency and its suitability for parallel execution on multicore and SIMD processors. However, current state-of-the-art algorithms require many iterations to achieve comparable bit and frame error rate compared to successive cancellation algorithms. Also, the current state-of-the-art belief propagation algorithms have a high computational complexity compared to successive cancellation. In this paper we present an enhanced belief propagation algorithm, in which parts of the computations are altered to reduce the negative effect of the short cycles in the polar code factor graph. Our proposed algorithm has a gain of approx+0.4mathbf{dB} in both frame and bit error rate compared to successive cancellation and a gain of approx+0.16mathbf{dB} and approx+0.13mathbf{dB} at a frame and bit error rate of 10-3 respectively, compared to belief propagation. Also, the maximum number of iterations of our algorithm is reduce to 0.6cdot I_{max}. As a result, the latency is up to approx 11 times lower compared to successive cancellation and up to approx 1.8 times lower compared to the current state-of-the-art belief propagation polar code algorithm. Furthermore, the reduction in the maximum iteration count results in a lower power consumption after implementation.

Related papers

Software Implementation and Performance of a Computational Complexity Reduced Belief Propagation Polar Code Decoder

Arvid B. van den Brink, Oğuz Meteer, Marco J.G. Bekooij

The belief propagation algorithm is one of the preferred algorithms for a polar code based decoder that can potentially achieve the lowest latency. Although belief propagation polar code algorithms have the ability for a highly parallelized implementation, they require more iterations to achieve a comparable frame error rate and bit error rate compared to the successive cancellation polar code algorithm. The iterative nature of the belief propagation algorithms also results in a higher computational complexity, i.e. O(N(2log2N-1)) compared to the computational complexity O(Nlog2N) of the successive cancellation decoder algorithm. In this paper we propose several software implementations of belief propagation polar code decoders using the computational complexity reduced belief propagation algorithm and the enhanced loop-weakened belief propagation algorithm, to increase the number of decoded codes per second. Compared to a baseline belief propagation implementation, our proposed radix-2 and radix-4 implementations increase the throughput by approximately 15.4% and 22.04% respectively. This gain is the result of a reduction of arithmetic operations, i.e., additions, compares, and multiplications, which is obtained without a loss in error-correcting performance.

International Conference on Electrical, Computer, Communications and Mechatronics Engineering (ICECCME)•Jul 19, 2023•0 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

Belief Propagation List Decoding of Polar Codes

Ahmed Elkelesh, Moustafa Ebada, Sebastian Cammerer +1 more

We propose a belief propagation list (BPL) decoder with comparable performance to the successive cancellation list (SCL) decoder of polar codes, which already achieves the maximum likelihood (ML) bound of polar codes for sufficiently large list size L. The proposed decoder is composed of multiple parallel independent belief propagation (BP) decoders based on differently permuted polar code factor graphs. A list of possible transmitted codewords is generated and the one closest to the received vector, in terms of Euclidean distance, is picked. To the best of our knowledge, the proposed BPL decoder provides the best performance of plain polar codes under iterative decoding known so far. The proposed algorithm does not require any changes in the polar code structure itself, rendering the BPL into an alternative to the SCL decoder, equipped with a soft output capability enabling, e.g., iterative detection and decoding to further improve performance. Further benefits are the lower decoding latency than the SCL decoder and the possibility of high throughput implementations. Additionally, we show that a different selection strategy of frozen bit positions can further enhance the error-rate performance of the proposed decoder.

arXiv:1806.10503•IEEE Communications Letters•Jun 26, 2018•161 citations

An Enhanced Belief Propagation Decoder for Polar Codes

Meng Zhang, Zhuo Li, Lijuan Xing

Belief propagation (BP) has attracted increasing attention due to its high parallelism. In this letter, a correction method is proposed to improve the block error rate (BLER) performance of the BP decoder for polar codes so that it is comparable to that of the successive cancellation list (SCL) decoder. Compared with BP flipping (BPF) decoding, the proposed decoder focuses on prior knowledge of the code bits in the factor graph. Two strategies have been proposed to construct the correction set. The simulation results show that the BPC decoder exhibits a BLER similar to that of BPF decoder while reducing the average latency and complexity by half. In addition, the BLER of the BPC decoder can approach that of the cyclic redundancy check (CRC)-aided SCL (CA-SCL) decoder in regions with low and medium signal-to-noise ratios (SNRs).

IEEE Communications Letters•Aug 11, 2021•16 citations

Enhancing Belief Propagation Decoding of Polar Codes: A Reinforcement Learning Approach

Mohsen Moradi, Salman Habib, David G. M. Mitchell

Short block-length polar-like codes showcase exceptional error correction performance (ECP) using sequential decoding or successive cancellation list decoding with a large list size. However, achieving a high level of reliability with these methods involves high-latency decoding. To meet the growing demand for low-latency communication with acceptable complexity, belief propagation (BP) decoding emerges as an attractive option, although its ECP is known to fall short of those high-latency alternatives. In this paper, we propose an enhanced BP decoding approach for polar codes, leveraging reinforcement learning (RL) to optimize the message-passing schedule. Moreover, we investigate the design of the polar code rate profile and corresponding Tanner graph representation to enhance the benefits of RL. Numerical results demonstrate a performance gain of more than 1 dB for polar codes with a length of 128 and a rate of 0.5 compared to conventional BP decoding alone at highEb/N0values, demonstrating the promise of the proposed approach.

IEEE Communications Letters•Apr 9, 2025•3 citations

Partially Permuted Multi-Trellis Belief Propagation for Polar Codes

Vismika Ranasinghe, Nandana Rajatheva, Matti Latva‐aho

Belief propagation (BP) is an iterative decoding algorithm for polar codes which can be parallelized effectively to achieve higher throughput. However, because of the presence of error floor due to cycles and stopping sets in the factor graph, the performance of the BP decoder is far from the performance of state of the art cyclic redundancy check (CRC) aided successive cancellation list (CA-SCL) decoders. It has been shown that successive BP decoding on multiple permuted factor graphs, which is called the multi-trellis BP decoder, can improve the error performance. However, when permuting the entire factor graph, since the decoder dismisses the information from the previous permutation, the number of iterations required is significantly larger than that of the standard BP decoder. In this work, we propose a new variant of the multi-trellis BP decoder which permutes only a subgraph of the original factor graph. This enables the decoder to retain information of variable nodes in the subgraphs, which are not permuted, reducing the required number of iterations needed in-between the permutations. As a result, the proposed decoder can perform permutations more frequently, hence being more effective in mitigating the effect of cycles which cause oscillation errors. Experimental results show that for a polar code with block length 1024 and rate 0.5 the error performance gain of the proposed decoder at the frame error rate of $10^{-6}$ is 0.25 dB compared to multi-trellis decoder based on full permutations. This performance gain is achieved along with reduced latency in terms of the number of iterations.

arXiv:1911.08868•International Conference on Communications•Jun 1, 2020•3 citations
A polar code decoder based on the belief propagation algorithm is desirable because of the potentially low latency and its suitability for parallel execution on multicore and SIMD processors. However, current state-of-the-art algorithms require many iterations to achieve comparable bit and frame error rate compared to successive cancellation algorithms. Also, the current state-of-the-art belief propagation algorithms have a high computational complexity compared to successive cancellation. In this paper we present an enhanced belief propagation algorithm, in which parts of the computations are altered to reduce the negative effect of the short cycles in the polar code factor graph. Our proposed algorithm has a gain of approx+0.4mathbf{dB} in both frame and bit error rate compared to successive cancellation and a gain of approx+0.16mathbf{dB} and approx+0.13mathbf{dB} at a frame and bit error rate of 10-3 respectively, compared to belief propagation. Also, the maximum number of iterations of our algorithm is reduce to 0.6cdot I_{max}. As a result, the latency is up to approx 11 times lower compared to successive cancellation and up to approx 1.8 times lower compared to the current state-of-the-art belief propagation polar code algorithm. Furthermore, the reduction in the maximum iteration count results in a lower power consumption after implementation.
The belief propagation algorithm is one of the preferred algorithms for a polar code based decoder that can potentially achieve the lowest latency. Although belief propagation polar code algorithms have the ability for a highly parallelized implementation, they require more iterations to achieve a comparable frame error rate and bit error rate compared to the successive cancellation polar code algorithm. The iterative nature of the belief propagation algorithms also results in a higher computational complexity, i.e. O(N(2log2N-1)) compared to the computational complexity O(Nlog2N) of the successive cancellation decoder algorithm. In this paper we propose several software implementations of belief propagation polar code decoders using the computational complexity reduced belief propagation algorithm and the enhanced loop-weakened belief propagation algorithm, to increase the number of decoded codes per second. Compared to a baseline belief propagation implementation, our proposed radix-2 and radix-4 implementations increase the throughput by approximately 15.4% and 22.04% respectively. This gain is the result of a reduction of arithmetic operations, i.e., additions, compares, and multiplications, which is obtained without a loss in error-correcting performance.
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.
We propose a belief propagation list (BPL) decoder with comparable performance to the successive cancellation list (SCL) decoder of polar codes, which already achieves the maximum likelihood (ML) bound of polar codes for sufficiently large list size L. The proposed decoder is composed of multiple parallel independent belief propagation (BP) decoders based on differently permuted polar code factor graphs. A list of possible transmitted codewords is generated and the one closest to the received vector, in terms of Euclidean distance, is picked. To the best of our knowledge, the proposed BPL decoder provides the best performance of plain polar codes under iterative decoding known so far. The proposed algorithm does not require any changes in the polar code structure itself, rendering the BPL into an alternative to the SCL decoder, equipped with a soft output capability enabling, e.g., iterative detection and decoding to further improve performance. Further benefits are the lower decoding latency than the SCL decoder and the possibility of high throughput implementations. Additionally, we show that a different selection strategy of frozen bit positions can further enhance the error-rate performance of the proposed decoder.
Belief propagation (BP) has attracted increasing attention due to its high parallelism. In this letter, a correction method is proposed to improve the block error rate (BLER) performance of the BP decoder for polar codes so that it is comparable to that of the successive cancellation list (SCL) decoder. Compared with BP flipping (BPF) decoding, the proposed decoder focuses on prior knowledge of the code bits in the factor graph. Two strategies have been proposed to construct the correction set. The simulation results show that the BPC decoder exhibits a BLER similar to that of BPF decoder while reducing the average latency and complexity by half. In addition, the BLER of the BPC decoder can approach that of the cyclic redundancy check (CRC)-aided SCL (CA-SCL) decoder in regions with low and medium signal-to-noise ratios (SNRs).
Short block-length polar-like codes showcase exceptional error correction performance (ECP) using sequential decoding or successive cancellation list decoding with a large list size. However, achieving a high level of reliability with these methods involves high-latency decoding. To meet the growing demand for low-latency communication with acceptable complexity, belief propagation (BP) decoding emerges as an attractive option, although its ECP is known to fall short of those high-latency alternatives. In this paper, we propose an enhanced BP decoding approach for polar codes, leveraging reinforcement learning (RL) to optimize the message-passing schedule. Moreover, we investigate the design of the polar code rate profile and corresponding Tanner graph representation to enhance the benefits of RL. Numerical results demonstrate a performance gain of more than 1 dB for polar codes with a length of 128 and a rate of 0.5 compared to conventional BP decoding alone at highEb/N0values, demonstrating the promise of the proposed approach.
Belief propagation (BP) is an iterative decoding algorithm for polar codes which can be parallelized effectively to achieve higher throughput. However, because of the presence of error floor due to cycles and stopping sets in the factor graph, the performance of the BP decoder is far from the performance of state of the art cyclic redundancy check (CRC) aided successive cancellation list (CA-SCL) decoders. It has been shown that successive BP decoding on multiple permuted factor graphs, which is called the multi-trellis BP decoder, can improve the error performance. However, when permuting the entire factor graph, since the decoder dismisses the information from the previous permutation, the number of iterations required is significantly larger than that of the standard BP decoder. In this work, we propose a new variant of the multi-trellis BP decoder which permutes only a subgraph of the original factor graph. This enables the decoder to retain information of variable nodes in the subgraphs, which are not permuted, reducing the required number of iterations needed in-between the permutations. As a result, the proposed decoder can perform permutations more frequently, hence being more effective in mitigating the effect of cycles which cause oscillation errors. Experimental results show that for a polar code with block length 1024 and rate 0.5 the error performance gain of the proposed decoder at the frame error rate of 10−610^{-6}10−6 is 0.25 dB compared to multi-trellis decoder based on full permutations. This performance gain is achieved along with reduced latency in terms of the number of iterations.