This paper descibes a new low complexity maximum likelihood decoder for 2nd order reed-Muller codes. The new decoder exploits the algebraic structure of the code and the relationship of the code with the Hadamard transform. For an (n,k;d) binary block code, a brute force ML decoder requires 2 sup k*(n-1) adds and 2 sup k-1 compares. In general, there is no better way to do ML decoding. We consider the (32,16;8) RM2 code in detail. Usig our decoder, there is a reduction in the number of computations by a factor of 29 with respect to a brute force method. The only downside is that our decoder requires some storage. In addition to RM2 codes, our decoder also works for Kerdock codes, which form a class of nonlinear codes sandwiched between 1st order and 2nd order reed-muller codes.
展开▼
机译：本文描述了一种用于二阶里德-穆勒码的新型低复杂度最大似然解码器。新的解码器利用代码的代数结构以及代码与Hadamard变换之间的关系。对于（n，k; d）个二进制块代码，蛮力ML解码器需要2 sup k *（n-1）加和2 sup k-1比较。通常，没有更好的方法来进行ML解码。我们将详细考虑（32,16; 8）RM2代码。使用我们的解码器，相对于蛮力法，计算数量减少了29倍。唯一的缺点是我们的解码器需要一些存储空间。除RM2码外，我们的解码器还适用于Kerdock码，该码形成了一类介于一阶和二阶里德-穆勒码之间的非线性码。
展开▼
