Patent ID: 8245116

Claim:
A method for performing soft decision decoding of a codeword of a Euclidean a space Reed-Muller (RM) code, wherein a code RM(r, m) of order r and a codeword of length 2 m is a set of all binary vectors associated with coefficients of a Boolean polynomial with m variables, and whose terms are composed of monomials of degree r, comprising the steps of: selecting an optimal decomposition variable i using a likelihood calculation; expressing the code RM(r, m) as {(u, uv)|uεRM(r, m−1) and vεRM(r−1, m−1)}, where uv denotes a component-wise multiplication of u and v, and (u, uv)=(r 1 , r 2 ); separating receive codeword into r 1 =u and r 2 =uv based on the optimal decomposition variable; decoding r 2 , according to the optimal decomposition variable, using a RM(r−1, m−1) decoder to obtain a decoded v and a first set of decoded bits; combining the decoded v with r 1 using (r 1 +r 2 v)/2; and decoding (r 1 +r 2 v)/2 using a RM(r, m−1) decoder to obtain a decoded u and a second set of decoded bits, wherein the steps are performed in a processor.