Fast Decoding of the p-Ary First-Order Reed-Muller Codes Based on Jacket Transform

摘要

We propose a fast decoding algorithm for the p-ary first-order Reed-Muller code guaranteeing correction of up to n/4 sin 「(p-1/2p)π」 errors and having complexity proportional to n log n, where n = p~m is the code length and p is an odd prime. This algorithm is an extension in the complex domain of the fast Hadamard transform decoding algorithm applicable to the binary case.