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 Information Theory Workshop (ITW)

Non-binary GLD codes and their lattices

Nicola di Pietro, Nour Basha, Joseph J. Boutros

Published Apr 1, 2015• 9 citations
Publisher

Abstract

The recently discovered family of generalized low-density (GLD) lattices brings new mathematical challenges to coding theorists and practitioners. Given the excellent performance of integer GLD lattices in high dimensions and motivated by the simple lattice structure used for fast iterative decoding, this paper is a first attempt to analyze GLD lattices for asymptotically large dimensions. Firstly, we describe non-binary GLD codes and show their asymptotic goodness in terms of minimum Hamming distance. Secondly, we consider a GLD lattice ensemble built via Construction A from non-binary GLD codes, and analyze their goodness with respect to Poltyrev limit on the Gaussian channel. Finally, at large dimensions and using a large code alphabet, we prove that infinite GLD lattice constellations attain Poltyrev capacity limit under maximum likelihood decoding.

DOI
10.1109/itw.2015.7133127

Related papers

New results on low-density integer lattices

Nicola di Pietro, Joseph J. Boutros, Gilles Zémor +1 more

A new family of integer lattices built from Construction A and non-binary low-density parity-check (LDPC) codes has been proposed by the authors in 2012. Lattices in this family are referred to as LDA lattices. Previous experimental results revealed excellent performance which clearly single out LDA lattices among the strongest candidates for potential applications in digital communications and networks, such as network coding and information theoretic security at the physical layer level. In this paper, we show that replacing random codes by LDPC codes in Construction A does not induce any structural loss. More precisely, our main theorem states that LDA lattices can achieve Poltyrev capacity limit on an additive white Gaussian noise channel. We present here the detailed proof and its consequences on the lattice dimension, the finite field size, and the parameters of the LDPC ensemble. The latter has a row weight that increases logarithmically in the code length. In a more recent work, it is proved that the Poltyrev limit is attained by a different LDA ensemble having a small constant row weight.

Information Theory and Applications Workshop (ITA)•Feb 1, 2013•12 citations

Integer low-density lattices based on construction A

Nicola di Pietro, Joseph J. Boutros, Gilles Zémor +1 more

We describe a new family of integer lattices built from construction A and non-binary LDPC codes. An iterative message-passing algorithm suitable for decoding in high dimensions is proposed. This family of lattices, referred to as LDA lattices, follows the recent transition of Euclidean codes from their classical theory to their modern approach as announced by the pioneering work of Loeliger (1997), Erez, Litsyn, and Zamir (2004-2005). Besides their excellent performance near the capacity limit, LDA lattice construction is conceptually simpler than previously proposed lattices based on multiple nested binary codes and LDA decoding is less complex than real-valued message passing.

IEEE Information Theory Workshop (ITW)•Sep 1, 2012•51 citations

Generalized low density (Tanner) codes

Joseph J. Boutros, O. Pothier, Gilles Zémor

We build a class of pseudo-random error correcting codes, called generalized low density codes (GLD), from the intersection of two interleaved block codes. GLD code performance approaches the channel capacity limit and the GLD decoder is based on simple and fast SISO (soft input-soft output) decoders of smaller block codes. GLD codes are a special case of Tanner codes and a generalization of Gallager's LDPC codes. It is also proved by an ensemble performance argument that these codes are asymptotically good in the sense of the minimum distance criterion. The flexibility in selecting the parameters of GLD codes makes them suitable for small and large block length forward error correcting schemes.

International Conference on Communications•Jan 20, 2003•183 citations

On generalized low-density parity-check codes based on Hamming component codes

Michael Lentmaier, Kamil Sh. Zigangirov

In this paper we investigate a generalization of Gallager's (1963) low-density (LD) parity-check codes, where as component codes single error correcting Hamming codes are used instead of single error detecting parity-check codes. It is proved that there exist such generalized low-density (GLD) codes for which the minimum distance is growing linearly with the block length, and a lower bound of the minimum distance is given. We also study iterative decoding of GLD codes for the communication over an additive white Gaussian noise channel. The performance in terms of the bit error rate, obtained by computer simulations, is presented for GLD codes of different lengths.

IEEE Communications Letters•Aug 1, 1999•186 citations

A family of non-binary TLDPC codes: density evolution, convergence and thresholds

Iryna Andriyanova, Jean–Pierre Tillich

We generalize the results about how to compute iterative decoding thresholds over the binary erasure channel of non-binary LDPC code ensembles of [16] to non-binary TLDPC codes [2], [3]. We show in this case how density evolution can be performed in order to calculate iterative decoding thresholds and find several families with a very simple regular structure and thresholds close to the Shannon limit. To check the performances of these codes over other channels we have tested one of the simplest codes over F4which has rate 1/2 on the Gaussian channel. For the (binary) length 1008 for instance, without any optimization on the permutation structure of the code, it matches the performances of the best binary codes of the same length up to the word-error rate 10-3. We also notice that all LDPC codes (binary or not) having at least two symbols of degree 2 per parity-check equation can be represented as a special kind of TLDPC codes. We show that this representation and the associated decoding algorithm leads in the case of cycle codes to a significant reduction of the number of iterations which are needed for iterative decoding.

IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2007•5 citations

High-performance, low-complexity decoding of generalized low-density parity-check codes

T. Zhang, Keshab K. Parhi

