A successive cancellation (SC) decoder with inactivations is proposed as an efficient implementation of SC list (SCL) decoding over the binary erasure channel. The proposed decoder assigns a dummy variable to an information bit whenever it is erased during SC decoding and continues with decoding. Inactivated bits are resolved using information gathered from decoding frozen bits. This decoder leverages the structure of the Hadamard matrix, but can be applied to any linear code by representing it as a polar code with dynamic frozen bits. SCL decoders are partially characterized using density evolution to compute the average number of inactivations required to achieve the maximum a-posteriori decoding performance. The proposed measure quantifies the performance vs. complexity trade-off and provides new insight into dynamics of the number of paths in SCL decoding. The technique is applied to analyze Reed-Muller (RM) codes with dynamic frozen bits. It is shown that these modified RM codes perform close to extended BCH codes.
A successive cancellation (SC) decoder with inactivations is proposed as an efficient implementation of SC list (SCL) decoding over the binary erasure channel. The proposed decoder assigns a dummy variable to an information bit whenever it is erased during SC decoding and continues with decoding. Inactivated bits are resolved using information gathered from decoding frozen bits. This decoder leverages the structure of the Hadamard matrix, but can be applied to any linear code by representing it as a polar code with dynamic frozen bits. SCL decoders are partially characterized using density evolution to compute the average number of inactivations required to achieve the maximum a-posteriori decoding performance. The proposed measure quantifies the performance vs. complexity trade-off and provides new insight into dynamics of the number of paths in SCL decoding. The technique is applied to analyze Reed-Muller (RM) codes with dynamic frozen bits. It is shown that these modified RM codes perform close to extended BCH codes.
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.
This work identifies information-theoretic quantities that are closely related to the required list size on average for successive cancellation list (SCL) decoding to implement maximum-likelihood decoding over general binary memoryless symmetric (BMS) channels. It also provides upper and lower bounds for these quantities that can be computed efficiently for very long codes. For the binary erasure channel (BEC), we provide a simple method to estimate the mean accurately via density evolution. The analysis shows how to modify, e.g., Reed-Muller codes, to improve the performance when practical list sizes, e.g.,L∈[8,1024], are adopted. Exemplary constructions with block lengthsN∈{128,512}outperform polar codes of 5G over the binary-input additive white Gaussian noise channel. It is further shown that there is a concentration around the mean of the logarithm of the required list size for sufficiently large block lengths, over discrete-output BMS channels. We provide the probability mass functions (p.m.f.s) of this logarithm, over the BEC, for a sequence of the modified RM codes with an increasing block length via simulations, which illustrate that the p.m.f.s concentrate around the estimated mean.
Successive cancellation (SC) decoding algorithm and successive cancellation list (SCL) decoding algorithm are two common decoding methods for polar codes. The SC decoding algorithm has low complexity, but in its decoding process, the bits with small channel indices are used to assist the decoding of the bits with large channel indices. Therefore, the bit being decoded depends on the bits that have already been decoded which causes error propagation. On the basis of SC decoding, the SCL decoding algorithm overcomes the problem of error propagation by widening the path search width and retaining multiple paths at the same time in the decoding process. However, the complexity of SCL decoding is higher than that of SC decoding. Without changing the performance of the SCL decoding algorithm, we propose a low-complexity SCL decoding algorithm based on path metric (PM). After the last frozen bit is decoded, the path with the smallest PM is selected, and the subsequent nodes adopt SC decoding. Through this combination of SCL decoding and SC decoding, the complexity of the SCL decoding algorithm can be effectively reduced while the SCL decoding performance remains unchanged, especially in the case of high code rates.
To address the weaknesses of successive cancellation (SC) decoding, this chapter explores enhanced algorithms that follow multiple paths in the decoding tree. These decoders, known as successive cancelation list (SCL) decoders, retain the recursive structure of SC decoding while improving its performance by considering several distinct solutions. The chapter delves into both parallel and serial implementations of SCL decoders, highlighting their fundamental structures and trade-offs. It helps the readers to gain an understanding of the fundamental principles behind SC list decoders and learn how to exploit the structural properties of polar codes to enhance decoding efficiency. The SCL decoding algorithm scans the binary tree (in the case of binary codes) by following more than one path at a time. That is, a number of paths are followed in parallel. The chapter review different strategies for additional decoding attempts in an iterative manner for the SC and SCL decoding algorithms.
In the conventional successive cancellation (SC) decoder for polar codes, all the future bits to be estimated later are treated as random variables. However, polar codes inevitably involve frozen bits, and their concatenated coding schemes also include parity bits (or dynamic frozen bits) causally generated from the past bits estimated earlier. We refer to the frozen and parity bits located behind a target decoding bit as its future constraints (FCs). Although the values of FCs are deterministic given the past estimates, they have not been exploited in the conventional SC-based decoders, not leading to optimality. In this paper, with a primary focus on the binary erasure channel (BEC), we propose SC-check (SCC) and belief propagation SCC (BP-SCC) decoding algorithms in order to leverage FCs in decoding. We further devise an improved tree search technique based on stack-based backjumping (SBJ) to solve dynamic constraint satisfaction problems (CSPs) formulated by FCs. Over the BEC, numerical results show that a combination of the BP-SCC algorithm and the SBJ tree search technique achieves the erasure recovery performance close to the dependence testing (DT) bound, a bound of achievable finite-length performance.
In this paper, a new soft-decision decoding for extended Bose-Chaudhuri-Hocquenghem (eBCH) codes, referred to as CPC-SCL, is proposed, and it can achieve error-correction performance close to that of polarization-adjusted convolutional (PAC) codes in [1] when the code length n and dimension k are 128 and 64, respectively. Specifically, this paper first decomposes the eBCH code into a concatenated structure comprising an outer code and a Reed-Muller inner code. The outer code has a parity-check matrix characterized by a special block structure, which reveals that the positions of all frozen bits (including frozen zero bits and dynamic frozen bits) in the eBCH code are closely related to the index weights of elements from the perspective of the polar code. Subsequently, the CPC-SCL decoding of the eBCH codes is proposed by utilizing the cyclic property of codewords and parity-check-aided successive cancellation list (PC-SCL) decoding. Simulations also demonstrate that, over an additive white Gaussian noise (AWGN) channel with binary phase-shift keying (BPSK) modulation, the proposed decoding can achieve near maximum-likelihood (ML) performance at n = 64, k = 24 or 45.