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

Wireless and Optical Communications Conference

Early termination belief propagation decoder with parity check matrix for polar codes

Hsin−Fu Yu, Huang–Chang Lee, Shih-Kai Lee

Published Apr 1, 2018• 5 citations
Publisher

Abstract

In this paper, a belief propagation (BP) decoding algorithm with early termination is proposed for polar code. The early termination is accomplished using the syndrome generated by the parity-check matrix, which can be transferred from the generator matrix. With the assistance of the early termination, the BP decoder can provide not only a better bit error rate performance but also significantly reduce the decoding complexity. For (1024, 512) polar codes, the average numbers of iterations can be reduced from 80 to 23 when Eb/N0=3 dB. The reduction in the computation complexity is about 70%.

DOI
10.1109/wocc.2018.8372719

Related papers

Parity-check and G-matrix based intelligent early stopping criterion for belief propagation decoder for polar codes

Qasim Jan, Shahid Hussain, Zhiwen Pan +4 more

The error correction performance of Belief Propagation (BP) decoding for polar codes is satisfactory compared with the Successive Cancellation (SC) decoding. Nevertheless, it has to complete a fixed number of iterations, which results in high computational complexity. This necessitates an intelligent identification of successful BP decoding for early termination of the decoding process to avoid unnecessary iterations and minimize the computational complexity of BP decoding. This paper proposes a hybrid technique that combines the “parity-check” with the “G-matrix” to reduce the computational complexity of BP decoder for polar codes. The proposed hybrid technique takes advantage of the parity-check to intelligently identify the valid codeword at an early stage and terminate the BP decoding process, which minimizes the overhead of the G-matrix and reduces the computational complexity of BP decoding. We explore a detailed mechanism incorporating the parity bits as outer code and prove that the proposed hybrid technique minimizes the computational complexity while preserving the BP error correction performance. Moreover, mathematical formulation for the proposed hybrid technique that minimizes the computation cost of the G-matrix is elaborated. The performance of the proposed hybrid technique is validated by comparing it with the state-of-the-art early stopping criteria for BP decoding. Simulation results show that the proposed hybrid technique reduces the iterations by about 90% of BP decoding in a high Signal-to-Noise Ratio (SNR) (i.e., 3.5 ∼ 4 ​dB), and approaches the error correction performance of G-matrix and conventional BP decoder for polar codes.

Digital Communications and Networks•Dec 15, 2022•1 citation

BP Polar Decoders with Early Termination and Belief Enhancing

Chao Yang, Junmei Yang, Xiao Liang +3 more

In this paper an early termination scheme, partial LLR-aided (PLA) scheme, is proposed for belief propagation (BP) polar decoding with lower complexity and higher throughput. Numerical results of (1024, 512) code show at least 82% iteration reduction than conventional design at SNR =3.5 dB with proposed early termination scheme. In this paper, belief enhancing schemes based on threshold and cyclic redundancy check (CRC) are proposed, namely, threshold-based LLR (TB-LLR) scheme and segment-divided CRC (SD-CRC) scheme. For (1024, 512) polar code, the performance gains for TB-LLR and SD-CRC are 0.35 dB and 0.2 dB respectively, when BER = 10-3. A general hardware architecture for proposed BP polar decoders is also proposed.

IEEE International Conference on Digital Signal Processing (DSP)•Nov 1, 2018•5 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

Bipartite Belief Propagation Polar Decoding With Bit-Flipping

Zihao Gong, Yifei Shen, Houren Ji +4 more

For the scenarios with high throughput requirements, the belief propagation (BP) decoding is one of the most promising decoding strategies for polar codes. By pruning the redundant variable nodes (VNs) and check nodes (CNs) in the original factor graph, the graph is condensed to a sparse bipartite graph which is similar to the graph for low-density parity-check (LDPC) codes. In this paper, we introduce the bit-flipping scheme into the LDPC-like BP (L-BP) decoding and propose two methods to identify the error-prone VNs. By additional decoding attempts, the L-BP flip (L-BPF) decoding improves the error-rate performance with a similar average complexity for high Eb=N0values. The simulation results show that the L-BPF decoding achieves 0:25 dB gain compared with the L-BP decoding.

