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

KSII Transactions on Internet and Information Systems

Improved LDPC-like BPL Decoding Algorithm for Polar Code

Rui Guo, Chenfei Zhang, Chen Lou

Published Jan 31, 2025• 0 citations
Publisher

Abstract

To improve the performance of BP decoding for polar codes, researchers have developed a Belief Propagation List (BPL) decoding algorithm by executing multiple BP decoders in parallel.This algorithm outperforms traditional BP decoding based on single graph decoding, although it sacrifices some complexity and delay.Unlike this basic Polar-BPL decoding mentioned above, a low-density parity check like (LDPC-like) BPL decoding algorithm has been introduced into polar codes.This algorithm performs more efficient BP decoding iterations on sparse graphs.To further reduce the complexity and delay of LDPC-like BPL, and avoid analyzing all sparse graphs, this article proposes an improved LDPC-like BPL (ILDPC-like BPL) decoding algorithm based on selecting factor graphs.This algorithm analyzes differences in permuted factor graphs and selects these graphs with non-convergent decoding results to form a decoding list, allowing decoding to be completed with fewer graphs traversed and iterations, thereby reducing complexity and delay.On this basis, to improve the reliability of this algorithm, this article further adds a path metric (PM) mechanism, which can dynamically evaluate different sparse graphs' results in parallel decoding.The simulation results show that compared with LDPC-like BPL (random scheme), ILDPC-like BPL improves decoding performance while reducing decoding delay and complexity; Compared with basic Polar-BPL (cycle-shift scheme), this algorithm greatly reduces decoding delay and complexity while achieving similar performance.

DOI
10.3837/tiis.2025.01.013

Related papers

BP-Based Sparse Graph List Decoding of Polar Codes

Han Liu, Erry Gunawan, Yaoyue Hu +1 more

How to construct an effective polar decoding scheme has attracted researchers in the field of communication. The belief propagation list (BPL) decoder has performance improvement over the traditional BP decoder but comes with much higher complexity. To solve the issue of high complexity & latency, a low-density parity-check (LDPC) like BP decoder was proposed but it suffered from performance degradation over the original BP decoder. In this letter, a BP-based sparse graph list (BP-SGL) decoder is proposed by leveraging both list decoding scheme and LDPC-like BP decoding algorithm to achieve performance improvement while maintaining low complexity & latency. The key idea of the proposed list generation method is the similarity comparison of decoding graphs. Testing results verify that selecting graphs with large structural differences helps to construct a list with good overall performance. Simulation results show that the proposed scheme is superior to LDPC-like BP, and even outperforms the original BPL and some state-of-the-art (SOTA) BP-based decoding algorithms with significant reduction in complexity & latency.

IEEE Communications Letters•Mar 14, 2023•8 citations

Improved Belief Propagation List Decoding for Polar Codes

Binghao Li, Baoming Bai, Min Zhu +1 more

In this paper, we present an improved belief propagation list (BPL) decoding algorithm for polar codes. Rather than getting L factor graphs (FGs) at random and cyclic shift permutation, we use the upper bounds on the block error propability of polar codes with different FGs as the metric to choose the best L FGs. By observing the bounds of different FGs, we propose a heuristic method to reduce search complexity. Simulation results show that there is only a gap of 0.2 dB between the frame error rate (FER) performance of the improved BPL decoder using RM16-GA construction and that of length-1024 5G polar code decoded by SCL with the same list size of 32 at FER =10-4. Moreover, with the proposed FG selection method, BPL decoding can reduce clock cycles by 97.74% compared with the SCL decoding.

IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2020•10 citations

CRC-Aided Belief Propagation with Permutated Graphs Decoding of Polar Codes

Liyun Dai, Li Huang, Yaohui Bai +2 more

It has been shown that the permutation factor graph is an effective method to improve the performance of belief propagation (BP) decoding. The research of belief propagation list (BPL) algorithm based on permutation factor graph has also made great progress, but the complexity of decoding process is still too high. In order to compromise performance and complexity, in this work, we focus on the iterative convergence of BPL decoding algorithm, and propose an early termination BPL algorithm based on multiple CRCs. The results show that the improved BPL decoding scheme can provide higher throughput and achieve similar decoding performance with the existing BPL decoding under the same simulation condition.

