Simple MAP Decoding of First Order Reed-Muller and Hamming Codes

A maximum a posteriori probability (MAP) decoder of a block code minimizes the probability of error for each transmitted symbol separately. The standard way of implementing MAP decoding of a linear code is the BCJR algorithm, which is based on a trellis representation of the code. The complexity of the BCJR algorithm for the first order Reed-Muller codes and Hamming codes is proportional to $n^2$, where $n$ is the code length. In the article we present new MAP decoding algorithms for binary and nonbinary first order Reed-Muller and Hamming codes. The proposed algorithms have complexities proportional to $q^2 nlog_q n$, where $q$ is the alphabet size. In particular, for the binary codes this yields complexity of order $sim n log n$.