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

Multiple Node Flip Fast-SSC Decoding Algorithm for Polar Codes Based on Node Reliability

Guo Rui, Pei Yang, Na Ying, Wang Lixin

Published Feb 28, 2022• 0 citations
Publisher

Abstract

This paper presents a fast-simplified successive cancellation (SC) flipping (Fast-SSC-Flip) decoding algorithm for polar code.Firstly, by researching the probability distribution of the number of error bits in a node caused by channel noise in simplified-SC (SSC) decoder, a measurement criterion of node reliability is proposed.Under the guidance of the criterion, the most unreliable nodes are firstly located, then the unreliable bits are selected for flipping, so as to realize Fast-SSC-Flip decoding algorithm based on node reliability (NR-Fast-SSC-Flip).Secondly, we extended the proposed NR-Fast-SSC-Flip to multiple node (NR-Fast-SSC-Flipω) by considering dynamic update to measure node reliability, where ω is the order of flipnodes set.The extended algorithm can correct the error bits in multiple nodes, and get good performance at medium and high signal-to-noise (SNR) region.Simulation results show that the proposed NR-Fast-SSC-Flip decoder can obtain 0.27dB and 0.17dB gains, respectively, compared with the traditional Fast-SSC-Flip [14] and the newly proposed two-bit-flipping Fast-SSC (Fast-SSC-2Flip-E2) [18] under the same conditions.Compared with the newly proposed partitioned Fast-SSC-Flip (PA-Fast-SSC-Flip) (𝑠𝑠=4) [18], the proposed NR-Fast-SSC-Flip-ω (ω=2) decoder can obtain about 0.21dB gain, and the FER performance exceeds the cyclic-redundancy-check (CRC) aided SC-list (CRC-SCL) decoder (L=4).

DOI
10.3837/tiis.2022.02.015

Related papers

An Error Segment Bit-Flip Algorithm for Successive Cancellation List Decoding of Polar Codes

Jing Zhang, Hongbing Qiu, Ling Zhan +1 more

Polar codes have garnered significant attention since they were proposed due to their capacity-achieving properties and their low-complexity decoding process, and they were selected as the coding scheme for the control channel in 5G mobile communication technology. A successive cancellation list (SCL) decoder, aided by a cyclic redundancy check (CRC), performs the competitive error correcting performance for polar codes compared to other sophisticated codes. The SCL-Flip decoding algorithm is proposed to enhance the error correction performance of the SCL. However, the SCL-Flip is hampered by a high decoding complexity due to the necessary selection and sorting process of path metrics (PMs). Additionally, it requires a large number of iterations to achieve a good error correction performance. In this paper, we propose the error segment bit-flip (ES-SCL-Flip) decoding algorithm, a simplified bit-flip approach for the SCL decoder based on analyzing the distributions of the first error bit. Firstly, we construct an index set with a high probability of the first erroneous bit. Second, a bit-flip criterion is introduced to prevent the costly operation of the PM selection and sorting without compromising the error correction performance. Finally, a search strategy is employed that utilizes segmented error indication to target and rectify the initial error segment sequentially. The simulation results demonstrate that the ES-SCL-Flip decoder provides an improved error correction performance with only a minimal increase in decoding complexity compared to the conventional CRC-aided SCL decoder. This algorithm attains a commendable equilibrium between the error correction performance and decoding complexity.

Mathematics•Jul 2, 2024•1 citation

Fast Node Polar Decoding Method Based on Hybrid Parity Check and CRC

Zongmiao He, Yangjun Chen, Shipeng Gao +3 more