IEEE International Conference on Electronic Information and Communication Technology (ICEICT)•Nov 13, 2020•4 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

Improved Belief Propagation List Decoding for Polar Codes

Huan Li, Jingxuan Huang, Ce Sun

Polar codes have become the channel coding scheme for control channel of enhanced mobile broadband in the 5G communication systems. Belief propagation (BP) decoding of polar codes has advantages of low decoding latency and high parallelism but achieves worse bit error ratio (BER) performance compared with the successive cancellation list (SCL) decoding scheme. In this paper, an improved BP list (IBPL) decoding algorithm is proposed with comparable BER performance to SCL algoritm. Firstly, the optimal permuted factor graph is analyzed for polar codes, which improves the performance of the BP decoder without path extension. Furthermore, based on the optimal graph, the bit metric and decoding path metric are proposed to extend and prune the decoding path. The proposed IBPL decoder is focused on not only the permutation of polar codes but also the reliabilities of decoded codewords during each iteration of BP decoding, which has a more accurate decoding path list. The simulation results show that the proposed IBPL decoder improves the BER performance compared with the original BP decoder significantly, and can approach the performance of the SCL decoder at low signal to noise ratio regions.

Electronics•Aug 7, 2022•7 citations

Belief Propagation-Based Polar Decoders With Schedule Diversity

C S You, Yi‐Hsin Chen, Chen-Wei Hu +2 more

Based on pruning techniques that interpret polar codes as low-density parity-check-like (LDPC-like) codes, this paper develops novel belief propagation (BP)-based decoders utilizing the concept of schedule diversity. By analyzing the impact of hidden variable nodes (VNHs), scheduling algorithms that guarantee fast convergence speeds and superior error performance are devised for the LDPC-like sparse factor graph (SPF), incorporating both standard sequential scheduling (SSS) and informed dynamic scheduling (IDS) algorithms. To further enhance error performance, cyclic redundancy check (CRC) bits are integrated into the LDPC-like SPF, and random update sequences are introduced to reduce computational complexity while implementing schedule diversity. Inspired by belief propagation list decoding, the proposed approaches eventually update messages in the LDPC-like SPF according to various schedules, thereby producing diverse decoding outcomes. Compared to the CRC-aided successive cancellation list (CA-SCL) decoder and benchmark soft-output decoders in the literature, the proposed schemes achieve comparable or improved error performance while reducing computational complexity in the high SNR region. These results serve as preliminary findings on the BP algorithm over LDPC-like SFGs and provide useful insights for the design and practical improvement of polar decoders.