A class of pseudo-random compound error-correcting codes, called generalized low-density (GLD) parity-check codes, has been proposed recently. As a generalization of Gallager's low-density parity-check (LDPC) codes, GLD codes are also asymptotically good in the sense of minimum distance criterion and can be effectively decoded based on iterative soft-input soft-output (SISO) decoding of individual constituent codes. The code performance and decoding complexity of GLD codes are heavily dependent on the employed SISO decoding algorithm. In this paper, we show that Max-Log-MAP is an attractive SISO decoding algorithm for GLD coding scheme, considering the trade-off between performance and complexity in the practical implementations. A normalized Max-Log-MAP is presented to improve the GLD code performance significantly compared with using conventional Max-Log-MAP. Moreover, we propose two techniques, decoding task scheduling and reduced search Max-Log-MAP, to effectively reduce the decoding complexity without any performance degradation.

Globecom•Nov 13, 2002•10 citations
The recently discovered family of generalized low-density (GLD) lattices brings new mathematical challenges to coding theorists and practitioners. Given the excellent performance of integer GLD lattices in high dimensions and motivated by the simple lattice structure used for fast iterative decoding, this paper is a first attempt to analyze GLD lattices for asymptotically large dimensions. Firstly, we describe non-binary GLD codes and show their asymptotic goodness in terms of minimum Hamming distance. Secondly, we consider a GLD lattice ensemble built via Construction A from non-binary GLD codes, and analyze their goodness with respect to Poltyrev limit on the Gaussian channel. Finally, at large dimensions and using a large code alphabet, we prove that infinite GLD lattice constellations attain Poltyrev capacity limit under maximum likelihood decoding.
A new family of integer lattices built from Construction A and non-binary low-density parity-check (LDPC) codes has been proposed by the authors in 2012. Lattices in this family are referred to as LDA lattices. Previous experimental results revealed excellent performance which clearly single out LDA lattices among the strongest candidates for potential applications in digital communications and networks, such as network coding and information theoretic security at the physical layer level. In this paper, we show that replacing random codes by LDPC codes in Construction A does not induce any structural loss. More precisely, our main theorem states that LDA lattices can achieve Poltyrev capacity limit on an additive white Gaussian noise channel. We present here the detailed proof and its consequences on the lattice dimension, the finite field size, and the parameters of the LDPC ensemble. The latter has a row weight that increases logarithmically in the code length. In a more recent work, it is proved that the Poltyrev limit is attained by a different LDA ensemble having a small constant row weight.
We describe a new family of integer lattices built from construction A and non-binary LDPC codes. An iterative message-passing algorithm suitable for decoding in high dimensions is proposed. This family of lattices, referred to as LDA lattices, follows the recent transition of Euclidean codes from their classical theory to their modern approach as announced by the pioneering work of Loeliger (1997), Erez, Litsyn, and Zamir (2004-2005). Besides their excellent performance near the capacity limit, LDA lattice construction is conceptually simpler than previously proposed lattices based on multiple nested binary codes and LDA decoding is less complex than real-valued message passing.
We build a class of pseudo-random error correcting codes, called generalized low density codes (GLD), from the intersection of two interleaved block codes. GLD code performance approaches the channel capacity limit and the GLD decoder is based on simple and fast SISO (soft input-soft output) decoders of smaller block codes. GLD codes are a special case of Tanner codes and a generalization of Gallager's LDPC codes. It is also proved by an ensemble performance argument that these codes are asymptotically good in the sense of the minimum distance criterion. The flexibility in selecting the parameters of GLD codes makes them suitable for small and large block length forward error correcting schemes.
In this paper we investigate a generalization of Gallager's (1963) low-density (LD) parity-check codes, where as component codes single error correcting Hamming codes are used instead of single error detecting parity-check codes. It is proved that there exist such generalized low-density (GLD) codes for which the minimum distance is growing linearly with the block length, and a lower bound of the minimum distance is given. We also study iterative decoding of GLD codes for the communication over an additive white Gaussian noise channel. The performance in terms of the bit error rate, obtained by computer simulations, is presented for GLD codes of different lengths.
We generalize the results about how to compute iterative decoding thresholds over the binary erasure channel of non-binary LDPC code ensembles of [16] to non-binary TLDPC codes [2], [3]. We show in this case how density evolution can be performed in order to calculate iterative decoding thresholds and find several families with a very simple regular structure and thresholds close to the Shannon limit. To check the performances of these codes over other channels we have tested one of the simplest codes over F4which has rate 1/2 on the Gaussian channel. For the (binary) length 1008 for instance, without any optimization on the permutation structure of the code, it matches the performances of the best binary codes of the same length up to the word-error rate 10-3. We also notice that all LDPC codes (binary or not) having at least two symbols of degree 2 per parity-check equation can be represented as a special kind of TLDPC codes. We show that this representation and the associated decoding algorithm leads in the case of cycle codes to a significant reduction of the number of iterations which are needed for iterative decoding.
A class of pseudo-random compound error-correcting codes, called generalized low-density (GLD) parity-check codes, has been proposed recently. As a generalization of Gallager's low-density parity-check (LDPC) codes, GLD codes are also asymptotically good in the sense of minimum distance criterion and can be effectively decoded based on iterative soft-input soft-output (SISO) decoding of individual constituent codes. The code performance and decoding complexity of GLD codes are heavily dependent on the employed SISO decoding algorithm. In this paper, we show that Max-Log-MAP is an attractive SISO decoding algorithm for GLD coding scheme, considering the trade-off between performance and complexity in the practical implementations. A normalized Max-Log-MAP is presented to improve the GLD code performance significantly compared with using conventional Max-Log-MAP. Moreover, we propose two techniques, decoding task scheduling and reduced search Max-Log-MAP, to effectively reduce the decoding complexity without any performance degradation.