Complexity-Adaptive Maximum-Likelihood Decoding of Modified G_N-Coset Codes

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.