Complexity-Adaptive Maximum-Likelihood Decoding of Modified ${\mathbf{G}}_N$-Coset Codes

Abstract

A complexity-adaptive tree search algorithm is proposed for ${\mathbf{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 ${\mathbf{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.

arXiv commentAccepted for a presentation at ITW2021

References in corpus (7)

• LLR-based Successive Cancellation List Decoding of Polar Codes
• From sequential decoding to channel polarization and back again
• PAC Codes: Sequential Decoding vs List Decoding
• On Pre-transformed Polar Codes
• Polar Code Construction for List Decoding
• Performance of CRC Concatenated Pre-transformed RM-Polar Codes
• On the Weight Spectrum of Pre-Transformed Polar Codes