IEEE Transactions on Communications•Dec 15, 2025•1 citation
To improve the performance of BP decoding for polar codes, researchers have developed a Belief Propagation List (BPL) decoding algorithm by executing multiple BP decoders in parallel.This algorithm outperforms traditional BP decoding based on single graph decoding, although it sacrifices some complexity and delay.Unlike this basic Polar-BPL decoding mentioned above, a low-density parity check like (LDPC-like) BPL decoding algorithm has been introduced into polar codes.This algorithm performs more efficient BP decoding iterations on sparse graphs.To further reduce the complexity and delay of LDPC-like BPL, and avoid analyzing all sparse graphs, this article proposes an improved LDPC-like BPL (ILDPC-like BPL) decoding algorithm based on selecting factor graphs.This algorithm analyzes differences in permuted factor graphs and selects these graphs with non-convergent decoding results to form a decoding list, allowing decoding to be completed with fewer graphs traversed and iterations, thereby reducing complexity and delay.On this basis, to improve the reliability of this algorithm, this article further adds a path metric (PM) mechanism, which can dynamically evaluate different sparse graphs' results in parallel decoding.The simulation results show that compared with LDPC-like BPL (random scheme), ILDPC-like BPL improves decoding performance while reducing decoding delay and complexity; Compared with basic Polar-BPL (cycle-shift scheme), this algorithm greatly reduces decoding delay and complexity while achieving similar performance.
How to construct an effective polar decoding scheme has attracted researchers in the field of communication. The belief propagation list (BPL) decoder has performance improvement over the traditional BP decoder but comes with much higher complexity. To solve the issue of high complexity & latency, a low-density parity-check (LDPC) like BP decoder was proposed but it suffered from performance degradation over the original BP decoder. In this letter, a BP-based sparse graph list (BP-SGL) decoder is proposed by leveraging both list decoding scheme and LDPC-like BP decoding algorithm to achieve performance improvement while maintaining low complexity & latency. The key idea of the proposed list generation method is the similarity comparison of decoding graphs. Testing results verify that selecting graphs with large structural differences helps to construct a list with good overall performance. Simulation results show that the proposed scheme is superior to LDPC-like BP, and even outperforms the original BPL and some state-of-the-art (SOTA) BP-based decoding algorithms with significant reduction in complexity & latency.
In this paper, we present an improved belief propagation list (BPL) decoding algorithm for polar codes. Rather than getting L factor graphs (FGs) at random and cyclic shift permutation, we use the upper bounds on the block error propability of polar codes with different FGs as the metric to choose the best L FGs. By observing the bounds of different FGs, we propose a heuristic method to reduce search complexity. Simulation results show that there is only a gap of 0.2 dB between the frame error rate (FER) performance of the improved BPL decoder using RM16-GA construction and that of length-1024 5G polar code decoded by SCL with the same list size of 32 at FER =10-4. Moreover, with the proposed FG selection method, BPL decoding can reduce clock cycles by 97.74% compared with the SCL decoding.
It has been shown that the permutation factor graph is an effective method to improve the performance of belief propagation (BP) decoding. The research of belief propagation list (BPL) algorithm based on permutation factor graph has also made great progress, but the complexity of decoding process is still too high. In order to compromise performance and complexity, in this work, we focus on the iterative convergence of BPL decoding algorithm, and propose an early termination BPL algorithm based on multiple CRCs. The results show that the improved BPL decoding scheme can provide higher throughput and achieve similar decoding performance with the existing BPL decoding under the same simulation condition.
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.
Polar codes have become the channel coding scheme for control channel of enhanced mobile broadband in the 5G communication systems. Belief propagation (BP) decoding of polar codes has advantages of low decoding latency and high parallelism but achieves worse bit error ratio (BER) performance compared with the successive cancellation list (SCL) decoding scheme. In this paper, an improved BP list (IBPL) decoding algorithm is proposed with comparable BER performance to SCL algoritm. Firstly, the optimal permuted factor graph is analyzed for polar codes, which improves the performance of the BP decoder without path extension. Furthermore, based on the optimal graph, the bit metric and decoding path metric are proposed to extend and prune the decoding path. The proposed IBPL decoder is focused on not only the permutation of polar codes but also the reliabilities of decoded codewords during each iteration of BP decoding, which has a more accurate decoding path list. The simulation results show that the proposed IBPL decoder improves the BER performance compared with the original BP decoder significantly, and can approach the performance of the SCL decoder at low signal to noise ratio regions.
Based on pruning techniques that interpret polar codes as low-density parity-check-like (LDPC-like) codes, this paper develops novel belief propagation (BP)-based decoders utilizing the concept of schedule diversity. By analyzing the impact of hidden variable nodes (VNHs), scheduling algorithms that guarantee fast convergence speeds and superior error performance are devised for the LDPC-like sparse factor graph (SPF), incorporating both standard sequential scheduling (SSS) and informed dynamic scheduling (IDS) algorithms. To further enhance error performance, cyclic redundancy check (CRC) bits are integrated into the LDPC-like SPF, and random update sequences are introduced to reduce computational complexity while implementing schedule diversity. Inspired by belief propagation list decoding, the proposed approaches eventually update messages in the LDPC-like SPF according to various schedules, thereby producing diverse decoding outcomes. Compared to the CRC-aided successive cancellation list (CA-SCL) decoder and benchmark soft-output decoders in the literature, the proposed schemes achieve comparable or improved error performance while reducing computational complexity in the high SNR region. These results serve as preliminary findings on the BP algorithm over LDPC-like SFGs and provide useful insights for the design and practical improvement of polar decoders.