Skip to main content
Open Access Publications from the University of California

UC Riverside

UC Riverside Previously Published Works bannerUC Riverside

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 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. 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.

Many UC-authored scholarly publications are freely available on this site because of the UC's open access policies. Let us know how this access is important for you.

Main Content
For improved accessibility of PDF content, download the file to your device.
Current View