IEEE International Conference on Acoustics Speech and Signal Processing•Apr 9, 2020•4 citations

Iterative Decoding Based on Concatenated Belief Propagation for CRC-Aided Polar Codes

Satoshi Tajima, Takumi Takahashi, Shinsuke Ibi +1 more

This paper proposes a novel iterative decoder based on concatenated belief propagation (BP) for CRC-aided polar codes. Compared to the conventional BP-based decoders for polar codes, soft cancellation (SCAN) decoder can generate a log likelihood ratio (LLR) of coded bit with lower computational complexity without sacrificing the detection capability. Unfortunately, its performance is not as good as that of CRC-aided successive cancellation list decoder (SCLD) although SCAN decoder has advantage of hardware implementation. To compensate the performance gap, we exploit CRC structure for not only error detection but also error correction with the assistance of its error correction capability at a short code length by exchanging LLRs between SCAN decoder and BP decoder on the basis of CRC. Moreover, the sub-optimal criterion for selecting a parity check matrix of CRC for BP decoder is proposed. Finally, computer simulations are conducted to confirm the validity of our proposed method. The proposed method can obtain the gain of about 0.6 dB at BER=10-3compared to the native SCAN decoder without requiring huge memory size as in SCLD.

Asia-Pacific Signal and Information Processing Association Annual Summit and Conference (APSIPA ASC)•Nov 1, 2018•7 citations

An Enhanced Belief Propagation Flipping Decoder for Polar Codes with Stepping Strategy

Xiaojun Zhang, Yimeng Liu, Chengguan Chen +2 more

The Belief Propagation (BP) algorithm has the advantages of high-speed decoding and low latency. To improve the block error rate (BLER) performance of the BP-based algorithm, the BP flipping algorithm was proposed. However, the BP flipping algorithm attempts numerous useless flippings for improving the BLER performance. To reduce the number of decoding attempts needed without any loss of BLER performance, in this paper a metric is presented to evaluate the likelihood that the bits would correct the BP flipping decoding. Based on this, a BP-Step-Flipping (BPSF) algorithm is proposed which only traces the unreliable bits in the flip set (FS) to flip and skips over the reliable ones. In addition, a threshold β is applied when the magnitude of the log–likelihood ratio (LLR) is small, and an enhanced BPSF (EBPSF) algorithm is presented to lower the BLER. With the same FS, the proposed algorithm can reduce the average number of iterations efficiently. Numerical results show the average number of iterations for EBPSF-1 decreases by 77.5% when N = 256, compared with the BP bit-flip-1 (BPF-1) algorithm at Eb/N0 = 1.5 dB.

