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)

Low-Complexity Multilevel LDPC Lattices and a Generalization of Construction D'

Paulo Ricardo Branco da Silva, Danilo Silva

Published Jun 1, 2018• 2 citations
Publisher

Abstract

We propose efficient encoding and decoding algorithms for Construction D` multilevel LDPC lattices whose complexity is linear in the total number of coded bits. Moreover, we propose a generalization of Construction D ` that relaxes some of the nesting constraints on 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 lattice decoding is comparable to that of polar lattices on the power-unconstrained AWGN channel.

DOI
10.1109/isit.2018.8437928

Related papers

Low-Complexity Multilevel LDPC Lattices and a a Generalization of Construction $\mathrm{D}^{\prime}$

Paulo Ricardo Branco da Silva, Danilo Silva

We propose efficient encoding and decoding algorithms for Construction $\mathrm{D}$ ‘ multilevel LDPC lattices whose complexity is linear in the total number of coded bits. Moreover, we propose a generalization of Construction $\mathrm{D}$ ‘ that relaxes some of the nesting constraints on 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 lattice decoding is comparable to that of polar lattices on the power-unconstrained AWGN channel.

IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2018•0 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•20 citations

Low-Density Parity-Check Lattices: Construction and Decoding Analysis

Mohammad‐Reza Sadeghi, Amir H. Banihashemi, Daniel Panario

Low-density parity-check codes (LDPC) can have an impressive performance under iterative decoding algorithms. In this paper we introduce a method to construct high coding gain lattices with low decoding complexity based on LDPC codes. To construct such lattices we apply Construction D', due to Bos, Conway, and Sloane, to a set of parity checks defining a family of nested LDPC codes. For the decoding algorithm, we generalize the application of max-sum algorithm to the Tanner graph of lattices. Bounds on the decoding complexity are derived and our analysis shows that using LDPC codes results in low decoding complexity for the proposed lattices. The progressive edge growth (PEG) algorithm is then extended to construct a class of nested regular LDPC codes which are in turn used to generate low density parity check lattices. Using this approach, a class of two-level lattices is constructed. The performance of this class improves when the dimension increases and is within 3 dB of the Shannon limit for error probabilities of about 10-6. This is while the decoding complexity is still quite manageable even for dimensions of a few thousands

IEEE Transactions on Information Theory•Sep 29, 2006•95 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

Iterative decoding algorithm of lattices

Mohammad‐Reza Sadeghi, Amir H. Banihashemi, Daniel Panario

The so-called min-sum algorithm for iterative decoding of low-density parity-check (LDPC) codes is generalized to decode lattices. An upper bound on the decoding complexity per iteration is derived, and for LDPC lattices constructed by Construction D' and using a nested sequence of LDPC codes, exact values for computational complexity are also given. We show that iterative decoding of LDPC lattices has a reasonably low complexity such that lattices with dimensions of a few thousands can be easily decoded.

Conference proceedings - Canadian Conference on Electrical and Computer Engineering•Nov 12, 2004•5 citations

Construction of lattices from LDPC codes

Mohammad‐Reza Sadeghi, Banihashemit AH, Daniel Panario

Low-density parity-check (LDPC) codes can have a good performance under iterative decoding algorithms. This idea is used to construct a class of lattices with relatively high coding gain and low decoding complexity. To construct such lattices, Construction D' is applied to the set of parity check vectors of a class of nested LDPC codes. Bounds on the minimum distance and the coding gain of the corresponding lattice are provided. We also provide a practical way of finding the cross sections of the lattice given the parity check matrix of a lattice. The progressive edge growth algorithm is extended and is used to construct a class of nested binary codes to generate the corresponding lattice. Simulation results confirm the good performance of this class of lattice.

Conference proceedings - Canadian Conference on Electrical and Computer Engineering•Nov 12, 2004•2 citations
We propose efficient encoding and decoding algorithms for Construction Dmultilevel LDPC lattices whose complexity is linear in the total number of coded bits. Moreover, we propose a generalization of Construction D that relaxes some of the nesting constraints on 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 lattice decoding is comparable to that of polar lattices on the power-unconstrained AWGN channel.
Low-Complexity Multilevel LDPC Lattices and a a Generalization of Construction D′\mathrm{D}^{\prime}D′
We propose efficient encoding and decoding algorithms for Construction D\mathrm{D}D ‘ multilevel LDPC lattices whose complexity is linear in the total number of coded bits. Moreover, we propose a generalization of Construction D\mathrm{D}D ‘ that relaxes some of the nesting constraints on 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 lattice decoding is comparable to that of polar lattices on the power-unconstrained AWGN channel.
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.
Low-density parity-check codes (LDPC) can have an impressive performance under iterative decoding algorithms. In this paper we introduce a method to construct high coding gain lattices with low decoding complexity based on LDPC codes. To construct such lattices we apply Construction D', due to Bos, Conway, and Sloane, to a set of parity checks defining a family of nested LDPC codes. For the decoding algorithm, we generalize the application of max-sum algorithm to the Tanner graph of lattices. Bounds on the decoding complexity are derived and our analysis shows that using LDPC codes results in low decoding complexity for the proposed lattices. The progressive edge growth (PEG) algorithm is then extended to construct a class of nested regular LDPC codes which are in turn used to generate low density parity check lattices. Using this approach, a class of two-level lattices is constructed. The performance of this class improves when the dimension increases and is within 3 dB of the Shannon limit for error probabilities of about 10-6. This is while the decoding complexity is still quite manageable even for dimensions of a few thousands
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.
The so-called min-sum algorithm for iterative decoding of low-density parity-check (LDPC) codes is generalized to decode lattices. An upper bound on the decoding complexity per iteration is derived, and for LDPC lattices constructed by Construction D' and using a nested sequence of LDPC codes, exact values for computational complexity are also given. We show that iterative decoding of LDPC lattices has a reasonably low complexity such that lattices with dimensions of a few thousands can be easily decoded.
Low-density parity-check (LDPC) codes can have a good performance under iterative decoding algorithms. This idea is used to construct a class of lattices with relatively high coding gain and low decoding complexity. To construct such lattices, Construction D' is applied to the set of parity check vectors of a class of nested LDPC codes. Bounds on the minimum distance and the coding gain of the corresponding lattice are provided. We also provide a practical way of finding the cross sections of the lattice given the parity check matrix of a lattice. The progressive edge growth algorithm is extended and is used to construct a class of nested binary codes to generate the corresponding lattice. Simulation results confirm the good performance of this class of lattice.