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.
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.
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.
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.
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.
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.
A new decoding scheme aided by simulated annealing algorithm is proposed to further improve the decoding performance of successive cancellation (SC) for polar codes at the short block. We use simulated annealing to revise the decoding result of SC which cannot pass the CRC check. To generate the new neighbors, the decoder flips one bit from the set of the least unreliable information bits each time in the estimated source vector of SC decoding. Euclidean distance is used to measure the gap between the new neighbor solution and the received word so that the decoder can obtain a global optimal solution. Simulation shows that the proposed decoder has a performance gain about 0.5 dB in terms of frame error rate (FER) under short blocks in the additive white Gaussian noise (AWGN) channel compared to other basic decoders, while keeping a low time cost through a parameter tuning process.
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.