Efficient bounded distance decoders for Barnes-Wall lattices
Daniele Micciancio, Antonio R. Nicolosi · 2008
We describe a new family of parallelizable bounded distance decoding algorithms for the Barnes-Wall lattices, and analyze their decoding complexity. The algorithms are parameterized by the number p = 4kles N2of available processors, work for Barnes-Wall lattices in arbitrary dimension N = 2n, correct any error up to squared unique decoding radius d2min/ A, and run in worst- case time O (Nlog2N/radic(p)). Depending on the value of the parameter p, this yields efficient decoding algorithms ranging from a fast sequential algorithm with quasi- linear decoding complexity O(N log2N), to a fully parallel decoding circuit with polylogarithmic depth O(log2N) and polynomially many arithmetic gates.