| 摘要 |
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 MAP decoding algorithm is disclosed that exploits properties of Reed-Muller error correction codes to provide a decoding algorithm having a complexity that is proportional to n log n for Reed-Muller codes. The disclosed MAP decoding algorithm employs two matrices D and {overscore (D to represent the code set and has an overall complexity that is exponential for a general code set. For Reed-Muller codes, the disclosed MAP decoding algorithm employs matrices Bi and {overscore (Bi that are sparse matrices (i.e., contain many zero entries), thereby reducing the number of required operations and yielding a complexity that is proportional to n log n. In addition, the disclosed MAP decoding algorithm permits faster decoding by permitting a parallel implementation having a critical path length that is proportional to 2 log n for Reed-Muller codes.
|
