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 Conference on Computer and Communications (ICCC)

A Low-Complexity Improved Progressive Bit-Flipping Decoding for Polar Codes

Jianming Cui, Zuowen Zhang, Xiaojun Zhang, Hengzhong Li, Qingtian Zeng

Published Dec 1, 2018• 2 citations
Publisher

Abstract

The decoding performance of successive cancellation (SC) can be improved by correcting the error bits caused by channel noises. In order to identify and correct those error bits, we propose an improved progressive bit-flipping (IPBF) decoding algorithm. First, a more efficient method of constructing the set of error bit positions (EBPs) is proposed. It can significantly reduce the size of the set of EBPs, especially at medium to high signal to noise ratio (SNR). Second, a pruning technique of reducing the number of error bit-flipping combinations (EBFCs) is presented. In the case of ensuring that the decoding performance of PBF algorithm is not degraded, the decoding complexity is reduced as much as possible with the help of the pruning scheme. From the simulation results, compared to the conventional PBF algorithm, the proposed IPBF algorithm not only significantly reduces the average decoding complexity, but also has a slight improvement in decoding performance. At 2.0dB, the decoding complexity can be reduced by 63.6%, 87.5%, and 97.6% when ω is equal to 2, 3 and 4, respectively.

DOI
10.1109/compcomm.2018.8780858

Related papers

An Improved Multiple Bit-Flipping Successive Cancellation Decoding Algorithm for Polar Codes

Sha Sha, Li Guo Zhang, Yejun He

Although original successive cancellation flip (SCF) decoding of the polar codes can identify the first error position and flip the error, decoding still fails when other errors occur after the corrected error bit. Therefore, the improvement of the block error rate (BLER) performance is limited. In this paper, we present an improved algorithm that can correct multiple error bits, named as improved multiple bit-flipping successive cancellation decoding algorithm. First, multiple sets are constructed by calculating the log likelihood ratio (LLR) of each information bit. Then, a bit is selected and corrected from the first set when original decoding fails; two bits are selected and flipped from the second set when all bits in the first set cannot be successfully decoded; when all bits combinations in the second set are flipped but the output vector still does not match the input vector, three bits are selected and corrected from the third set. Simulation results show that the BLER performance of the improved algorithm is better than that of the successive cancellation list decoding (SCL) decoding algorithm with a list size of L = 8 for N = 256. When N = 1024 and SNR = 3 dB, the BLER performance of improved algorithm is slightly better than that of SCL decoding algorithm with a list size of L = 4.

International Conference on Wireless Communications and Signal Processing (WCSP)•Oct 21, 2020•1 citation

An Improved Belief Propagation Bit-Flipping Decoder for Polar Codes

Mengqing Zhao, Daqin Peng

Bit flipping was first used to improve the decoding performance of successive cancellation (SC) decoder. Since SC decoding process is serial, so the first bit that goes wrong in the decoding process will cause several subsequent bits to go wrong, which will suffer from higher decoding delay than belief propagation (BP) parallel decoding. In order to meet the performance of 5G low latency and high reliability, BP decoding algorithm have received a lot of attention. However, at medium and high signal-to-noise ratios (SNR), BP decoding does not perform as well as the SC list (SCL) decoding algorithm. Hence, BP decoding algorithm borrows bit-flip strategies from SC bit flip (SCF) decoder to improve the performance. The performance of BP bit flip (BPF) decoding depends on whether the construction of the flip set is correct, so this letter proposes a flip set construction approach based on the standard deviation of the log-likelihood ratio (LLR) and the reliability weight of polarized channels, which is comparable to the existing BPF decoding, the improved algorithm can identify the error-prone bits more efficiently and improve the decoding performance.

International Conference on Intelligent Computing and Signal Processing (ICSP)•Apr 21, 2023•2 citations

An Improved Bit-Flipping Algorithm of Successive Cancellation List Decoding for Polar Codes

Desheng Wang, Jihang Yin, Yonggang Xu +3 more

Polar codes, as the coding scheme for the control channel in fifth-generation mobile communication technology (5G), have attracted widespread attention since their proposal. As a mainstream decoding algorithm for polar codes, the successive cancellation list (SCL) decoder usually improves the error correction performance by increasing the list size, but this method suffers from the problems of high decoding complexity. To address this problem, this paper proposes a layered-search bit-flipping (LS-SCLF) decoding algorithm based on SCL decoding. Firstly, a new flip-bit metric is proposed, which derives a formula to approximate the probability of an error occurring in an information bit. This formula introduces a perturbation parameter to improve the calculation accuracy. Secondly, a compromise scheme for determining the perturbation parameter is proposed. The scheme uses Monte Carlo simulation to determine an optimized parameter for the precise positioning of the first erroneous decoded bit under different decoding conditions. Finally, a layered search strategy is adopted to sequentially search the erroneous decoded bits from the low order to high order, which can correct up to multiple bits at the same time. Simulation results show that the proposed algorithm achieves improved error correction performance with a slight increase in decoding complexity compared to the generalized SCL-Flip (GSCLF) decoding algorithm. This algorithm also achieves a good balance between the error correction performance and decoding complexity.

