Method for performing soft decision decoding of Euclidean space Reed-Muller codes
View Patent ↗Soft decision decoding of a codeword of a Reed-Muller (RM) code by selecting an optimal decomposition variable i using a likelihood calculation. A code RM(r, m) is expressed 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 ). A receive codeword is separated into r 1 =u and r 2 =uv based on the optimal decomposition variable, and r 2 is decoded 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. The decoded v is combined with r 1 using (r 1 +r 2 v)/2, and (r 1 +r 2 v)/2 is decoded using a RM(r, m−1) decoder to obtain a decoded u and a second set of decoded bits.
1. 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.
2. The method of claim 1 , wherein the selecting determines a log likelihood ratio of v, and uses absolute and maximum operations.
3. The method of claim 1 , wherein the selecting uses a sum operation.
4. The method of claim 1 , wherein the selecting uses a minimum operation.
5. The method of claim 1 , wherein the decoding of the RM(1, m) code uses a Hadamard transform to obtain a maximum likelihood (ML) estimate of a transmitted codeword.
6. The method of claim 5 , wherein the decoding of the RM(1, m) code uses a list Hadamard transform for a plurality of most likely decoded v.
7. The method of claim 1 , wherein a RM(m, m) code is decoded by a matrix inversion.
8. The method of claim 5 , wherein a RM(1, m) code is decoded using the Hadamard transform to obtain a Maximum A Posteriori (MAP) estimate of the transmitted information bit in the codeword.
9. The method of claim 7 , further comprising:
determining the likelihood of each codeword based on received vector, decoding the RM(m, m) code using the matrix inversion to obtain a Maximum A Posteriori (MAP) estimate of a transmitted information bit in the codeword.
10. The method of claim 9 , further comprising:
determining a probability of valid codewords based on the MAP estimate of the transmitted information bit at an output of the RM(r−1, m−1) decoder; and
selecting a most likely codeword from the output of the RM(r−1, m−1) to combine with r 1 .
11. The method of claim 10 , further comprising:
determining the MAP estimate of the information bit using a weight sum operation.