KSII Transactions on Internet and Information Systems

Complete State Critical Set Based SCLF Decoding Algorithm for Polar Codes

Wenjie Dai, Rui Guo

Published Dec 31, 2024• 0 citations

Abstract

The revised critical set (RCS) used by successive cancellation list flip (SCLF) decoding algorithm only retains the unreliable bits of SC state.So, the bits of information in the RCS are not comprehensive enough.Aiming at this problem, this paper proposed a kind of complete state critical set (CSCS) based SCLF decoding algorithm for polar codes.In order to obtain a more complete flipping set of states, the proposed CSCS is constructed according to different path splitting states after pruning.According to different states of CSCS, hard decision and path metric (PM) correction methods are adopted respectively, to cut off the wrong path and keep the correct path, so as to achieve bit flipping function.Experimental results show that compared with the traditional SCLF decoding algorithm, the performance of complete state SCLF (CS-SCLF) decoding algorithm is improved.At the same time, the average flipping number of flips is reduced without loss of decoding performance.

DOI: 10.3837/tiis.2024.12.011

Related papers

Bit Metrics Based on SCLF Decoding Algorithm for Polar Codes

Haifeng Lin, Rui Guo

As an indispensable part of cyclic redundancy check aided Successive Cancellation List (CA-SCL) decoding and SCL bit flipping (CA-SCLF) decoding, sort operation increases the complexity of decoding.In order to minimize the quantity of sorting and simplify the complexity of SCLF decoding algorithm, this paper proposes an improved SCLF decoding algorithm, called NSCLF algorithm, which reduces the number of paths involved in sorting by detecting and pruning paths whose bit metric value is less than the set threshold before sorting operations.Meanwhile, pruning paths are dynamically selected according to node states during the flipping process.The flipping path selections are more accurate and the number of flipping correspondingly decreases.The simulation results demonstrate that when SNR is 3dB, the code length and code rate , while maintaining decoding performance comparable to that of traditional CA-SCLF, the sorting operation of our proposed NSCLF is about 93% less than that of traditional CA-SCLF, and the decoding complexity is less than that of traditional CA-SCLF.

KSII Transactions on Internet and Information SystemsMay 31, 20250 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, 20212 citations

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.12239IEEE AccessJan 1, 20228 citations

Successive Cancellation List Flip Decoding for eBCH-polar Codes

Wei-Cheng Wang, Meng-Ru Wu, Shan Lu +2 more

The eBCH-polar codes is a powerful way to construct polar codes. With high minimum Hamming distance, it outperforms ordinary Polar codes under successive cancellation list (SCL) decoder. However, the absence of cyclic redundancy check (CRC) bits in eBCH-polar codes makes it challenging to adopt SCL-flip (SCLF) decoding scheme. In this research, we propose a flip scheme activated by a Normalized Path Metric (PM) range and a mismatch criterion, which respectively leverage the properties of SCL decoding and dynamic frozen bits of eBCH-polar codes. This work also improves the selection the flipping bits by modifying metric to account for the structure of dynamic frozen bits and reduce the search space. Based on these modifications, we proposed SCLF-1 and SCLF-2 decoding algorithms for eBCH-polar codes. Simulation results show that both of the proposed decoding schemes achieve superior performance compared to other contemporary decoding algorithms for CRC aided polar (CA-polar) codes, demonstrating enhanced error rates performance within the same decoding attempt.

IEEE Vehicular Technology ConferenceOct 19, 20250 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.

MathematicsOct 27, 20232 citations

Improved generalized successive cancellation list flip decoder of polar codes with fast decoding of special nodes

Fedor I. Ivanov, Valerii Morishnik, Evgenii A. Krouk

In this paper, an improvement for SC list flip (SCL-Flip) decoding is presented for polar codes. A novel bit-selection metric for critical set (set of information symbols of polar codes being flipped during additional decoding attempts) based on path metric of successive cancellation list (SCL) decoding is suggested. With the proposed metric, the improved SCL scheme based on special nodes (SN) decoders was developed. This decoder will be denoted by GSCLF. The main idea of the proposed decoder is joint using of two approaches: first one is a fast decoding of special nodes in binary tree representation of polar code (e.g., some special nodes in tree representation of polar code that allow efficient list decoding with low complexity) and the second one is an applying of additional decoding attempts (flips) in the case when initial decoding was erroneous. The simultaneous use of these two approaches results in both a significant reduction in spatial complexity and a significant reduction in the number of computations required for decoding whereas keeping excellent performance. Simulation results presented in this paper allow us to conclude that the computational complexity of the proposed GSCLF decoder is from 66% to 80% smaller than the one of SCL-32 decoder.

Journal of Communications and NetworksDec 1, 202120 citations