Mathematics•Oct 27, 2023•2 citations

A Low Complexity Segmented Parity SC Flip Decoding Algorithm for Polar Codes

Dwaipayan Ghosh, Shriya Das, Leuna Das +2 more

The Successive Cancellation decoder cannot provide satisfactory error correcting performance for finite length polar codes. The error performance can be improved by using Successive Cancellation Flip decoders at the expense of higher complexity. In line with this, a novel decoding approach has been developed in this paper, where distributed parity bits are used to divide the codeword into multiple segments having equal probability of error occurrence, allowing early termination. The proposed Segmented Parity Successive Cancellation Flip (SP-SC Flip) Decoder achieves lower normalized complexity and average decoding latency compared to some related existing decoders, without degrading the error correcting performance. Further improvement in decoder performance is observed when code words are divided into a greater number of segments.

IEEE International Conference on Advanced Networks and Telecommunications Systems•Dec 15, 2024•0 citations

A Muti-Bit Flip Successive Cancellation Decoder for Polar Codes

Xiaonan Jiang, Xiaoming Niu, Ruihuan Tian +3 more

A decoding algorithm for polar codes based on successive cancellation is proposed in this paper, which determines the location of multiple bit errors by calculating the maximum likelihood result of successive cancellation decoding, and achieves the improvement of decoding performance by flipping the values of multiple bits. Simulation results show that the proposed multi-bit flip decoding algorithm exhibits better performance than the single-bit flip decoding algorithm with the same-order computational complexity under the additive white Gaussian noise (AWGN). In addition, as the signal-to-noise ratio (SNR) increases, the complexity of the proposed algorithm approaches that of the successive cancellation decoder.

International Symposium on Antennas, Propagation and EM Theory (ISAPE)•Oct 23, 2024•1 citation

Fast Successive-Cancellation List Flip Decoding of Polar Codes

Nghia Doan, Seyyed Ali Hashemi, Warren J. Gross

This work presents a fast successive-cancellation list flip (Fast-SCLF) decoding algorithm for polar codes that addresses the high latency issue associated with the successive-cancellation list flip (SCLF) decoding algorithm. We first propose a bit-flipping strategy tailored to the state-of-the-art fast successive-cancellation list (FSCL) decoding that avoids tree-traversal in the binary tree representation of SCLF, thus reducing the latency of the decoding process. We then derive a parameterized path selection error model to accurately estimate the bit index at which the correct decoding path is eliminated from the initial FSCL decoding. The trainable parameter is optimized online based on an efficient supervised learning framework. Simulation results show that for a polar code of length 512 with 256 information bits, with similar error-correction performance and memory consumption, the proposed Fast-SCLF decoder reduces up to 73.4% of the average decoding latency of the SCLF decoder with the same list size at the frame error rate of 10−4, while incurring a maximum computational complexity overhead of 27.6%. For the same polar code of length 512 with 256 information bits and at practical signal-to-noise ratios, the proposed decoder with list size 4 reduces 89.3% and 43.7% of the average complexity and decoding latency of the FSCL decoder with list size 32 (FSCL-32), respectively, while also reducing 83.2% of the memory consumption of FSCL-32. The significant improvements of the proposed decoder come at the cost of 0.07 dB error-correction performance degradation compared with FSCL-32.

