Recursive decoding for Reed-Muller codes and their modifications

Recursive decoding techniques are considered for Reed-Muller (RM) codes of growing length and their subcodes. Using this approach, a decoding algorithm is designed that has complexity of order n log n and outperforms other algorithms with nonexponential complexity known for RM codes.; To evaluate decoding capability, a probabilistic technique that analysis decoding as a sequence of recursive steps is developed. However dependent, different decoding steps can be tightly approximated by independent events that occur given that all preceding decodings are correct. This technique provides insight into the decoding process and locates the least protected information bits.; The enhanced versions of the basic recursive algorithms are also discussed. These make use of short code lists, permutation techniques, and pruning the most error-prone information bits. Extensive simulation results are provided. They show that by combining these enhancements it is possible to achieve maximum-likelihood performance for the considered codes of length up to 512.