A noise-adaptive algorithm for first-order Reed-Muller decoding

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 complementary code keying (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.2 dB in error rate. We show analytically that the error rate of our adaptive algorithm is 2^-Ω(n), where n is the length of a codeword.