Method and apparatus for MAP decoding of binary hamming codes and related error correction codes

摘要

A method and apparatus are disclosed for MAP decoding of signals encoded using error correction codes to make maximum probability decisions about each transmitted bit. A disclosed MAP decoding algorithm extends the work of Hartman and Rudolph and exploits properties of Hamming error correction codes to provide a decoding algorithm having a complexity that is proportional to n log n for Hamming codes. The invention computes a difference, rho, of the probabilities the that transmitted symbol was zero and one based on characteristics of the channel and then determines the product of the rhol values corresponding to non-zero positions of codewords of the dual code using real vector and F2[2]-vector fast Walsh-Hadamard transforms. The invention also processes all positions of all codewords to determine a sum for each position that indicates the reliability that a received bit is a given value for a given position using the real vector fast Walsh-Hadamard transforms.