In the case of short code, polar code demonstrates superior performance compared with Low Density Parity Check (LDPC) code. Particularly in low coding rate scenario, the complexity of Polar code encoding and decoding is significantly lower than that of LDPC code. The technological advantage of Polar code makes it of great value in special application scenarios such as satellite communication and ocean communication. The polar coding scheme can significantly improve the transmission reliability of the communication system, because the satellite spread spectrum communication system generally adopts short code design.In the research of decoding algorithm, the original Serial Cancellation (SC) decoding algorithm has simple rules, but the decoding effect is not ideal under the limited code length, and the serial decoding mechanism leads to large decoding delay. The Successive Cancellation List (SCL) decoding algorithm improves decoding performance by increasing the number of decoding search path. However, maintaining multiple decoding paths can multiply the decoding complexity. Fast node-based decoding algorithm aims to accelerate decoding and reduce latency by defining and simplifying the decoding process for specific nodes, yet they do not optimize the decoding paths. In view of the above problems, this paper proposes a Simplified Parity Check-based Cyclic Redundancy Check (CRC)-Aided Successive Cancellation List (S-PC-CASCL) decoding algorithm. Simulation results demonstrate that the proposed S-PC-CASCL maintains excellent error correction performance while reducing the average list size by up to 16 % under low Signal Noise Ratio (SNR) conditions, thereby lowering computational complexity and decoding latency compared with other widely used polar decoding methods.

IEEE Access•Jan 1, 2025•0 citations

Bit-Flip Algorithm for Successive Cancellation List Decoder of Polar Codes

Fengyi Cheng, Aijun Liu, Yingxian Zhang +1 more

A successive cancellation list (SCL) decoder with the assistance of a cyclic redundancy check (CRC) can provide competitive decoding performance for polar codes compared with the state-of-the-art codes. In this paper, we adopt a bit-flip algorithm for the CRC-assisted SCL decoder to further improve the error-correcting performance. We first introduce a new bit-flip criterion for the SCL decoder. To support this criterion, we give the metric to identify the positions that need to be flipped. To verify the superiority of the proposed bit-flip criterion, we also consider a kind of SCL-flip decoder whose criterion is very similar with the existing one and we will prove that its performance is worse than the decoder with the proposed bit-flip criterion. The simulation results show that the decoder with the proposed bit-flip criterion outperforms both the standard CRC-assisted SCL decoder and the existing SCL-based bit-flip decoder.

IEEE Access•Jan 1, 2019•41 citations

Belief Propagation Bit-Flip Decoder for Polar Codes

Yongrun Yu, Zhiwen Pan, Nan Liu +1 more

The bit-flip method has been successfully applied to the successive cancellation (SC) decoder to improve the block error rate (BLER) performance for polar codes in the finite code length region. However, due to the sequential decoding, the SC decoder inherently suffers from longer decoding latency than that of the belief propagation (BP) decoder with efficient early stopping criterion. It is natural to ask how to perform bit-flip in a polar BP decoder. In this paper, bit-flip is introduced into the BP decoder for polar codes. The idea of critical set (CS), that is, originally proposed by Zhang et al. for identifying unreliable bits in a SC bit-flip decoder, is extended to the BP decoder here. After revealing the relationship between CS and the incorrect BP decoding results, critical set with order ω (CS-ω) is constructed to identify unreliable bit decisions in polar BP decoding. The simulation results demonstrate that compared with the conventional BP decoder, the BLER of the proposed bit-flip decoder can achieve significant signal-to-noise ratio (SNR) gain which is comparable to that of a cyclic redundancy check-aided SC list decoder with a moderate list size. In addition, the decoding latency of the proposed BP bit-flip decoder is only slightly higher than that of the conventional BP decoder in the medium and high SNR regions.

IEEE Access•Jan 1, 2019•67 citations

Improved Fast-SSC-Flip Decoding of Polar Codes

Yangcan Zhou, Jun Ting Lin, Zhongfeng Wang

In this letter, state-of-the-art fast simplified successive-cancellation (Fast-SSC) decoding is modified to cooperate with SC flip decoding. The resulting Fast-SSC-Flip decoding aims to flip the first error of invalid codewords to improve the performance of polar codes. Compared with existing Fast-SSC-Flip decoding, our decoder has about a 0.45-dB performance gain. For most undecodable codewords under Fast-SSC decoding, the proposed Fast-SSC-Flip decoding can successfully decode them much faster than prior Fast-SSC-Flip decoding.

IEEE Communications Letters•Jun 1, 2019•18 citations

An Improved Bit-Flipping Based Decoding Algorithm for Polar Codes

Xiao Hu, Shufeng Li, Mingyu Cai

