Recursive decoding and its performance for low-rate Reed-Muller codes

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.

I. Introduction

IN this paper, our goal is to design new decoding algorithms that can enhance techniques known to date for Reed–Muller (RM) codes. In general, RM codes can be designed from the set of all -variate Boolean polynomials of degree or less. Here each polynomial is defined on the -dimensional space . For any , we consider the sequence of binary values obtained as argument runs through . These sequences—codewords —form an RM code, which is below denoted and has length , dimension , and distance as follows: $$n=2^{m},\quad k=\sum_{i=0}^{r} {m \choose i},\quad d=2^{m-r}.$$ The decoding algorithms discussed in this paper (including the new algorithms) can be applied to any RM code. However, we will mostly focus on their asymptotic performance obtained for long RM codes of fixed order . To define their error-correcting performance, we use the following definition. Given an infinite sequence of codes , we say that a decoding algorithm has a sequence and a sequence if for •

correctly decodes all but a vanishing fraction of error patterns of weight or less;

•

fails to decode a nonvanishing fraction of error patterns of weight or less.¹

Note that multiple sequences with can satisfy the same definition.