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 Communications Letters

Relation Between GCD Constraint and Full-Length Row-Multiplier QC-LDPC Codes With Girth Eight

Guohua Zhang, Yulin Hu, Yi Fang, Defeng Ren

Published Jul 12, 2021• 12 citations
Publisher

Abstract

The greatest-common-divisor (GCD) method is a general framework employing a set of simple inequalities (called GCD constraint) to guarantee girth eight for a class of (J,L) quasi-cyclic (QC) low-density parity-check (LDPC) codes. However, an important problem, i.e., whether the GCD constraint is necessary for this class of codes to have girth eight, remains open. In this letter, the question is answered affirmatively, following which a novel algorithm aiming to find the shortest codes with girth eight in such a class is proposed. Besides, a close connection is established between the GCD method and the base expansion method, which are both applicable for any J and any L.

DOI
10.1109/lcomm.2021.3096386

Related papers

Construction of Girth-Eight QC-LDPC Codes from Greatest Common Divisor

Guohua Zhang, Rong Xia Sun, Xinmei Wang

For any column weight J and any row weight L, a novel framework is proposed such that a girth-eight (J,L) quasi-cyclic low-density parity-check (QC-LDPC) code with any block length above a lower bound can be constructed via a simple inequality in terms of greatest common divisor (GCD). The main advantage is that the construction of a class of (J,L) girth-eight QC-LDPC codes is transformed into a rather simple task, searching for J integers satisfying the so-called GCD constraint for L. Combining the new method with masking matrices, a class of type-1 QC-LDPC codes is presented with girth at least eight. Simulation results show that the type-1 codes perform better than the random QC-LDPC codes and quadratic-congruence-based QC-LDPC codes for moderate block lengths and low code rates.

IEEE Communications Letters•Jan 2, 2013•47 citations

Automatic Verification of GCD Constraint for Construction of Girth-Eight QC-LDPC Codes

Guohua Zhang, Yi Fang, Yuanhua Liu

As a general method to yield constructions for quasi-cyclic (QC) low-density parity-check (LDPC) codes with girth eight, the greatest-common-divisor (GCD) framework heavily relies on verifying a type of inequalities, referred to as GCD constraints. An algorithm is developed in this letter to automatically verify GCD constraints without conducting any manual analysis, by bounding from above the GCD of a fixed integer and an integer in the form of linear function. As an application of the algorithm, a set of novel constructions based on GCD framework is proposed. From these new constructions, four novel bounds on the size of circulant permutation matrices (CPMs) are formulated, such that girth-eight QC-LDPC codes always exist for any CPM size greater than or equal to the bounds. The new bound for column weight of 6 slightly improves the existing best one, and those for column weights from 7 to 9 significantly strengthen the state-of-the-art ones by decreasing from essentially a cubic or biquadratic power of row weight to a quadratic power of row weight.

IEEE Communications Letters•Jun 28, 2019•11 citations

Full-Length Row-Multiplier QC-LDPC Codes With Girth Eight and Short Circulant Sizes

Juhua Wang, Jianhua Zhang, Quan Zhou +1 more

As a special case of a quasi-cyclic (QC) low-density parity-check (LDPC) code, a full-length row-multiplier (FLRM) QC-LDPC code is described by a compact exponent matrix based on two sequences of integers. The codes designed by a framework known as greatest-common-divisor (GCD) method, belong to a salient class of FLRM QC-LDPC codes, which can eliminate cycles of length up to six by carefully selecting a special sequence subject to a set of simple inequalities. However, the GCD method ensures the absence of these cycles only if circulant sizes are larger than a certain threshold. By combining the existing GCD method, novel sequences and a new analysis method (based on new lemmas of circulants and integers) for modulo equations, a group of novel FLRM QC-LDPC codes free of 4-cycles and 6-cycles are explicitly proposed for column weights from three to five in this paper, which possess circulant sizes much smaller than the forgoing threshold. Simulations show that the new FLRM QC-LDPC codes with shorter lengths perform almost the same as the existing FLRM QC-LDPC codes with longer lengths, and that the novel FLRM QC-LDPC codes noticeably outperform their counterparts with (nearly) identical lengths.

IEEE Access•Jan 1, 2023•10 citations

On the Class of High-Rate QC-LDPC Codes With Girth 8 From Sequences Satisfied in GCD Condition

Marjan Majdzade, Mohammad Gholami

