Recursive Decoding and Its Performance for Low-Rate Reed-Muller Codes

Abstract

Recursive decoding techniques are considered for Reed-Muller (RM) codes of growing length $n$ and fixed order $r.$ An algorithm is designed that has complexity of order $n\log n$ and corrects most error patterns of weight up to $n(1/2-\epsilon )$ given that $\epsilon$ exceeds $n^{-1/2^r}.$ This improves the asymptotic bounds known for decoding RM codes with nonexponential complexity.