List decoding of Reed-Muller codes up to the Johnson bound with almost linear complexity
Ilya I. Dumer, Grigory A. Kabatiansky, Cédric Tavernier · 2006
A new deterministic list decoding algorithm is proposed for general Reed-Muller codes RM(s,m) of length n = 2mand distance d = 2m-epsi. Given n and d, the algorithm performs beyond the bounded distance threshold of d/2 and has a low complexity order of nmepsi-1for any decoding radius T that is less than the Johnson bound