In this paper, we propose three improved bit flipping algorithms in successive cancellation (SC) decoding and successive cancellation list (SCL) decoding. Weighted single-bit flipping successive cancellation (WSFSC) decoding first performs SC decoding on the output sequence, T bits with the smallest product of channel capacity and absolute value of LLR are regarded as unreliable bits. In multi-bit flipping successive cancellation (MFSC) algorithm, the unreliable bits are respectively corrected according to the single-bit flipping and multi-bit flipping rules. In single flipping successive cancellation list (SFSCL) algorithm, by subtracting a large penalty value from the path metric (PM) value of the unreliable bit, the decoding path corresponding to this bit is more likely to be pruned during path screening, so as to realize bit flipping indirectly. Simulation results show that the proposed WSFSC and MFSC algorithm has a gain of 0.3dB compared with the traditional SC algorithm, SFSCL algorithm has a gain of 0.3dB compared with the traditional SCL algorithm.

IEEE International Conference on Control Science and Systems Engineering (ICCSSE)•Jul 30, 2021•2 citations
This paper presents a fast-simplified successive cancellation (SC) flipping (Fast-SSC-Flip) decoding algorithm for polar code.Firstly, by researching the probability distribution of the number of error bits in a node caused by channel noise in simplified-SC (SSC) decoder, a measurement criterion of node reliability is proposed.Under the guidance of the criterion, the most unreliable nodes are firstly located, then the unreliable bits are selected for flipping, so as to realize Fast-SSC-Flip decoding algorithm based on node reliability (NR-Fast-SSC-Flip).Secondly, we extended the proposed NR-Fast-SSC-Flip to multiple node (NR-Fast-SSC-Flipω) by considering dynamic update to measure node reliability, where ω is the order of flipnodes set.The extended algorithm can correct the error bits in multiple nodes, and get good performance at medium and high signal-to-noise (SNR) region.Simulation results show that the proposed NR-Fast-SSC-Flip decoder can obtain 0.27dB and 0.17dB gains, respectively, compared with the traditional Fast-SSC-Flip [14] and the newly proposed two-bit-flipping Fast-SSC (Fast-SSC-2Flip-E2) [18] under the same conditions.Compared with the newly proposed partitioned Fast-SSC-Flip (PA-Fast-SSC-Flip) (𝑠𝑠=4) [18], the proposed NR-Fast-SSC-Flip-ω (ω=2) decoder can obtain about 0.21dB gain, and the FER performance exceeds the cyclic-redundancy-check (CRC) aided SC-list (CRC-SCL) decoder (L=4).
Polar codes have garnered significant attention since they were proposed due to their capacity-achieving properties and their low-complexity decoding process, and they were selected as the coding scheme for the control channel in 5G mobile communication technology. A successive cancellation list (SCL) decoder, aided by a cyclic redundancy check (CRC), performs the competitive error correcting performance for polar codes compared to other sophisticated codes. The SCL-Flip decoding algorithm is proposed to enhance the error correction performance of the SCL. However, the SCL-Flip is hampered by a high decoding complexity due to the necessary selection and sorting process of path metrics (PMs). Additionally, it requires a large number of iterations to achieve a good error correction performance. In this paper, we propose the error segment bit-flip (ES-SCL-Flip) decoding algorithm, a simplified bit-flip approach for the SCL decoder based on analyzing the distributions of the first error bit. Firstly, we construct an index set with a high probability of the first erroneous bit. Second, a bit-flip criterion is introduced to prevent the costly operation of the PM selection and sorting without compromising the error correction performance. Finally, a search strategy is employed that utilizes segmented error indication to target and rectify the initial error segment sequentially. The simulation results demonstrate that the ES-SCL-Flip decoder provides an improved error correction performance with only a minimal increase in decoding complexity compared to the conventional CRC-aided SCL decoder. This algorithm attains a commendable equilibrium between the error correction performance and decoding complexity.
In the case of short code, polar code demonstrates superior performance compared with Low Density Parity Check (LDPC) code. Particularly in low coding rate scenario, the complexity of Polar code encoding and decoding is significantly lower than that of LDPC code. The technological advantage of Polar code makes it of great value in special application scenarios such as satellite communication and ocean communication. The polar coding scheme can significantly improve the transmission reliability of the communication system, because the satellite spread spectrum communication system generally adopts short code design.In the research of decoding algorithm, the original Serial Cancellation (SC) decoding algorithm has simple rules, but the decoding effect is not ideal under the limited code length, and the serial decoding mechanism leads to large decoding delay. The Successive Cancellation List (SCL) decoding algorithm improves decoding performance by increasing the number of decoding search path. However, maintaining multiple decoding paths can multiply the decoding complexity. Fast node-based decoding algorithm aims to accelerate decoding and reduce latency by defining and simplifying the decoding process for specific nodes, yet they do not optimize the decoding paths. In view of the above problems, this paper proposes a Simplified Parity Check-based Cyclic Redundancy Check (CRC)-Aided Successive Cancellation List (S-PC-CASCL) decoding algorithm. Simulation results demonstrate that the proposed S-PC-CASCL maintains excellent error correction performance while reducing the average list size by up to 16 % under low Signal Noise Ratio (SNR) conditions, thereby lowering computational complexity and decoding latency compared with other widely used polar decoding methods.
A successive cancellation list (SCL) decoder with the assistance of a cyclic redundancy check (CRC) can provide competitive decoding performance for polar codes compared with the state-of-the-art codes. In this paper, we adopt a bit-flip algorithm for the CRC-assisted SCL decoder to further improve the error-correcting performance. We first introduce a new bit-flip criterion for the SCL decoder. To support this criterion, we give the metric to identify the positions that need to be flipped. To verify the superiority of the proposed bit-flip criterion, we also consider a kind of SCL-flip decoder whose criterion is very similar with the existing one and we will prove that its performance is worse than the decoder with the proposed bit-flip criterion. The simulation results show that the decoder with the proposed bit-flip criterion outperforms both the standard CRC-assisted SCL decoder and the existing SCL-based bit-flip decoder.
The bit-flip method has been successfully applied to the successive cancellation (SC) decoder to improve the block error rate (BLER) performance for polar codes in the finite code length region. However, due to the sequential decoding, the SC decoder inherently suffers from longer decoding latency than that of the belief propagation (BP) decoder with efficient early stopping criterion. It is natural to ask how to perform bit-flip in a polar BP decoder. In this paper, bit-flip is introduced into the BP decoder for polar codes. The idea of critical set (CS), that is, originally proposed by Zhang et al. for identifying unreliable bits in a SC bit-flip decoder, is extended to the BP decoder here. After revealing the relationship between CS and the incorrect BP decoding results, critical set with order ω (CS-ω) is constructed to identify unreliable bit decisions in polar BP decoding. The simulation results demonstrate that compared with the conventional BP decoder, the BLER of the proposed bit-flip decoder can achieve significant signal-to-noise ratio (SNR) gain which is comparable to that of a cyclic redundancy check-aided SC list decoder with a moderate list size. In addition, the decoding latency of the proposed BP bit-flip decoder is only slightly higher than that of the conventional BP decoder in the medium and high SNR regions.
In this letter, state-of-the-art fast simplified successive-cancellation (Fast-SSC) decoding is modified to cooperate with SC flip decoding. The resulting Fast-SSC-Flip decoding aims to flip the first error of invalid codewords to improve the performance of polar codes. Compared with existing Fast-SSC-Flip decoding, our decoder has about a 0.45-dB performance gain. For most undecodable codewords under Fast-SSC decoding, the proposed Fast-SSC-Flip decoding can successfully decode them much faster than prior Fast-SSC-Flip decoding.
In this paper, we propose three improved bit flipping algorithms in successive cancellation (SC) decoding and successive cancellation list (SCL) decoding. Weighted single-bit flipping successive cancellation (WSFSC) decoding first performs SC decoding on the output sequence, T bits with the smallest product of channel capacity and absolute value of LLR are regarded as unreliable bits. In multi-bit flipping successive cancellation (MFSC) algorithm, the unreliable bits are respectively corrected according to the single-bit flipping and multi-bit flipping rules. In single flipping successive cancellation list (SFSCL) algorithm, by subtracting a large penalty value from the path metric (PM) value of the unreliable bit, the decoding path corresponding to this bit is more likely to be pruned during path screening, so as to realize bit flipping indirectly. Simulation results show that the proposed WSFSC and MFSC algorithm has a gain of 0.3dB compared with the traditional SC algorithm, SFSCL algorithm has a gain of 0.3dB compared with the traditional SCL algorithm.