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 nlogn and corrects most error patterns of weight up to n(1/2-/spl epsiv/) given that /spl epsiv/ exceeds n/sup -1/2r/. This improves the asymptotic bounds known for decoding RM codes with nonexponential complexity. To evaluate decoding capability, we develop a probabilistic technique that disintegrates decoding into a sequence of recursive steps. Although dependent, subsequent outputs can be tightly evaluated under the assumption that all preceding decodings are correct. In turn, this allows us to employ second-order analysis and find the error weights for which the decoding error probability vanishes on the entire sequence of decoding steps as the code length n grows.