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:1203.3282 · IEEE Transactions on Communications

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

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

Published Oct 7, 2013• 17 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1109/tcomm.2013.100213.130018

Related papers

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

Multilevel LDPC Lattices With Efficient Encoding and Decoding and a Generalization of Construction $\text{D}'$

Paulo Ricardo Branco da Silva, Danilo Silva

Lattice codes are elegant and powerful structures that not only achieve the capacity of the additive white Gaussian noise (AWGN) channel but are also a key ingredient to many multiterminal schemes that exploit linearity properties. However, constructing lattice codes that can realize these benefits with low complexity is still a challenging problem. In this paper, efficient encoding and decoding algorithms are proposed for multilevel binary low-density parity-check (LDPC) lattices constructed via Construction D' whose complexity is linear in the total number of coded bits. Moreover, a generalization of Construction D' is proposed, which relaxes some of the nesting constraints on the parity-check matrices of the component codes, leading to a simpler and improved design. Based on this construction, low-complexity multilevel LDPC lattices are designed whose performance under multistage decoding is comparable to that of polar lattices and close to that of low-density lattice codes on the power-unconstrained AWGN channel.

arXiv:1712.08201•IEEE Transactions on Information Theory•Nov 23, 2018•18 citations

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

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

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
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.
Multilevel LDPC Lattices With Efficient Encoding and Decoding and a Generalization of Construction D′\text{D}'D′
Lattice codes are elegant and powerful structures that not only achieve the capacity of the additive white Gaussian noise (AWGN) channel but are also a key ingredient to many multiterminal schemes that exploit linearity properties. However, constructing lattice codes that can realize these benefits with low complexity is still a challenging problem. In this paper, efficient encoding and decoding algorithms are proposed for multilevel binary low-density parity-check (LDPC) lattices constructed via Construction D' whose complexity is linear in the total number of coded bits. Moreover, a generalization of Construction D' is proposed, which relaxes some of the nesting constraints on the parity-check matrices of the component codes, leading to a simpler and improved design. Based on this construction, low-complexity multilevel LDPC lattices are designed whose performance under multistage decoding is comparable to that of polar lattices and close to that of low-density lattice codes on the power-unconstrained AWGN channel.
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.