A Noise-Adaptive Strategy for First-Order Reed-Muller Decoding

by Jon Feldman, Ibrahim Abou-Faycal, and Matteo Frigo.

IEEE Semiannual Vehicular Technology Conference, Fall 2002
[Full text]


We consider the problem of decoding First-Order Reed-Muller codes efficiently. We give an algorithm that implicitly adapts to the noise conditions, runs significantly faster than known maximum-likelihood algorithms, and yields an error rate that is very close to optimal. When applied to CCK demodulation (used in the 802.11b standard for Wireless Local Area Networks), the algorithm runs up to 4 times faster than a decoder based on the Fast Hadamard Transform, with a loss of at most 0.2dB in error rate. We show analytically that the error rate of our adaptive algorithm is 2^-Omega(n), where n is the length of a codeword.

This page maintained by: Matteo Frigo. Last updated: Sun Jun 21 09:29:38 2009