Entropy•Aug 3, 2022•1 citation
In this paper, a belief propagation (BP) decoding algorithm with early termination is proposed for polar code. The early termination is accomplished using the syndrome generated by the parity-check matrix, which can be transferred from the generator matrix. With the assistance of the early termination, the BP decoder can provide not only a better bit error rate performance but also significantly reduce the decoding complexity. For (1024, 512) polar codes, the average numbers of iterations can be reduced from 80 to 23 when Eb/N0=3 dB. The reduction in the computation complexity is about 70%.
The error correction performance of Belief Propagation (BP) decoding for polar codes is satisfactory compared with the Successive Cancellation (SC) decoding. Nevertheless, it has to complete a fixed number of iterations, which results in high computational complexity. This necessitates an intelligent identification of successful BP decoding for early termination of the decoding process to avoid unnecessary iterations and minimize the computational complexity of BP decoding. This paper proposes a hybrid technique that combines the “parity-check” with the “G-matrix” to reduce the computational complexity of BP decoder for polar codes. The proposed hybrid technique takes advantage of the parity-check to intelligently identify the valid codeword at an early stage and terminate the BP decoding process, which minimizes the overhead of the G-matrix and reduces the computational complexity of BP decoding. We explore a detailed mechanism incorporating the parity bits as outer code and prove that the proposed hybrid technique minimizes the computational complexity while preserving the BP error correction performance. Moreover, mathematical formulation for the proposed hybrid technique that minimizes the computation cost of the G-matrix is elaborated. The performance of the proposed hybrid technique is validated by comparing it with the state-of-the-art early stopping criteria for BP decoding. Simulation results show that the proposed hybrid technique reduces the iterations by about 90% of BP decoding in a high Signal-to-Noise Ratio (SNR) (i.e., 3.5 ∼ 4 ​dB), and approaches the error correction performance of G-matrix and conventional BP decoder for polar codes.
In this paper an early termination scheme, partial LLR-aided (PLA) scheme, is proposed for belief propagation (BP) polar decoding with lower complexity and higher throughput. Numerical results of (1024, 512) code show at least 82% iteration reduction than conventional design at SNR =3.5 dB with proposed early termination scheme. In this paper, belief enhancing schemes based on threshold and cyclic redundancy check (CRC) are proposed, namely, threshold-based LLR (TB-LLR) scheme and segment-divided CRC (SD-CRC) scheme. For (1024, 512) polar code, the performance gains for TB-LLR and SD-CRC are 0.35 dB and 0.2 dB respectively, when BER = 10-3. A general hardware architecture for proposed BP polar decoders is also proposed.
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.
For the scenarios with high throughput requirements, the belief propagation (BP) decoding is one of the most promising decoding strategies for polar codes. By pruning the redundant variable nodes (VNs) and check nodes (CNs) in the original factor graph, the graph is condensed to a sparse bipartite graph which is similar to the graph for low-density parity-check (LDPC) codes. In this paper, we introduce the bit-flipping scheme into the LDPC-like BP (L-BP) decoding and propose two methods to identify the error-prone VNs. By additional decoding attempts, the L-BP flip (L-BPF) decoding improves the error-rate performance with a similar average complexity for high Eb=N0values. The simulation results show that the L-BPF decoding achieves 0:25 dB gain compared with the L-BP decoding.
This paper proposes a novel iterative decoder based on concatenated belief propagation (BP) for CRC-aided polar codes. Compared to the conventional BP-based decoders for polar codes, soft cancellation (SCAN) decoder can generate a log likelihood ratio (LLR) of coded bit with lower computational complexity without sacrificing the detection capability. Unfortunately, its performance is not as good as that of CRC-aided successive cancellation list decoder (SCLD) although SCAN decoder has advantage of hardware implementation. To compensate the performance gap, we exploit CRC structure for not only error detection but also error correction with the assistance of its error correction capability at a short code length by exchanging LLRs between SCAN decoder and BP decoder on the basis of CRC. Moreover, the sub-optimal criterion for selecting a parity check matrix of CRC for BP decoder is proposed. Finally, computer simulations are conducted to confirm the validity of our proposed method. The proposed method can obtain the gain of about 0.6 dB at BER=10-3compared to the native SCAN decoder without requiring huge memory size as in SCLD.
The Belief Propagation (BP) algorithm has the advantages of high-speed decoding and low latency. To improve the block error rate (BLER) performance of the BP-based algorithm, the BP flipping algorithm was proposed. However, the BP flipping algorithm attempts numerous useless flippings for improving the BLER performance. To reduce the number of decoding attempts needed without any loss of BLER performance, in this paper a metric is presented to evaluate the likelihood that the bits would correct the BP flipping decoding. Based on this, a BP-Step-Flipping (BPSF) algorithm is proposed which only traces the unreliable bits in the flip set (FS) to flip and skips over the reliable ones. In addition, a threshold β is applied when the magnitude of the log–likelihood ratio (LLR) is small, and an enhanced BPSF (EBPSF) algorithm is presented to lower the BLER. With the same FS, the proposed algorithm can reduce the average number of iterations efficiently. Numerical results show the average number of iterations for EBPSF-1 decreases by 77.5% when N = 256, compared with the BP bit-flip-1 (BPF-1) algorithm at Eb/N0 = 1.5 dB.