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 Symposium on Broadband Multimedia Systems and Broadcasting (BMSB)

Polar Decoding with Schedule Diversity Based on LDPC-like Sparse Graphs

Yen‐Ming Chen, Yong-Jan Yang, Bo-Lun Huang, Huang–Chang Lee, Chih–Peng Li

Published Oct 27, 2020• 4 citations
Publisher

Abstract

In this paper, based on the technique of LDPC (low-density parity-check)-like sparse graphs for the Polar codes, we propose a Polar decoding method which provides the schedule diversity. The investigated decoding schedules outperforms Arikan's belief propagation (BP) algorithm performed on the original encoding factor graph. Secondly, based on both the layered BP (LBP) and the modified node-wise residual BP (NW-RBP) schedules, we are able produce several sequential decoding schedules that are executed in serial. It is shown through simulations that when compared to the successive cancellation list (SCL) decoding, the proposed scheme achieves a lower complexity level, while a gap of 0.2 dB still exists in BER performance in the high-SNR region. However, the enhanced BP-based decoding method provides a flexible decoding latency, and is able to generate soft-in/soft-out information, which makes it suitable for the schemes which perform iterative decoding and detection processes.

DOI
10.1109/bmsb49480.2020.9379440

Related papers

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

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

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

A Novel Fast LDPC Decoder Using APP-Based Dynamic Scheduling Scheme

Tian Xia, Hsiao‐Chun Wu, Scott C.-H. Huang

Low-density parity-check (LDPC) codes are favorable in modern telecommunication technologies due to its superior error-correction capability especially when the codeword length is large. The commonly-used LDPC decoders are based on the belief-propagation (BP) algorithms. It is well known that the layered (serial) belief-propagation (LBP) decoding algorithms can reduce the number of iterations by half in comparison with the flooding (parallel) BP decoding algorithms. Further reduction in total number of iterations can be achieved by using the informed dynamic scheduling techniques, such as residual BP (RBP) and node-wise residual BP (NWRBP) methods. However, the incurred additional computation of residuals is far from trivial. In this paper, we propose a novel efficient dynamic scheduling scheme, called a posteriori probability RBP (APPRBP) algorithm, which offers more flexibility to leverage the performance-complexity trade-off using a threshold parameter. The simulation results demonstrate that the average iteration numbers for our proposed APPRBP algorithm can be remarkably reduced especially in the low E_b/N_0 (signal-energy-per-information-bit to noise-power-spectral-density ratio) conditions while the bit-error rate (BER) performance is subject to slight degradation.

Globecom•Dec 1, 2014•0 citations

Improved LDPC-like BPL Decoding Algorithm for Polar Code

Rui Guo, Chenfei Zhang, Chen Lou

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.

KSII Transactions on Internet and Information Systems•Jan 31, 2025•0 citations

A Novel Fast LDPC Decoder Using APP-Based Dynamic Scheduling Scheme

Tian Xia, Hsiao‐Chun Wu, Scott C.-H. Huang

Low-density parity-check (LDPC) codes are favorable in modern telecommunication technologies due to its superior error-correction capability especially when the codeword length is large. The commonly-used LDPC decoders are based on the belief-propagation (BP) algorithms. It is well known that the layered (serial) belief-propagation (LBP) decoding algorithms can reduce the number of iterations by half in comparison with the flooding (parallel) BP decoding algorithms. Further reduction in total number of iterations can be achieved by using the informed dynamic scheduling techniques, such as residual BP (RBP) and node-wise residual BP (NWRBP) methods. However, the incurred additional computation of residuals is far from trivial. In this paper, we propose a novel efficient dynamic scheduling scheme, called a posteriori probability RBP (APPRBP) algorithm, which offers more flexibility to leverage the performance-complexity trade-off using a threshold parameter. The simulation results demonstrate that the average iteration numbers for our proposed APPRBP algorithm can be remarkably reduced especially in the low E_b/N_0 (signal-energy-per-information-bit to noise-power-spectral-density ratio) conditions while the bit-error rate (BER) performance is subject to slight degradation.

Globecom•Dec 1, 2015•3 citations
In this paper, based on the technique of LDPC (low-density parity-check)-like sparse graphs for the Polar codes, we propose a Polar decoding method which provides the schedule diversity. The investigated decoding schedules outperforms Arikan's belief propagation (BP) algorithm performed on the original encoding factor graph. Secondly, based on both the layered BP (LBP) and the modified node-wise residual BP (NW-RBP) schedules, we are able produce several sequential decoding schedules that are executed in serial. It is shown through simulations that when compared to the successive cancellation list (SCL) decoding, the proposed scheme achieves a lower complexity level, while a gap of 0.2 dB still exists in BER performance in the high-SNR region. However, the enhanced BP-based decoding method provides a flexible decoding latency, and is able to generate soft-in/soft-out information, which makes it suitable for the schemes which perform iterative decoding and detection processes.
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.
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.
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.
Low-density parity-check (LDPC) codes are favorable in modern telecommunication technologies due to its superior error-correction capability especially when the codeword length is large. The commonly-used LDPC decoders are based on the belief-propagation (BP) algorithms. It is well known that the layered (serial) belief-propagation (LBP) decoding algorithms can reduce the number of iterations by half in comparison with the flooding (parallel) BP decoding algorithms. Further reduction in total number of iterations can be achieved by using the informed dynamic scheduling techniques, such as residual BP (RBP) and node-wise residual BP (NWRBP) methods. However, the incurred additional computation of residuals is far from trivial. In this paper, we propose a novel efficient dynamic scheduling scheme, called a posteriori probability RBP (APPRBP) algorithm, which offers more flexibility to leverage the performance-complexity trade-off using a threshold parameter. The simulation results demonstrate that the average iteration numbers for our proposed APPRBP algorithm can be remarkably reduced especially in the low E_b/N_0 (signal-energy-per-information-bit to noise-power-spectral-density ratio) conditions while the bit-error rate (BER) performance is subject to slight degradation.
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.
Low-density parity-check (LDPC) codes are favorable in modern telecommunication technologies due to its superior error-correction capability especially when the codeword length is large. The commonly-used LDPC decoders are based on the belief-propagation (BP) algorithms. It is well known that the layered (serial) belief-propagation (LBP) decoding algorithms can reduce the number of iterations by half in comparison with the flooding (parallel) BP decoding algorithms. Further reduction in total number of iterations can be achieved by using the informed dynamic scheduling techniques, such as residual BP (RBP) and node-wise residual BP (NWRBP) methods. However, the incurred additional computation of residuals is far from trivial. In this paper, we propose a novel efficient dynamic scheduling scheme, called a posteriori probability RBP (APPRBP) algorithm, which offers more flexibility to leverage the performance-complexity trade-off using a threshold parameter. The simulation results demonstrate that the average iteration numbers for our proposed APPRBP algorithm can be remarkably reduced especially in the low E_b/N_0 (signal-energy-per-information-bit to noise-power-spectral-density ratio) conditions while the bit-error rate (BER) performance is subject to slight degradation.