Recently, a class of (J, L) quasi-cyclic (QC) low-density parity-check (LDPC) codes with girth eight is constructed based on the greatest-common-divisor (GCD) condition. For L = 3, an equivalence between the sequences generated by a greedy algorithm satisfying in GCD condition and a known class of integer sequences, called Stanley sequences has been proposed as an open problem. In this letter, we solve this problem in a more general case by introducing the class of 3-free sets as a generalization of Stanley sequences and showing an equivalence between 3-free sets and the sequences satisfied in GCD condition. Then, a new algorithm is proposed to find 3-free sets efficiently usually having larger size than the known methods, leading to column-weight 3 QC-LDPC codes with smaller lengths and better 8-cycle distributions. In addition, a new explicit formula is proposed to construct Stanley sequences which results in a class of girth-8 column-weight 3 QC-LDPC codes with high rates. The protograph QC-LDPC codes lifted from the constructed base matrices outperform progressive-edge-growth (PEG), randomlike and some recent QC-LDPC codes with the same girth.

IEEE Communications Letters•Mar 24, 2020•11 citations

On Existence of Girth-8 QC-LDPC Code with Large Column Weight: Combining Mirror-sequence with Classification Modulo Ten

Guohua Zhang, Xiangya Liu, Jianhua Zhang +1 more

Quasi-cyclic (QC) LDPC codes with large girths play a crucial role in several research and application fields, including channel coding, compressed sensing and distributed storage systems. A major challenge in respect of the code construction is how to obtain such codes with the shortest possible length (or equivalently, the smallest possible circulant size) using algebraic methods instead of search methods. The greatest-common-divisor (GCD) framework we previously proposed has algebraically constructed QC-LDPC codes with column weights of 5 and 6, very short lengths, and a girth of 8. By introducing the concept of a mirror sequence and adopting a new row-regrouping scheme, QC-LDPC codes with column weights of 7 and 8, very short lengths, and a girth of 8 are proposed for arbitrary row weights in this article via an algebraic manner under the GCD framework. Thanks to these novel algebraic methods, the lower bounds (for column weights 7 and 8) on consecutive circulant sizes are both improved by asymptotically about 20%, compared with the existing benchmarks. Furthermore, these new constructions can also offer circulant sizes asymptotically about 25% smaller than the novel bounds.

arXiv:2601.10170•IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2026•0 citations

Constructions of Girth-Eight QC-LDPC Codes with Dual-Diagonal Structure Based on GCD Framework

Guohua Zhang, Haiyang Liu, Mengjuan Lou +1 more

A novel class of quasi-cyclic (QC) low-density parity-check (LDPC) codes is explicitly proposed without 4-cycles and 6-cycles via the greatest-common-divisor (GCD) framework. From the new codes, a novel type of girth-eight QC-LDPC codes with a dual-diagonal (DD) structure is presented, in which the single undetermined entry in the associated exponent matrix can be determined by simple formulae. The proposed DD codes have similar or better performance compared with DD codes obtained from computer search. Moreover, a lower bound on circulant sizes which guarantees the existence of qualified undetermined entries is also provided.

