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

arXiv:2001.05907 · IEEE International Symposium on Information Theory (ISIT)

On the decoding of Barnes-Wall lattices

Vincent Corlay, Joseph J. Boutros, Philippe Ciblat, Loïc Brunel

Published Jun 1, 2020• 4 citations
arXivHTMLPDF

Abstract

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.
DOI
10.1109/isit44484.2020.9173976

Related papers

Efficient bounded distance decoders for Barnes-Wall lattices

Daniele Micciancio, Antonio R. Nicolosi

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.

IEEE International Symposium on Information Theory (ISIT)•Jul 1, 2008•23 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

A new framework for building and decoding group codes.

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

This paper investigates the construction and the decoding of a remarkable set of lattices and codes viewed as group codes: We treat in a unified framework the Leech lattice and the Golay code in dimension 24, the Nebe lattice in dimension 72, the Barnes-Wall lattices, and the Reed-Muller codes. We also present a new family of lattices called the parity lattices. The common aspect of these group codes is that they can be obtained as single parity-check $k$-groups or via the $k$-ing construction. We exploit these constructions to introduce a new efficient paradigm for decoding. This leads to efficient list decoders and quasi-optimal decoders on the Gaussian channel. Both theoretical and practical performance (point error probability and complexity) of the new decoders are provided.

•Dec 12, 2020•1 citation

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

Practical Encoders and Decoders for Euclidean Codes from Barnes-Wall Lattices

J. Harshan, Emanuele Viterbo, J.-C. Belfiore

We address the application of Barnes-Wall (BW) lattice codes for communication over additive white Gaussian noise (AWGN) channels. We introduce Construction A^prime of complex BW lattices that makes new connection between linear codes over polynomial rings and lattices. We show that Construction A^prime of BW lattices is equivalent to the multilevel construction from Reed-Muller codes proposed by Forney. To decode the BW lattice code, we adapt the low-complexity sequential BW lattice decoder (SBWD) proposed by Micciancio and Nicolosi. First we study the error performance of SBWD for decoding the infinite lattice, and demonstrate that it is powerful in making correct decisions well beyond the packing radius. Subsequently, we use the SBWD to decode lattice codes through a novel noise trimming technique, where the received vector is appropriately scaled before applying the SBWD. We show that the noise trimming technique is most effective for decoding BW lattice codes in smaller dimensions, while the gain diminishes for decoding codes in larger dimensions.

arXiv:1203.3282•IEEE Transactions on Communications•Oct 7, 2013•17 citations

Symplectic Barnes-Wall GKP Codes: Deterministic $O(N \log^2 N)$ Decoding and Logarithmic Rate Scaling

Shanxiang Lyu

We construct an explicit symplectic realization of the Barnes-Wall lattice that yields a family of multimode Gottesman-Kitaev-Preskill (GKP) codes with encoding rate $R = \frac{1}{2}\log_2 N$ and a deterministic $O(N\log^2 N)$ bounded-distance decoder. The recursive generator $G_{m+1} = \bigl(\begin{smallmatrix} G_m & 0 \\ G_m & R_m G_m \end{smallmatrix}\bigr)$ with $R_m = I + Ω$ simultaneously guarantees symplectic integrality for valid quantum stabilizers and preserves the exact Barnes-Wall decoding structure through a chain of isometric isomorphisms. The code distance is constant at $Δ^2 = 1$ (in units of $2π$), representing an explicit distance--rate tradeoff in which logarithmic encoding efficiency is achieved at the cost of non-scaling protection. This construction provides a deterministic, space-efficient paradigm for GKP error correction in platforms supporting non-local modular connectivity.

cs.ITCross-listedarXiv:2608.00601•Aug 4, 2026•0 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.
This paper investigates the construction and the decoding of a remarkable set of lattices and codes viewed as group codes: We treat in a unified framework the Leech lattice and the Golay code in dimension 24, the Nebe lattice in dimension 72, the Barnes-Wall lattices, and the Reed-Muller codes. We also present a new family of lattices called the parity lattices. The common aspect of these group codes is that they can be obtained as single parity-check kkk-groups or via the kkk-ing construction. We exploit these constructions to introduce a new efficient paradigm for decoding. This leads to efficient list decoders and quasi-optimal decoders on the Gaussian channel. Both theoretical and practical performance (point error probability and complexity) of the new decoders are provided.
We address the application of Barnes-Wall (BW) lattice codes for communication over additive white Gaussian noise (AWGN) channels. We introduce Construction A^prime of complex BW lattices that makes new connection between linear codes over polynomial rings and lattices. We show that Construction A^prime of BW lattices is equivalent to the multilevel construction from Reed-Muller codes proposed by Forney. To decode the BW lattice code, we adapt the low-complexity sequential BW lattice decoder (SBWD) proposed by Micciancio and Nicolosi. First we study the error performance of SBWD for decoding the infinite lattice, and demonstrate that it is powerful in making correct decisions well beyond the packing radius. Subsequently, we use the SBWD to decode lattice codes through a novel noise trimming technique, where the received vector is appropriately scaled before applying the SBWD. We show that the noise trimming technique is most effective for decoding BW lattice codes in smaller dimensions, while the gain diminishes for decoding codes in larger dimensions.
Symplectic Barnes-Wall GKP Codes: Deterministic O(Nlog⁡2N)O(N \log^2 N)O(Nlog2N) Decoding and Logarithmic Rate Scaling
We construct an explicit symplectic realization of the Barnes-Wall lattice that yields a family of multimode Gottesman-Kitaev-Preskill (GKP) codes with encoding rate R=12log⁡2NR = \frac{1}{2}\log_2 NR=21​log2​N and a deterministic O(Nlog⁡2N)O(N\log^2 N)O(Nlog2N) bounded-distance decoder. The recursive generator Gm+1=(Gm0GmRmGm)G_{m+1} = \bigl(\begin{smallmatrix} G_m & 0 \\ G_m & R_m G_m \end{smallmatrix}\bigr)Gm+1​=(Gm​Gm​​0Rm​Gm​​) with Rm=I+ΩR_m = I + ΩRm​=I+Ω simultaneously guarantees symplectic integrality for valid quantum stabilizers and preserves the exact Barnes-Wall decoding structure through a chain of isometric isomorphisms. The code distance is constant at Δ2=1Δ^2 = 1Δ2=1 (in units of 2π2π2π), representing an explicit distance--rate tradeoff in which logarithmic encoding efficiency is achieved at the cost of non-scaling protection. This construction provides a deterministic, space-efficient paradigm for GKP error correction in platforms supporting non-local modular connectivity.