TY - GEN
T1 - Efficient bounded distance decoders for Barnes-Wall lattices
AU - Micciancio, Daniele
AU - Nicolosi, Antonio
PY - 2008
Y1 - 2008
N2 - 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 = Ak ≤ N 2 of available processors, work for Barnes-Wall lattices in arbitrary dimension N = 2n, correct any error up to squared unique decoding radius dmin2/4, and run in worstcase time O (N log 2 N/√p). Depending on the value of the parameter p, this yields efficient decoding algorithms ranging from a fast sequential algorithm with quasilinear decoding complexity O(N log2 N), to a fully parallel decoding circuit with polylogarithmic depth O(log2 N) and polynomially many arithmetic gates.
AB - 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 = Ak ≤ N 2 of available processors, work for Barnes-Wall lattices in arbitrary dimension N = 2n, correct any error up to squared unique decoding radius dmin2/4, and run in worstcase time O (N log 2 N/√p). Depending on the value of the parameter p, this yields efficient decoding algorithms ranging from a fast sequential algorithm with quasilinear decoding complexity O(N log2 N), to a fully parallel decoding circuit with polylogarithmic depth O(log2 N) and polynomially many arithmetic gates.
UR - http://www.scopus.com/inward/record.url?scp=52349103414&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=52349103414&partnerID=8YFLogxK
U2 - 10.1109/ISIT.2008.4595438
DO - 10.1109/ISIT.2008.4595438
M3 - Conference contribution
AN - SCOPUS:52349103414
SN - 9781424422579
T3 - IEEE International Symposium on Information Theory - Proceedings
SP - 2484
EP - 2488
BT - Proceedings - 2008 IEEE International Symposium on Information Theory, ISIT 2008
T2 - 2008 IEEE International Symposium on Information Theory, ISIT 2008
Y2 - 6 July 2008 through 11 July 2008
ER -