arXiv:2109.12239•IEEE Access•Jan 1, 2022•8 citations
The decoding performance of successive cancellation (SC) can be improved by correcting the error bits caused by channel noises. In order to identify and correct those error bits, we propose an improved progressive bit-flipping (IPBF) decoding algorithm. First, a more efficient method of constructing the set of error bit positions (EBPs) is proposed. It can significantly reduce the size of the set of EBPs, especially at medium to high signal to noise ratio (SNR). Second, a pruning technique of reducing the number of error bit-flipping combinations (EBFCs) is presented. In the case of ensuring that the decoding performance of PBF algorithm is not degraded, the decoding complexity is reduced as much as possible with the help of the pruning scheme. From the simulation results, compared to the conventional PBF algorithm, the proposed IPBF algorithm not only significantly reduces the average decoding complexity, but also has a slight improvement in decoding performance. At 2.0dB, the decoding complexity can be reduced by 63.6%, 87.5%, and 97.6% when ω is equal to 2, 3 and 4, respectively.
Although original successive cancellation flip (SCF) decoding of the polar codes can identify the first error position and flip the error, decoding still fails when other errors occur after the corrected error bit. Therefore, the improvement of the block error rate (BLER) performance is limited. In this paper, we present an improved algorithm that can correct multiple error bits, named as improved multiple bit-flipping successive cancellation decoding algorithm. First, multiple sets are constructed by calculating the log likelihood ratio (LLR) of each information bit. Then, a bit is selected and corrected from the first set when original decoding fails; two bits are selected and flipped from the second set when all bits in the first set cannot be successfully decoded; when all bits combinations in the second set are flipped but the output vector still does not match the input vector, three bits are selected and corrected from the third set. Simulation results show that the BLER performance of the improved algorithm is better than that of the successive cancellation list decoding (SCL) decoding algorithm with a list size of L = 8 for N = 256. When N = 1024 and SNR = 3 dB, the BLER performance of improved algorithm is slightly better than that of SCL decoding algorithm with a list size of L = 4.
Bit flipping was first used to improve the decoding performance of successive cancellation (SC) decoder. Since SC decoding process is serial, so the first bit that goes wrong in the decoding process will cause several subsequent bits to go wrong, which will suffer from higher decoding delay than belief propagation (BP) parallel decoding. In order to meet the performance of 5G low latency and high reliability, BP decoding algorithm have received a lot of attention. However, at medium and high signal-to-noise ratios (SNR), BP decoding does not perform as well as the SC list (SCL) decoding algorithm. Hence, BP decoding algorithm borrows bit-flip strategies from SC bit flip (SCF) decoder to improve the performance. The performance of BP bit flip (BPF) decoding depends on whether the construction of the flip set is correct, so this letter proposes a flip set construction approach based on the standard deviation of the log-likelihood ratio (LLR) and the reliability weight of polarized channels, which is comparable to the existing BPF decoding, the improved algorithm can identify the error-prone bits more efficiently and improve the decoding performance.
Polar codes, as the coding scheme for the control channel in fifth-generation mobile communication technology (5G), have attracted widespread attention since their proposal. As a mainstream decoding algorithm for polar codes, the successive cancellation list (SCL) decoder usually improves the error correction performance by increasing the list size, but this method suffers from the problems of high decoding complexity. To address this problem, this paper proposes a layered-search bit-flipping (LS-SCLF) decoding algorithm based on SCL decoding. Firstly, a new flip-bit metric is proposed, which derives a formula to approximate the probability of an error occurring in an information bit. This formula introduces a perturbation parameter to improve the calculation accuracy. Secondly, a compromise scheme for determining the perturbation parameter is proposed. The scheme uses Monte Carlo simulation to determine an optimized parameter for the precise positioning of the first erroneous decoded bit under different decoding conditions. Finally, a layered search strategy is adopted to sequentially search the erroneous decoded bits from the low order to high order, which can correct up to multiple bits at the same time. Simulation results show that the proposed algorithm achieves improved error correction performance with a slight increase in decoding complexity compared to the generalized SCL-Flip (GSCLF) decoding algorithm. This algorithm also achieves a good balance between the error correction performance and decoding complexity.
The Successive Cancellation decoder cannot provide satisfactory error correcting performance for finite length polar codes. The error performance can be improved by using Successive Cancellation Flip decoders at the expense of higher complexity. In line with this, a novel decoding approach has been developed in this paper, where distributed parity bits are used to divide the codeword into multiple segments having equal probability of error occurrence, allowing early termination. The proposed Segmented Parity Successive Cancellation Flip (SP-SC Flip) Decoder achieves lower normalized complexity and average decoding latency compared to some related existing decoders, without degrading the error correcting performance. Further improvement in decoder performance is observed when code words are divided into a greater number of segments.
A decoding algorithm for polar codes based on successive cancellation is proposed in this paper, which determines the location of multiple bit errors by calculating the maximum likelihood result of successive cancellation decoding, and achieves the improvement of decoding performance by flipping the values of multiple bits. Simulation results show that the proposed multi-bit flip decoding algorithm exhibits better performance than the single-bit flip decoding algorithm with the same-order computational complexity under the additive white Gaussian noise (AWGN). In addition, as the signal-to-noise ratio (SNR) increases, the complexity of the proposed algorithm approaches that of the successive cancellation decoder.
This work presents a fast successive-cancellation list flip (Fast-SCLF) decoding algorithm for polar codes that addresses the high latency issue associated with the successive-cancellation list flip (SCLF) decoding algorithm. We first propose a bit-flipping strategy tailored to the state-of-the-art fast successive-cancellation list (FSCL) decoding that avoids tree-traversal in the binary tree representation of SCLF, thus reducing the latency of the decoding process. We then derive a parameterized path selection error model to accurately estimate the bit index at which the correct decoding path is eliminated from the initial FSCL decoding. The trainable parameter is optimized online based on an efficient supervised learning framework. Simulation results show that for a polar code of length 512 with 256 information bits, with similar error-correction performance and memory consumption, the proposed Fast-SCLF decoder reduces up to 73.4% of the average decoding latency of the SCLF decoder with the same list size at the frame error rate of 10−4, while incurring a maximum computational complexity overhead of 27.6%. For the same polar code of length 512 with 256 information bits and at practical signal-to-noise ratios, the proposed decoder with list size 4 reduces 89.3% and 43.7% of the average complexity and decoding latency of the FSCL decoder with list size 32 (FSCL-32), respectively, while also reducing 83.2% of the memory consumption of FSCL-32. The significant improvements of the proposed decoder come at the cost of 0.07 dB error-correction performance degradation compared with FSCL-32.