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

Conference proceedings - Canadian Conference on Electrical and Computer Engineering

Construction of lattices from LDPC codes

Mohammad‐Reza Sadeghi, Banihashemit AH, Daniel Panario

Published Nov 12, 2004• 2 citations
Publisher

Abstract

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.

DOI
10.1109/ccece.2004.1349661

Related papers

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

Irregular low-density parity-check lattices

Ihn-Jung Baik, Sae-Young Chung

We construct lattices with high coding gains based on nested low-density parity-check (LDPC) codes by Construction D′.We generalize the LDPC lattices [1] to have irregular degrees and call them irregular LDPC lattices. To construct good irregular LDPC lattices, we optimize the degree distributions by using density evolution and a modified sequential quadratic programming (SQP) and show our optimized irregular LDPC lattice has a threshold 0.48dB from the capacity, which is about 0.6dB better than the regular one in [1]. To construct a Tanner graph corresponding to LDPC lattices, we generalize the progressive-edge growth (PEG) algorithm and show a lower bound on the girth of the graph. Simulation is performed using the sum-product algorithm. Also, we compare the performance of joint decoding and multi-stage decoding [2] and show the advantage of joint decoding.

IEEE International Symposium on Information Theory (ISIT)•Jul 1, 2008•13 citations

Low-density parity-check codes based on finite geometries: a rediscovery and new results

Y. Kou, Shu Lin, M.P.C. Fossorier

This paper presents a geometric approach to the construction of low-density parity-check (LDPC) codes. Four classes of LDPC codes are constructed based on the lines and points of Euclidean and projective geometries over finite fields. Codes of these four classes have good minimum distances and their Tanner (1981) graphs have girth 6. Finite-geometry LDPC codes can be decoded in various ways, ranging from low to high decoding complexity and from reasonably good to very good performance. They perform very well with iterative decoding. Furthermore, they can be put in either cyclic or quasi-cyclic form. Consequently, their encoding can be achieved in linear time and implemented with simple feedback shift registers. This advantage is not shared by other LDPC codes in general and is important in practice. Finite-geometry LDPC codes can be extended and shortened in various ways to obtain other good LDPC codes. Several techniques of extension and shortening are presented. Long extended finite-geometry LDPC codes have been constructed and they achieve a performance only a few tenths of a decibel away from the Shannon theoretical limit with iterative decoding.

IEEE Transactions on Information Theory•Jan 1, 2001•1,303 citations

Low Density Parity Check Codes Based on Finite Geometries: A Rediscovery and More

Yu Kou, Shu Lin, M.P.C. Fossorier

Low density parity check (LDPC) codes with iterative decoding based on belief propagation achieve astonishing error performance close to Shannon limit. No algebraic or geometric method for constructing these codes has been reported and they are largely generated by computer search. As a result, encoding of long LDPC codes is in general very complex. This paper presents two classes of high rate LDPC codes whose constructions are based on finite Euclidean and projective geometries, respectively. These classes of codes a.re cyclic and have good constraint parameters and minimum distances. Cyclic structure adows the use of linear feedback shift registers for encoding. These finite geometry LDPC codes achieve very good error performance with either soft-decision iterative decoding based on belief propagation or Gallager's hard-decision bit flipping algorithm. These codes can be punctured or extended to obtain other good LDPC codes. A generalization of these codes is also presented.

•Oct 20, 1999•89 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

Iterative Construction of Regular LDPC Codes from Independent Tree-Based Minimum Distance Bounds

Eric T. Psota, Lance C. Pérez

An independent tree-based method for lower bounding the minimum distance of low-density parity-check (LDPC) codes is presented. This lower-bound is then used as the decision criterion during the iterative construction of regular LDPC codes. The new construction algorithm results in LDPC codes with greater girth and improved minimum-distance bounds when compared to regular LDPC codes constructed using the progressive edge-growth (PEG) construction and the approximate cycle extrinsic message degree (ACE)-constrained PEG construction. Simulation results of codes constructed with the new method show improved performance on the additive white Gaussian noise channel at moderate signal-to-noise ratios.

IEEE Communications Letters•Jan 21, 2011•5 citations
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.
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
We construct lattices with high coding gains based on nested low-density parity-check (LDPC) codes by Construction D′.We generalize the LDPC lattices [1] to have irregular degrees and call them irregular LDPC lattices. To construct good irregular LDPC lattices, we optimize the degree distributions by using density evolution and a modified sequential quadratic programming (SQP) and show our optimized irregular LDPC lattice has a threshold 0.48dB from the capacity, which is about 0.6dB better than the regular one in [1]. To construct a Tanner graph corresponding to LDPC lattices, we generalize the progressive-edge growth (PEG) algorithm and show a lower bound on the girth of the graph. Simulation is performed using the sum-product algorithm. Also, we compare the performance of joint decoding and multi-stage decoding [2] and show the advantage of joint decoding.
This paper presents a geometric approach to the construction of low-density parity-check (LDPC) codes. Four classes of LDPC codes are constructed based on the lines and points of Euclidean and projective geometries over finite fields. Codes of these four classes have good minimum distances and their Tanner (1981) graphs have girth 6. Finite-geometry LDPC codes can be decoded in various ways, ranging from low to high decoding complexity and from reasonably good to very good performance. They perform very well with iterative decoding. Furthermore, they can be put in either cyclic or quasi-cyclic form. Consequently, their encoding can be achieved in linear time and implemented with simple feedback shift registers. This advantage is not shared by other LDPC codes in general and is important in practice. Finite-geometry LDPC codes can be extended and shortened in various ways to obtain other good LDPC codes. Several techniques of extension and shortening are presented. Long extended finite-geometry LDPC codes have been constructed and they achieve a performance only a few tenths of a decibel away from the Shannon theoretical limit with iterative decoding.
Low density parity check (LDPC) codes with iterative decoding based on belief propagation achieve astonishing error performance close to Shannon limit. No algebraic or geometric method for constructing these codes has been reported and they are largely generated by computer search. As a result, encoding of long LDPC codes is in general very complex. This paper presents two classes of high rate LDPC codes whose constructions are based on finite Euclidean and projective geometries, respectively. These classes of codes a.re cyclic and have good constraint parameters and minimum distances. Cyclic structure adows the use of linear feedback shift registers for encoding. These finite geometry LDPC codes achieve very good error performance with either soft-decision iterative decoding based on belief propagation or Gallager's hard-decision bit flipping algorithm. These codes can be punctured or extended to obtain other good LDPC codes. A generalization of these codes is also 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.
An independent tree-based method for lower bounding the minimum distance of low-density parity-check (LDPC) codes is presented. This lower-bound is then used as the decision criterion during the iterative construction of regular LDPC codes. The new construction algorithm results in LDPC codes with greater girth and improved minimum-distance bounds when compared to regular LDPC codes constructed using the progressive edge-growth (PEG) construction and the approximate cycle extrinsic message degree (ACE)-constrained PEG construction. Simulation results of codes constructed with the new method show improved performance on the additive white Gaussian noise channel at moderate signal-to-noise ratios.