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)

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

Eirik Rosnes, Marcel Ambroze, Martin Tomlinson

Published Jun 1, 2014• 0 citations
Publisher

Abstract

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.

DOI
10.1109/isit.2014.6875416

Related papers

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

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

On the minimum distance of array-based spatially-coupled low-density parity-check codes

Eirik Rosnes

An array low-density parity-check (LDPC) code is a quasi-cyclic LDPC code specified by two integers q and m, where q is an odd prime and m ≤ q. The exact minimum distance, for small q and m, has been calculated, and tight upper bounds on it for m ≤ 7 have been derived. In this work, we study the minimum distance of the spatially-coupled version of these codes. In particular, several tight upper bounds on the optimal minimum distance for coupling length at least two and m = 3; 4; 5, that are independent of q and that are valid for all values of q ≥ q0where q0depends on m, are presented. Furthermore, we show by exhaustive search that by carefully selecting the edge spreading or unwrapping procedure, the minimum distance (when q is not very large) can be significantly increased, especially for m = 5.

arXiv:1504.06416•IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2015•10 citations

More on the Minimum Distance of Array LDPC Codes

Haiyang Liu, Shipei Yang, Gang Deng +1 more

Array low-density parity-check (LDPC) codes are a special class of quasi-cyclic LDPC codes constructed from a pair of integers (m, q), where q is an odd prime, and m ≤ q. In this paper, an improved upper bound on the minimum distance of this class of codes is given.

IEEE Communications Letters•Apr 29, 2014•5 citations

Further Results on the Stopping Distance of Array LDPC Matrices

Haiyang Liu, Lu HE, Jie Chen

Given an odd prime q and an integer m ≤ q, an array-based parity-check matrix H(m,q) can be constructed for a quasi-cyclic low-density parity-check (LDPC) code C(m,q). For m = 4 and q ≥ 11, we prove the stopping distance of H(4,q) is 10, which is equal to the minimum Hamming distance of the associated code C(4,q). In addition, a tighter lower bound on the stopping distance of H(m,q) is also given for m > 4 and q ≥ 11.

IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences•Jan 1, 2012•6 citations

Tight Lower and Upper Bounds on the Minimum Distance of LDPC Codes

Yoones Hashemi, Amir H. Banihashemi

In this letter, we obtain lower and upper bounds on the minimum distance dminof low-density parity-check (LDPC) codes. The bounds are derived by categorizing the non-zero code words of an LDPC code into two categories of elementary and non-elementary. The first category contains code words whose induced subgraph has only degree-2 check nodes. We propose an efficient search algorithm that can find the elementary code words of an LDPC code with weight less than a certain value amax, exhaustively. We also derive a lower bound Lneon the weight of non-elementary code words. By performing the search with amax= Lne, we either obtain an elementary code word with the smallest weight dmin, or establish the lower bound of Lneon dmin. For the upper bound, we modify our search algorithm to reach elementary codewords of larger weights at the cost of being non-exhaustive. Once such a codeword is found, its weight acts as an upper bound on dmin. We examine a large number of regular and irregular LDPC codes, and demonstrate the efficiency and versatility of our technique in finding lower and upper bounds on, and in many cases the exact value of, dmin. Finding dmin, or establishing search-based lower or upper bounds, for many of the examined codes are out of the reach of any existing algorithm.

IEEE Communications Letters•Nov 1, 2017•11 citations
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.
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 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.
An array low-density parity-check (LDPC) code is a quasi-cyclic LDPC code specified by two integers q and m, where q is an odd prime and m ≤ q. The exact minimum distance, for small q and m, has been calculated, and tight upper bounds on it for m ≤ 7 have been derived. In this work, we study the minimum distance of the spatially-coupled version of these codes. In particular, several tight upper bounds on the optimal minimum distance for coupling length at least two and m = 3; 4; 5, that are independent of q and that are valid for all values of q ≥ q0where q0depends on m, are presented. Furthermore, we show by exhaustive search that by carefully selecting the edge spreading or unwrapping procedure, the minimum distance (when q is not very large) can be significantly increased, especially for m = 5.
In this letter, we obtain lower and upper bounds on the minimum distance dminof low-density parity-check (LDPC) codes. The bounds are derived by categorizing the non-zero code words of an LDPC code into two categories of elementary and non-elementary. The first category contains code words whose induced subgraph has only degree-2 check nodes. We propose an efficient search algorithm that can find the elementary code words of an LDPC code with weight less than a certain value amax, exhaustively. We also derive a lower bound Lneon the weight of non-elementary code words. By performing the search with amax= Lne, we either obtain an elementary code word with the smallest weight dmin, or establish the lower bound of Lneon dmin. For the upper bound, we modify our search algorithm to reach elementary codewords of larger weights at the cost of being non-exhaustive. Once such a codeword is found, its weight acts as an upper bound on dmin. We examine a large number of regular and irregular LDPC codes, and demonstrate the efficiency and versatility of our technique in finding lower and upper bounds on, and in many cases the exact value of, dmin. Finding dmin, or establishing search-based lower or upper bounds, for many of the examined codes are out of the reach of any existing algorithm.