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

A lower bound on the minimum distance of chained Gallager codes

Victor Zyablov, Florian Hug, Rolf Johannesson

Published Jan 1, 2009• 0 citations
OpenAlex

Abstract

Based on the combination of two regular Gallager (Low-Density Parity-Check (LDPC)) codes, we will introduce a new code construction, called Chained Gallager codes. Following Gallager’s method we will derive a lower bound on the normalized minimum distance for the ensemble of Chained Gallager codes. Applying this lower bound on the normalized minimum distance to different transmissions schemes with two parallel and independent channels, the error correcting capabilities will be studied, stressing the advantages of Chained Gallager codes.

Related papers

Chained Gallager codes

Victor Zyablov, Florian Hug, Rolf Johannesson

The ensemble of regular Low-Density Parity-Check (LDPC) codes introduced by Gallager is considered. Using probabilistic arguments a lower bound on the normalized minimum distance is derived. A new code construction, called Chained Gallager codes, is introduced as the combination of two Gallager codes and its error correcting capabilities are studied.

•Jan 1, 2009•1 citation

On the error-correcting capability of LDPC codes

Kamil Sh. Zigangirov, A. E. Pusane, D. K. Zigangirov +1 more

We consider the ensemble of low-density parity-check (LDPC) codes introduced by Gallager [1]. The Zyablov-Pinsker majority-logic iterative algorithm [2] for decoding LDPC codes is analyzed on the binary symmetric channel. An analytical lower bound on the error-correcting capability τ max that grows linearly in the code block length is obtained.

Problems of Information Transmission•Sep 1, 2008•11 citations

1 On the Minimum/Stopping Distance of Array Low-Density Parity-Check Codes

Eirik Rosnes, Marcel Ambroze, Martin Tomlinson +1 more

In this work, we study the minimum/stopping distance of array low-density parity-check (LDPC) codes. An array LDPC code is a quasi-cyclic LDPC code specified by two integers q and m, where q is an odd prime and m <= q. In the literature, the minimum/stopping distance of these codes (denoted by d(q,m) and h(q,m), respectively) has been thoroughly studied for m <= 5. Both exact results, for small values of q and m, and general (i.e., independent of q) bounds have been established. For m=6, the best known minimum distance upper bound, derived by Mittelholzer (IEEE Int. Symp. Inf. Theory, Jun./Jul. 2002), is d(q,6) <= 32. In this work, we derive an improved upper bound of d(q,6) <= 20 and a new upper bound d(q,7) <= 24 by using the concept of a template support matrix of a codeword/stopping set. The bounds are tight with high probability in the sense that we have not been able to find codewords of strictly lower weight for several values of q using a minimum distance probabilistic algorithm. Finally, we provide new specific minimum/stopping distance results for m <= 7 and low-to-moderate values of q <= 79.

•Aug 17, 2016•25 citations

An upper bound on the minimum distance of array low-density parity-check codes

Eirik Rosnes, Marcel Ambroze, Martin Tomlinson

In this work, we present an upper bound on the minimum distance of array low-density parity-check (LDPC) codes. An array LDPC code is a quasi-cyclic LDPC code specified by two integers q and m, where q is an odd prime and m ≤ q. In the literature, the minimum distance of these codes (denoted by d(q,m)) has been thoroughly studied for m ≤ 5. Both exact results, for small values of q and m, and general (i.e., independent of q) bounds have been established. For m ≤ 6, the best known minimum distance upper bound, derived by Mittelholzer (IEEE Int. Symp. Inf. Theory, Jun./Jul. 2002), is d(q, 6) ≤ 32. In this work, we derive an improved upper bound of d(q, 6) ≤ 20 by using the concept of a template support matrix of a codeword. The bound is tight with high probability in the sense that we have not been able to find codewords of strictly lower weight for several values of q using a minimum distance probabilistic algorithm. Finally, we provide new specific minimum distance results for m ≤ 6 and low-to-moderate values of q ≤ 79.

IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2014•0 citations

LDPC Codes Over the BEC: Bounds and Decoding Algorithms

Irina E. Bocharova, Boris D. Kudryashov, Vitaly Skachek +2 more

The performance of maximum-likelihood (ML) decoding on the binary erasure channel for finite-length low-density parity-check (LDPC) codes from two random ensembles is studied. A tightened union-type upper bound on the ML decoding error probability based on the precise coefficients of the average weight spectrum is presented. For LDPC codes from the Gallager ensemble and the Richardson-Urbanke ensemble, new upper bounds on the ML decoding performance based on computing the rank of submatrices of the code parity-check matrix are derived. A new lower bound on the ML decoding threshold followed from the latter error probability bound is obtained. An improved lower bound on the error probability for codes with a known estimate on the minimum distance is presented as well. A new low-complexity near-ML decoding algorithm for quasi-cyclic LDPC codes is proposed and simulated. Its performance is compared to the simulated belief propagation and ML decoding performance and simulated performance of the best known improved iterative decoding techniques, as well as, with the derived upper bounds on the ML decoding performance and with decoding thresholds obtained by the density evolution technique.

IEEE Transactions on Communications•Nov 6, 2018•5 citations

On the Minimum/Stopping Distance of Array Low-Density Parity-Check Codes

Eirik Rosnes, Marcel Ambroze, Martin Tomlinson

