Recursive error correction for general Reed–Muller codes

Reed–Muller (RM) codes of growing length n and distance d   are considered over a binary symmetric channel. A recursive decoding algorithm is designed that has complexity of order nlognnlogn and corrects most error patterns of weight (dlnd)/2(dlnd)/2. The presented algorithm outperforms other algorithms with nonexponential decoding complexity, which are known for RM codes. We evaluate code performance using a new probabilistic technique that disintegrates decoding into a sequence of recursive steps. This allows us to define the most error-prone information symbols and find the highest transition error probability pp, which yields a vanishing output error probability on long codes.