We present a new soft-decision majority decoding algorithm for Reed-Muller codes RM(r,m). First, the reliabilities of 2/sup m/ transmitted symbols are recalculated into the reliabilities of 2/sup m-r/ parity checks that represent each information bit. In turn, information bits are obtained by the weighted majority that gives more weight to more reliable parity checks. It is proven that for long low-rate codes RM(r,m), our soft-decision algorithm outperforms its conventional hard-decision counterpart by 10 log/sub 10/(/spl pi//2)/spl ap/2 dB at any given output error probability. For fixed code rate R and m/spl rarr//spl infin/, our algorithm increases almost 2/sup r/2/ times the correcting capability of soft-decision bounded distance decoding.

We can encode rare events with an overhead of about 1.56 bits/event. The contribution of the overhead to the total length of the code is negligible. The encoding and decoding time counted in operations over bits per bit of the code does not depend on the number of appearances of the events. We also present algorithms of the same speed which enumerate the pyramid cubic lattices with an overhead of about 1.56 bits/dimension. The overhead is the price for reaching the ultimate (to within a constant factor) encoding and decoding speed.

This correspondence shows that the known "add-half" rule is not asymptotically optimal for predicting the (n+1)st symbol after a sequence of n symbols, whereas the "add-/spl beta//sub 0/" rule, /spl beta//sub 0/=0.50922/spl middot//spl middot//spl middot/is.