Soft-decision decoding is considered for general Reed-Muller (RM) codes of length n and distance d used over a memoryless channel. A recursive decoding algorithm is designed and its decoding threshold is derived for long RM codes. The algorithm has complexity of order n ln n and corrects most error patterns of the Euclidean weight of order (n/ln n)^{1/2}, instead of the decoding threshold d^{1/2}/2 of the bounded distance decoding. Also, for long RM codes of fixed rate R, the new algorithm increases 4/pi times the decoding threshold of its hard-decision counterpart.

Let A (q, n, d) denote the maximum size of a q-ary code of length n and distance d. We study the minimum asymptotic redundancy rho(q, n, d) = n - log_(q) A(q, n, d) as n grows while q and d are fixed. For any d and q greater than or equal to d - 1, long algebraic codes are designed that improve on the Bose-Chaudhuri-Hocquenghem (BCH) codes and have the lowest asymptotic redundancy rho(q, n, d) less than or similar to ((d - 3) + 1/(d - 2)) log_(q)n known to date. Prior to this work, codes of fixed distance that asymptotically surpass BCH codes and the Gilbert-Varshamov bound were designed only for distances 4, 5, and 6.

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 n log n and corrects most error patterns of weight (d ln d)/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 p, which yields a vanishing output error probability on long codes. (c) 2005 Elsevier B.V. All rights reserved.

Recursive list decoding is considered for Reed-Muller (RM) codes. The algorithm repeatedly relegates itself to the shorter RM codes by recalculating the posterior probabilities of their symbols. Intermediate decodings are only performed when these recalculations reach the trivial RM codes. In turn, the updated lists of most plausible codewords are used in subsequent decodings. The algorithm is further improved by using permutation techniques on code positions and by eliminating the most error-prone information bits. Simulation results show that for all RM codes of length 256 and many subcodes of length 512, these algorithms approach maximum-likelihood (ML) performance within a margin of 0.1 dB. As a result, we present tight experimental bounds on ML performance for these codes.