Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

IEEE International Symposium on Information Theory (ISIT)

Efficient bounded distance decoders for Barnes-Wall lattices

Daniele Micciancio, Antonio R. Nicolosi

Published Jul 1, 2008• 23 citations
Publisher

Abstract

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.

DOI
10.1109/isit.2008.4595438

Related papers

On the decoding of Barnes-Wall lattices

Vincent Corlay, Joseph J. Boutros, Philippe Ciblat +1 more

We present new efficient recursive decoders for the Barnes-Wall lattices based on their squaring construction. The analysis of the new decoders reveals a quasi-quadratic complexity in the lattice dimension. The error rate is shown to be close to the universal lower bound in dimensions 64 and 128.

arXiv:2001.05907•IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2020•4 citations

Efficient decoding of the Gosset, Coxeter-Todd and the Barnes-Wall lattices

Moshe Ran, Jakov Snyders

Low complexity maximum-likelihood and bounded-distance soft decoding algorithms are presented for several block and lattice codes. The bounded-distance algorithms are based upon multilevel constructions of the codes. To demonstrate the approach, maximum-likelihood and bounded-distance decoders are devised for several well known codes and sphere packings in 8, 12 and 16 dimensions.

IEEE International Symposium on Information Theory (ISIT)•Nov 27, 2002•10 citations

Reduced Complexity Bounded-distance Decoding of the Leech Lattice

Ofer Amrani, Yair Be'ery, Alexander Vardy

A new efficient algorithm for bounded-distance decoding of the Leech lattice is presented. The algorithm decodes correctly at least up to the guaranteed error-correction radius of the Leech lattice. The proposed decoder is based on projecting the points of the Leech lattice onto the codewords of the (6, 3, 4) quarternary code, the hexacode H/sub 6/. Projection on the hexacode induces partition of the Leech lattice into four cosets of Q/sub 24/, beyond the conventional partition into two H/sub 24/ cosets. This enables bounded-distance decoding of the Leech lattice with only 1127 real operations in the worst case, as compared to about 3600 operations for the maximum-likelihood decoding of [9]. The proposed algorithm is at least 30% more efficient than Forney's algorithm [5] in terms of computational complexity, while the coding gain loss is no more than 0.05 dB (over BER ranging from 10/sup -1/ to 10/sup -6/ ).

IEEE International Symposium on Information Theory (ISIT)•Aug 24, 2005•0 citations

A Bounded-Distance Decoding Algorithm for Lattices Obtained from a Generalized Code Formula

M.A.O. da Costa e SiIva, Reginaldo Palazzo Júnior

A multistage decoding algorithm is given for lattices obtained from a generalized code formula. The corresponding multilevel construction is based on a chain of two-way lattice partitions and a family of binary linear block codes, whereas the multistage algorithm involves the use of a maximum-likelihood (ML) decoding algorithm for each two-way lattice partitions as well as a soft-decision ML decoding algorithm for each binary linear block code. The algorithm is shown to have the same effective error-correcting radius as ML decoding. Several known lattices and two new ones were then constructed by the generalized code formula. The trade-off between complexity reduction and performance loss achieved by the proposed algorithm is presented.

IEEE International Symposium on Information Theory (ISIT)•Aug 24, 2005•0 citations

Generalised minimum distance decoding of Reed-Muller codes and Barnes-Wall lattices

Chunxiang Wang, Ba-Zhong Shen, Kenneth K. Tzeng

Low complexity soft decision decoding algorithms for Reed-Muller codes and Barnes-Wall lattices are presented. These algorithms are constructed based on the usage of generalised minimum distance (GMD) decoding recursively. Evaluation of the algorithms on AWGN channel through computer simulation indicates a slight degradation in performance, compared to maximum likelihood decoding, but with considerable reduction in complexity.

IEEE International Symposium on Information Theory (ISIT)•Nov 19, 2002•4 citations

Even more efficient bounded-distance decoding of the hexacode, the Golay code, and the Leech lattice

Alexander Vardy

We present a new bounded-distance decoding algorithm for the hexacode, which requires at most 34 real operations in the worst case, as compared to 57 such operations in the best previously known decoder. The new algorithm is then employed for bounded-distance decoding of the Leech lattice and the Golay code. The error-correction radius of the resulting decoders is equal to that of a maximum-likelihood decoder. The resulting decoding complexity is at most 331 real operations for the Leech lattice and at most 121 operations for the Golay code. For all the three codes-the hexacode, the Golay code, and the Leech lattice-the proposed decoders are considerably more efficient than any decoder presently known.>

IEEE Transactions on Information Theory•Jan 1, 1995•37 citations
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.
A new efficient algorithm for bounded-distance decoding of the Leech lattice is presented. The algorithm decodes correctly at least up to the guaranteed error-correction radius of the Leech lattice. The proposed decoder is based on projecting the points of the Leech lattice onto the codewords of the (6, 3, 4) quarternary code, the hexacode H/sub 6/. Projection on the hexacode induces partition of the Leech lattice into four cosets of Q/sub 24/, beyond the conventional partition into two H/sub 24/ cosets. This enables bounded-distance decoding of the Leech lattice with only 1127 real operations in the worst case, as compared to about 3600 operations for the maximum-likelihood decoding of [9]. The proposed algorithm is at least 30% more efficient than Forney's algorithm [5] in terms of computational complexity, while the coding gain loss is no more than 0.05 dB (over BER ranging from 10/sup -1/ to 10/sup -6/ ).
A multistage decoding algorithm is given for lattices obtained from a generalized code formula. The corresponding multilevel construction is based on a chain of two-way lattice partitions and a family of binary linear block codes, whereas the multistage algorithm involves the use of a maximum-likelihood (ML) decoding algorithm for each two-way lattice partitions as well as a soft-decision ML decoding algorithm for each binary linear block code. The algorithm is shown to have the same effective error-correcting radius as ML decoding. Several known lattices and two new ones were then constructed by the generalized code formula. The trade-off between complexity reduction and performance loss achieved by the proposed algorithm is presented.
We present a new bounded-distance decoding algorithm for the hexacode, which requires at most 34 real operations in the worst case, as compared to 57 such operations in the best previously known decoder. The new algorithm is then employed for bounded-distance decoding of the Leech lattice and the Golay code. The error-correction radius of the resulting decoders is equal to that of a maximum-likelihood decoder. The resulting decoding complexity is at most 331 real operations for the Leech lattice and at most 121 operations for the Golay code. For all the three codes-the hexacode, the Golay code, and the Leech lattice-the proposed decoders are considerably more efficient than any decoder presently known.>