List decoding of Reed-Muller codes up to the Johnson bound with almost linear complexity

摘要

A new deterministic list decoding algorithm is proposed for general Reed-Muller codes RM(s,m) of length n = 2^m and distance d = 2^m-epsi. Given n and d, the algorithm performs beyond the bounded distance threshold of d/2 and has a low complexity order of nm^epsi-1 for any decoding radius T that is less than the Johnson bound