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

Electronics Letters

Improved BP decoder for polar codes based on a modified kernel matrix

Jin Sha, Jingbo Liu, Zhongfeng Wang

Published Oct 25, 2016• 6 citations
Publisher

Abstract

Since the polar code was discovered by Arikan, many decoding methods have been proposed, one of which is the belief propagation (BP) decoding. Its inherent high parallel level makes it suitable for high‐speed applications. A novel BP decoder based on a modified three‐by‐three kernel matrix is proposed. The corresponding decoding algorithm and frozen bits selection method are presented. The numerical results show that it has a similar error correcting capability compared with the original polar BP decoder. More importantly, the message memory requirement can be reduced from O ( N log 2 N ) to O ( N log 3 N ), and the decoding delay can be reduced accordingly.

DOI
10.1049/el.2016.1878

Related papers

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

Higher-Order Belief Propagation Correction Decoder for Polar Codes

Meng Zhang, Zhuo Li, Lijuan Xing +1 more

Belief propagation (BP) decoding for polar codes has been extensively studied because of its inherent parallelism. However, its performance remains inferior to that of successive cancellation list decoding (SCL) due to the structure of the decoding graph. To improve the block error rate (BLER) performance, the BP correction (BPC) decoding, a post-processing scheme that corrects prior knowledge of the identified code bit, improves convergence by executing additional iterations on the failed BP decoder. Moreover, the BPC decoder demonstrates a better decoding performance than the BP-based bit-flipping decoder. Nevertheless, the additional decoding attempts lead to increased latency. In this article, a modified BPC decoder is proposed to reduce the number of decoding attempts by redefining the correction rules. A new metric is designed to effectively identify the corrected location. Numerical results show that the proposed modified BPC decoder achieves a slight improvement in BLER compared with the original BPC, with a dramatic reduction in average complexity. Furthermore, a higher-order version, named MBPC-Ω, is extended to further improve the performance, where the Ω is the maximum correction order. Numerical results show that the higher-order modified BPC achieves a similar BLER performance to existing multiple bit-flipping BP decoders but has around half the latency overhead. In addition, the proposed MBPC-2 decoder performs better than the cyclic redundancy check-aided SCL (CA-SCL) decoder with list size 4 and is slightly worse than the CA-SCL with list size 8 in high signal-to-noise ratio (SNR) regions but with significant decoding latency reduction.

Entropy•Apr 11, 2022•2 citations

A simplified belief propagation decoder for polar codes

Yingxian Zhang, Qingshuang Zhang, Xiaofei Pan +2 more

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.

IEEE International Wireless Symposium•Mar 1, 2014•26 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

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

A Modified BP Bit-Flipping Algorithm for Polar Codes

Lijuan Li, Hangxuan Cui, Yangcan Zhou +1 more

The belief propagation (BP) algorithm for polar codes has attracted significant attention due to its soft-output property and high parallelism. However, the BP algorithm is not comparable with the successive cancellation list (SCL) algorithm in terms of the error-correction performance. In this paper, we propose a high-stage BP flip (HSBPF) algorithm to further improve the error-correction performance of the BP algorithm by analyzing the distribution of log-likelihood ratio (LLR) values. Simulation results show that the decoding latency can be reduced by 30% with the proposed algorithm. Moreover, benefiting from the simplified message passing of the factor graph, the computational complexity of the proposed algorithm is also significantly reduced compared with the existing algorithms.

SiPS ... design and implementation - IEEE Workshop on Signal Processing Systems•Nov 2, 2022•1 citation
Since the polar code was discovered by Arikan, many decoding methods have been proposed, one of which is the belief propagation (BP) decoding. Its inherent high parallel level makes it suitable for high‐speed applications. A novel BP decoder based on a modified three‐by‐three kernel matrix is proposed. The corresponding decoding algorithm and frozen bits selection method are presented. The numerical results show that it has a similar error correcting capability compared with the original polar BP decoder. More importantly, the message memory requirement can be reduced from O ( N log 2 N ) to O ( N log 3 N ), and the decoding delay can be reduced accordingly.
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.
Belief propagation (BP) decoding for polar codes has been extensively studied because of its inherent parallelism. However, its performance remains inferior to that of successive cancellation list decoding (SCL) due to the structure of the decoding graph. To improve the block error rate (BLER) performance, the BP correction (BPC) decoding, a post-processing scheme that corrects prior knowledge of the identified code bit, improves convergence by executing additional iterations on the failed BP decoder. Moreover, the BPC decoder demonstrates a better decoding performance than the BP-based bit-flipping decoder. Nevertheless, the additional decoding attempts lead to increased latency. In this article, a modified BPC decoder is proposed to reduce the number of decoding attempts by redefining the correction rules. A new metric is designed to effectively identify the corrected location. Numerical results show that the proposed modified BPC decoder achieves a slight improvement in BLER compared with the original BPC, with a dramatic reduction in average complexity. Furthermore, a higher-order version, named MBPC-Ω, is extended to further improve the performance, where the Ω is the maximum correction order. Numerical results show that the higher-order modified BPC achieves a similar BLER performance to existing multiple bit-flipping BP decoders but has around half the latency overhead. In addition, the proposed MBPC-2 decoder performs better than the cyclic redundancy check-aided SCL (CA-SCL) decoder with list size 4 and is slightly worse than the CA-SCL with list size 8 in high signal-to-noise ratio (SNR) regions but with significant decoding latency reduction.
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.
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).
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.
The belief propagation (BP) algorithm for polar codes has attracted significant attention due to its soft-output property and high parallelism. However, the BP algorithm is not comparable with the successive cancellation list (SCL) algorithm in terms of the error-correction performance. In this paper, we propose a high-stage BP flip (HSBPF) algorithm to further improve the error-correction performance of the BP algorithm by analyzing the distribution of log-likelihood ratio (LLR) values. Simulation results show that the decoding latency can be reduced by 30% with the proposed algorithm. Moreover, benefiting from the simplified message passing of the factor graph, the computational complexity of the proposed algorithm is also significantly reduced compared with the existing algorithms.