International Conference on Wireless Communications and Signal Processing (WCSP)•Nov 2, 2023•5 citations
The greatest-common-divisor (GCD) method is a general framework employing a set of simple inequalities (called GCD constraint) to guarantee girth eight for a class of (J,L) quasi-cyclic (QC) low-density parity-check (LDPC) codes. However, an important problem, i.e., whether the GCD constraint is necessary for this class of codes to have girth eight, remains open. In this letter, the question is answered affirmatively, following which a novel algorithm aiming to find the shortest codes with girth eight in such a class is proposed. Besides, a close connection is established between the GCD method and the base expansion method, which are both applicable for any J and any L.
For any column weight J and any row weight L, a novel framework is proposed such that a girth-eight (J,L) quasi-cyclic low-density parity-check (QC-LDPC) code with any block length above a lower bound can be constructed via a simple inequality in terms of greatest common divisor (GCD). The main advantage is that the construction of a class of (J,L) girth-eight QC-LDPC codes is transformed into a rather simple task, searching for J integers satisfying the so-called GCD constraint for L. Combining the new method with masking matrices, a class of type-1 QC-LDPC codes is presented with girth at least eight. Simulation results show that the type-1 codes perform better than the random QC-LDPC codes and quadratic-congruence-based QC-LDPC codes for moderate block lengths and low code rates.
As a general method to yield constructions for quasi-cyclic (QC) low-density parity-check (LDPC) codes with girth eight, the greatest-common-divisor (GCD) framework heavily relies on verifying a type of inequalities, referred to as GCD constraints. An algorithm is developed in this letter to automatically verify GCD constraints without conducting any manual analysis, by bounding from above the GCD of a fixed integer and an integer in the form of linear function. As an application of the algorithm, a set of novel constructions based on GCD framework is proposed. From these new constructions, four novel bounds on the size of circulant permutation matrices (CPMs) are formulated, such that girth-eight QC-LDPC codes always exist for any CPM size greater than or equal to the bounds. The new bound for column weight of 6 slightly improves the existing best one, and those for column weights from 7 to 9 significantly strengthen the state-of-the-art ones by decreasing from essentially a cubic or biquadratic power of row weight to a quadratic power of row weight.
As a special case of a quasi-cyclic (QC) low-density parity-check (LDPC) code, a full-length row-multiplier (FLRM) QC-LDPC code is described by a compact exponent matrix based on two sequences of integers. The codes designed by a framework known as greatest-common-divisor (GCD) method, belong to a salient class of FLRM QC-LDPC codes, which can eliminate cycles of length up to six by carefully selecting a special sequence subject to a set of simple inequalities. However, the GCD method ensures the absence of these cycles only if circulant sizes are larger than a certain threshold. By combining the existing GCD method, novel sequences and a new analysis method (based on new lemmas of circulants and integers) for modulo equations, a group of novel FLRM QC-LDPC codes free of 4-cycles and 6-cycles are explicitly proposed for column weights from three to five in this paper, which possess circulant sizes much smaller than the forgoing threshold. Simulations show that the new FLRM QC-LDPC codes with shorter lengths perform almost the same as the existing FLRM QC-LDPC codes with longer lengths, and that the novel FLRM QC-LDPC codes noticeably outperform their counterparts with (nearly) identical lengths.
Recently, a class of (J, L) quasi-cyclic (QC) low-density parity-check (LDPC) codes with girth eight is constructed based on the greatest-common-divisor (GCD) condition. For L = 3, an equivalence between the sequences generated by a greedy algorithm satisfying in GCD condition and a known class of integer sequences, called Stanley sequences has been proposed as an open problem. In this letter, we solve this problem in a more general case by introducing the class of 3-free sets as a generalization of Stanley sequences and showing an equivalence between 3-free sets and the sequences satisfied in GCD condition. Then, a new algorithm is proposed to find 3-free sets efficiently usually having larger size than the known methods, leading to column-weight 3 QC-LDPC codes with smaller lengths and better 8-cycle distributions. In addition, a new explicit formula is proposed to construct Stanley sequences which results in a class of girth-8 column-weight 3 QC-LDPC codes with high rates. The protograph QC-LDPC codes lifted from the constructed base matrices outperform progressive-edge-growth (PEG), randomlike and some recent QC-LDPC codes with the same girth.
Quasi-cyclic (QC) LDPC codes with large girths play a crucial role in several research and application fields, including channel coding, compressed sensing and distributed storage systems. A major challenge in respect of the code construction is how to obtain such codes with the shortest possible length (or equivalently, the smallest possible circulant size) using algebraic methods instead of search methods. The greatest-common-divisor (GCD) framework we previously proposed has algebraically constructed QC-LDPC codes with column weights of 5 and 6, very short lengths, and a girth of 8. By introducing the concept of a mirror sequence and adopting a new row-regrouping scheme, QC-LDPC codes with column weights of 7 and 8, very short lengths, and a girth of 8 are proposed for arbitrary row weights in this article via an algebraic manner under the GCD framework. Thanks to these novel algebraic methods, the lower bounds (for column weights 7 and 8) on consecutive circulant sizes are both improved by asymptotically about 20%, compared with the existing benchmarks. Furthermore, these new constructions can also offer circulant sizes asymptotically about 25% smaller than the novel bounds.
A novel class of quasi-cyclic (QC) low-density parity-check (LDPC) codes is explicitly proposed without 4-cycles and 6-cycles via the greatest-common-divisor (GCD) framework. From the new codes, a novel type of girth-eight QC-LDPC codes with a dual-diagonal (DD) structure is presented, in which the single undetermined entry in the associated exponent matrix can be determined by simple formulae. The proposed DD codes have similar or better performance compared with DD codes obtained from computer search. Moreover, a lower bound on circulant sizes which guarantees the existence of qualified undetermined entries is also provided.