A complexity-adaptive tree search algorithm is proposed for $boldsymbol{G}_N$-coset codes that implements maximum-likelihood (ML) decoding by using a successive decoding schedule. The average complexity is close to that of the successive cancellation
(SC) decoding for practical error rates when applied to polar codes and short Reed-Muller (RM) codes, e.g., block lengths up to $N=128$. By modifying the algorithm to limit the worst-case complexity, one obtains a near-ML decoder for longer RM codes and their subcodes. Unlike other bit-flip decoders, no outer code is needed to terminate decoding. The algorithm can thus be applied to modified $boldsymbol{G}_N$-coset code constructions with dynamic frozen bits. One advantage over sequential decoders is that there is no need to optimize a separate parameter.
This work identifies information-theoretic quantities that are closely related to the required list size for successive cancellation list (SCL) decoding to implement maximum-likelihood decoding. It also provides an approximation for these quantities
that can be computed efficiently for very long codes. There is a concentration around the mean of the logarithm of the required list size for sufficiently large block lengths. We further provide a simple method to estimate the mean via density evolution for the binary erasure channel (BEC). Simulation results for the binary-input additive white Gaussian noise channel as well as the BEC demonstrate the accuracy of the mean estimate. A modified Reed-Muller code with dynamic frozen bits performs very close to the random coding union (RCU) bound down to the block error rate of $10^{-5}$ under SCL decoding with list size $L=128$ when the block length is $N=128$. The analysis shows how to modify the design to improve the performance when a more practical list size, e.g., $L=32$, is adopted while keeping the performance with $L=128$ unchanged. For the block length of $N=512$, a design performing within $0.4$ dB from the RCU bound down to the block error rate of $10^{-6}$ under an SCL decoder with list size $L=1024$ is provided. The design is modified using the new guidelines so that the performance improves with practical list sizes, e.g., $Lin{8,32,128}$, outperforming 5G designs.
A polar-coded transmission (PCT) scheme with joint channel estimation and decoding is proposed for channels with unknown channel state information (CSI). The CSI is estimated via successive cancellation (SC) decoding and the constraints imposed by th
e frozen bits. SC list decoding with an outer code improves performance, including resolving a phase ambiguity when using quadrature phase-shift keying (QPSK) and Gray labeling. Simulations with 5G polar codes and QPSK show gains of up to $2$~dB at a frame error rate (FER) of $10^{-4}$ over pilot-assisted transmission for various non-coherent models. Moreover, PCT performs within a few tenths of a dB to a coherent receiver with perfect CSI. For Rayleigh block-fading channels, PCT outperforms an FER upper bound based on random coding and within one dB of a lower bound.
A product code with single parity-check component codes can be described via the tools of a multi-kernel polar code, where the rows of the generator matrix are chosen according to the constraints imposed by the product code construction. Following th
is observation, successive cancellation decoding of such codes is introduced. In particular, the error probability of single parity-check product codes over binary memoryless symmetric channels under successive cancellation decoding is characterized. A bridge with the analysis of product codes introduced by Elias is also established for the binary erasure channel. Successive cancellation list decoding of single parity-check product codes is then described. For the provided example, simulations over the binary input additive white Gaussian channel show that successive cancellation list decoding outperforms belief propagation decoding applied to the code graph. Finally, the performance of the concatenation of a product code with a high-rate outer code is investigated via distance spectrum analysis. Examples of concatenations performing within $0.7$ dB from the random coding union bound are provided.
The performance of short polar codes under successive cancellation (SC) and SC list (SCL) decoding is analyzed for the case where the decoder messages are coarsely quantized. This setting is of particular interest for applications requiring low-compl
exity energy-efficient transceivers (e.g., internet-of-things or wireless sensor networks). We focus on the extreme case where the decoder messages are quantized with 3 levels. We show how under SCL decoding quantized log-likelihood ratios lead to a large inaccuracy in the calculation of path metrics, resulting in considerable performance losses with respect to an unquantized SCL decoder. We then introduce two novel techniques which improve the performance of SCL decoding with coarse quantization. The first technique consists of a modification of the final decision step of SCL decoding, where the selected codeword is the one maximizing the maximum-likelihood decoding metric within the final list. The second technique relies on statistical knowledge about the reliability of the bit estimates, obtained through a suitably modified density evolution analysis, to improve the list construction phase, yielding a higher probability of having the transmitted codeword in the list. The effectiveness of the two techniques is demonstrated through simulations.
146 -
Mustafa Cemil Coc{s}kun
, Gianluigi Liva
, Alexandre Graell i Amat andn Michael Lentmaier
2017
We introduce successive cancellation (SC) decoding of product codes (PCs) with single parity-check (SPC) component codes. Recursive formulas are derived, which resemble the SC decoding algorithm of polar codes. We analyze the error probability of SPC
-PCs over the binary erasure channel under SC decoding. A bridge with the analysis of PCs introduced by Elias in 1954 is also established. Furthermore, bounds on the block error probability under SC decoding are provided, and compared to the bounds under the original decoding algorithm proposed by Elias. It is shown that SC decoding of SPC-PCs achieves a lower block error probability than Elias decoding.