In this paper, we study the minimum/stopping distance of array low-density parity-check (LDPC) codes. An array LDPC code is a quasi-cyclic LDPC code specified by two integers q and m, where q is an odd prime and m q. In the literature, the minimum/stopping distance of these codes (denoted by d(q, m) and h(q, m), respectively) has been thoroughly studied for m 5. Both exact results, for small values of q and m, and general (i.e., independent of q) bounds have been established. For m = 6, the best known minimum distance upper bound, derived by Mittelholzer, is d(q, 6) 32. In this paper, we derive an improved upper bound of d(q, 6) 20 and a new upper bound d(q, 7) 24 by using the concept of a template support matrix of a codeword/stopping set. The bounds are tight with high probability in the sense that we have not been able to find codewords of strictly lower weight for several values of q using a minimum distance probabilistic algorithm. Finally, we provide new specific minimum/stopping distance results for m 7 and low-to-moderate values of q ≤79.

arXiv:1205.2590•IEEE Transactions on Information Theory•Jul 11, 2014•22 citations
Based on the combination of two regular Gallager (Low-Density Parity-Check (LDPC)) codes, we will introduce a new code construction, called Chained Gallager codes. Following Gallager’s method we will derive a lower bound on the normalized minimum distance for the ensemble of Chained Gallager codes. Applying this lower bound on the normalized minimum distance to different transmissions schemes with two parallel and independent channels, the error correcting capabilities will be studied, stressing the advantages of Chained Gallager codes.
In this work, we study the minimum/stopping distance of array low-density parity-check (LDPC) codes. An array LDPC code is a quasi-cyclic LDPC code specified by two integers q and m, where q is an odd prime and m <= q. In the literature, the minimum/stopping distance of these codes (denoted by d(q,m) and h(q,m), respectively) has been thoroughly studied for m <= 5. Both exact results, for small values of q and m, and general (i.e., independent of q) bounds have been established. For m=6, the best known minimum distance upper bound, derived by Mittelholzer (IEEE Int. Symp. Inf. Theory, Jun./Jul. 2002), is d(q,6) <= 32. In this work, we derive an improved upper bound of d(q,6) <= 20 and a new upper bound d(q,7) <= 24 by using the concept of a template support matrix of a codeword/stopping set. The bounds are tight with high probability in the sense that we have not been able to find codewords of strictly lower weight for several values of q using a minimum distance probabilistic algorithm. Finally, we provide new specific minimum/stopping distance results for m <= 7 and low-to-moderate values of q <= 79.
In this work, we present an upper bound on the minimum distance of array low-density parity-check (LDPC) codes. An array LDPC code is a quasi-cyclic LDPC code specified by two integers q and m, where q is an odd prime and m ≤ q. In the literature, the minimum distance of these codes (denoted by d(q,m)) has been thoroughly studied for m ≤ 5. Both exact results, for small values of q and m, and general (i.e., independent of q) bounds have been established. For m ≤ 6, the best known minimum distance upper bound, derived by Mittelholzer (IEEE Int. Symp. Inf. Theory, Jun./Jul. 2002), is d(q, 6) ≤ 32. In this work, we derive an improved upper bound of d(q, 6) ≤ 20 by using the concept of a template support matrix of a codeword. The bound is tight with high probability in the sense that we have not been able to find codewords of strictly lower weight for several values of q using a minimum distance probabilistic algorithm. Finally, we provide new specific minimum distance results for m ≤ 6 and low-to-moderate values of q ≤ 79.
The performance of maximum-likelihood (ML) decoding on the binary erasure channel for finite-length low-density parity-check (LDPC) codes from two random ensembles is studied. A tightened union-type upper bound on the ML decoding error probability based on the precise coefficients of the average weight spectrum is presented. For LDPC codes from the Gallager ensemble and the Richardson-Urbanke ensemble, new upper bounds on the ML decoding performance based on computing the rank of submatrices of the code parity-check matrix are derived. A new lower bound on the ML decoding threshold followed from the latter error probability bound is obtained. An improved lower bound on the error probability for codes with a known estimate on the minimum distance is presented as well. A new low-complexity near-ML decoding algorithm for quasi-cyclic LDPC codes is proposed and simulated. Its performance is compared to the simulated belief propagation and ML decoding performance and simulated performance of the best known improved iterative decoding techniques, as well as, with the derived upper bounds on the ML decoding performance and with decoding thresholds obtained by the density evolution technique.
In this paper, we study the minimum/stopping distance of array low-density parity-check (LDPC) codes. An array LDPC code is a quasi-cyclic LDPC code specified by two integers q and m, where q is an odd prime and m q. In the literature, the minimum/stopping distance of these codes (denoted by d(q, m) and h(q, m), respectively) has been thoroughly studied for m 5. Both exact results, for small values of q and m, and general (i.e., independent of q) bounds have been established. For m = 6, the best known minimum distance upper bound, derived by Mittelholzer, is d(q, 6) 32. In this paper, we derive an improved upper bound of d(q, 6) 20 and a new upper bound d(q, 7) 24 by using the concept of a template support matrix of a codeword/stopping set. The bounds are tight with high probability in the sense that we have not been able to find codewords of strictly lower weight for several values of q using a minimum distance probabilistic algorithm. Finally, we provide new specific minimum/stopping distance results for m 7 and low-to-moderate values of q ≤79.