© 2026 Aqora Quantum S.A.S.

Terms Privacy Legal Notice

Space Electronic technology

New Construction of Large-girth QC-LDPC Codes by Classification of Cycles and Heuristic Search Strategy

Jianhua Zhang

Published Jan 1, 2013• 0 citations

Abstract

By classifying cycle types within the parity-check matrix of a quasi-cyclic(QC) low-density parity-check(LDPC) code,a method without repetition or omission is proposed to detect all the cycles with lengths smaller than twelve.Based on this cycle detection method,a new approach is presented to construct large girth QC-LDPC codes by using some heuristic strategies.The approach includes three steps.Firstly,under the infinite cyclic permutation matrix(CPM) size condition,two integer sequences satisfying the girth constraint are found using a heuristic strategy.Secondly,according to the designed code rate,several integer pairs are extracted from the two sequences so as to form a shift matrix.Finally,by employing the recently proposed theoretical lower bound by Zhang et.al,a range of consecutive CPM sizes in which the girth never decrease is accurately computed from the shift matrix.Compared with Liu-Han's method,the new approach possesses two advantages in the sense that:(1) Not only girth-10+ QC-LDPC codes but also girth-12 ones can be constructed to have consecutive CPM sizes;(2) girth-10+ and girth-12 QC-LDPC codes can be generated with very high code rates,due to the new cycle detection method which significantly accelerates the sequence search procedure.

Related papers

Novel Constructions of QC-LDPC Codes with Girth at Least Eight:An Explicit Framework

Xinmei Wang

Enabling the parity-check matrices to have a large girth is an efficient method to improve the decoding performance for many binary and non-binary QC-LDPC codes.A new explicit framework to construct QC-LDPC codes with girth at least eight is proposed,without any computer search procedures.The QC-LDPC codes constructed by the framework not only have a girth at least eight,but also possess an advantage of consecutive cyclic permutation matrix(CPM) sizes.The framework includes two steps:first,a parity-check matrix is explicitly constructed with a girth at least eight under an infinite CPM size;second,the tight lower bound of consecutive CPM sizes is precisely calculated directly from the corresponding shift matrix of the parity-check matrix,by employing a new girth property discovered by this paper.

Dianzi xuebao•Jan 1, 2012•3 citations

Girth-12 Quasi-Cyclic LDPC Codes with Consecutive Lengths

Guohua Zhang, Xinmei Wang

A method to construct girth-12 (3,L) quasi-cyclic low-density parity-check (QC-LDPC) codes with all lengths larger than a certain given number is proposed, via a given girth-12 code subjected to some constraints. The lengths of these codes can be arbitrary integers of the form LP, provided that P is larger than a tight lower bound determined by the maximal element within the exponent matrix of the given girth-12 code. By applying the method to the case of row-weight six, we obtained a family of girth-12 (3,6) QC-LDPC codes for arbitrary lengths above 2688, which includes 30 member codes with shorter code lengths compared with the shortest girth-12 (3,6) QC-LDPC codes reported by O'Sullivan.

arXiv:1001.3916•Jan 22, 2010•7 citations

Construction of Quasi-Cyclic LDPC codes with large girth based on circulant permutation matirx

Peng Yang, Xiaoxiao Bao, Hui Zhao

In this paper, we propose an algorithm for removing short-cycles in Quasi-Cyclic (QC) Low-density parity-check (LDPC) codes. First using an algorithm with lower computational complexity, all the cycles in the parity check matrix H are found. Then following a ruler, we adjust the shift value of circulant permutation matrix (CPM) to remove the short-cycles. This algorithm could ensure that the code after cycle removal process preserves the quasi-cyclic structure. Simulation results show that: comparing with the codes (504,252) and (1008, 504), we achieve 0.1dB improvement both.

Wireless and Optical Communications Conference•May 1, 2013•4 citations

Symmetrical Constructions for Regular Girth-8 QC-LDPC Codes

Alireza Tasdighi, Amir H. Banihashemi, Mohammad‐Reza Sadeghi

In this paper, we propose new constructions for regular girth-8 quasi-cyclic low-density parity-check (QC-LDPC) codes based on circulant permutation matrices (CPM). The constructions assume symmetries in the structure of the parity-check matrix and employ a greedy exhaustive search algorithm to find the permutation shifts of the CPMs. As a result of symmetries, the new codes have a more compact representation compared with their counterparts. In majority of cases, also, they achieve the girth 8 at a shorter block length for the same degree distribution (code rate). Deterministic (explicit) constructions are also presented to expand the proposed parity-check matrices to larger block lengths and higher rates. The proposed long high-rate codes are often substantially shorter than regular girth-8 QC-LDPC codes of similar rate in the literature. Simulation results demonstrate that the proposed symmetric codes have competitive performance in comparison with similar existing QC-LDPC codes that lack symmetry.

IEEE Transactions on Communications•Jan 1, 2016•66 citations

A fast searching method for the construction of QC-LDPC codes with large girth

Francis C. M. Lau, Wai M. Tam

In this paper, we propose an effective and efficient searching method for constructing quasi-cyclic low-density parity-check (QC-LDPC) codes with a desired girth g. We begin with an arbitrary QC-LDPC code with girth-4 and we evaluate only the number of cycles with length 4. When all the cycles with length 4 are removed by adjusting the elements of the QC-LDPC code, we form a QC-LDPC code with girth-6. Subsequently, we consider only the numbers of cycles with length 4 and length 6. In general, knowing that the current QC-LDPC code has a girth of g', we only consider the numbers of cycles with length up to g' even though g' may be smaller than the desired girth g. By using an adaptive cost function, which is defined as the number of cycles of length g', in the optimization/searching process, we are able to reduce the computational effort tremendously compared with Wang's searching algorithm [1]. Consequently, our proposed method can generate QC-LDPC codes with the desired girth much more efficiently.

IEEE Symposium on Computers and Communications (ISCC)•Jul 1, 2012•13 citations

Random Constructions of Girth-Eight QC-LDPC Codes with Structural Shaping

Songyan Xue, Guohua Zhang

In order to construct girth-8 quasi-cyclic (QC) low-density parity-check (LDPC) codes with low encoding complexity, this paper introduces structural shaping techniques to generate QC-LDPC codes with two different structures. These two structures are QC-LDPC codes constructed with vertical symmetric structure and reverse structure without 4-cycles and 6-cycles. Novel constructions assume that the structures of the parity check matrix (PCM) are symmetric and reverse, respectively, and the greedy exhaustive search algorithm is used to find the exponent matrix with the smallest possible size P of the circulant permutation matrix (CPM). Due to its symmetrical and reverse structural characteristics, the representation of the new codes is more compact than other codes. The simulation results show that the proposed codes have certain competitiveness compared to existing QC-LDPC codes.

IEEE/CIC International Conference on Communications in China (ICCC)•Aug 10, 2025•0 citations

By classifying cycle types within the parity-check matrix of a quasi-cyclic(QC) low-density parity-check(LDPC) code,a method without repetition or omission is proposed to detect all the cycles with lengths smaller than twelve.Based on this cycle detection method,a new approach is presented to construct large girth QC-LDPC codes by using some heuristic strategies.The approach includes three steps.Firstly,under the infinite cyclic permutation matrix(CPM) size condition,two integer sequences satisfying the girth constraint are found using a heuristic strategy.Secondly,according to the designed code rate,several integer pairs are extracted from the two sequences so as to form a shift matrix.Finally,by employing the recently proposed theoretical lower bound by Zhang et.al,a range of consecutive CPM sizes in which the girth never decrease is accurately computed from the shift matrix.Compared with Liu-Han's method,the new approach possesses two advantages in the sense that:(1) Not only girth-10+ QC-LDPC codes but also girth-12 ones can be constructed to have consecutive CPM sizes;(2) girth-10+ and girth-12 QC-LDPC codes can be generated with very high code rates,due to the new cycle detection method which significantly accelerates the sequence search procedure.

Enabling the parity-check matrices to have a large girth is an efficient method to improve the decoding performance for many binary and non-binary QC-LDPC codes.A new explicit framework to construct QC-LDPC codes with girth at least eight is proposed,without any computer search procedures.The QC-LDPC codes constructed by the framework not only have a girth at least eight,but also possess an advantage of consecutive cyclic permutation matrix(CPM) sizes.The framework includes two steps:first,a parity-check matrix is explicitly constructed with a girth at least eight under an infinite CPM size;second,the tight lower bound of consecutive CPM sizes is precisely calculated directly from the corresponding shift matrix of the parity-check matrix,by employing a new girth property discovered by this paper.

A method to construct girth-12 (3,L) quasi-cyclic low-density parity-check (QC-LDPC) codes with all lengths larger than a certain given number is proposed, via a given girth-12 code subjected to some constraints. The lengths of these codes can be arbitrary integers of the form LP, provided that P is larger than a tight lower bound determined by the maximal element within the exponent matrix of the given girth-12 code. By applying the method to the case of row-weight six, we obtained a family of girth-12 (3,6) QC-LDPC codes for arbitrary lengths above 2688, which includes 30 member codes with shorter code lengths compared with the shortest girth-12 (3,6) QC-LDPC codes reported by O'Sullivan.

In this paper, we propose an algorithm for removing short-cycles in Quasi-Cyclic (QC) Low-density parity-check (LDPC) codes. First using an algorithm with lower computational complexity, all the cycles in the parity check matrix H are found. Then following a ruler, we adjust the shift value of circulant permutation matrix (CPM) to remove the short-cycles. This algorithm could ensure that the code after cycle removal process preserves the quasi-cyclic structure. Simulation results show that: comparing with the codes (504,252) and (1008, 504), we achieve 0.1dB improvement both.

In this paper, we propose new constructions for regular girth-8 quasi-cyclic low-density parity-check (QC-LDPC) codes based on circulant permutation matrices (CPM). The constructions assume symmetries in the structure of the parity-check matrix and employ a greedy exhaustive search algorithm to find the permutation shifts of the CPMs. As a result of symmetries, the new codes have a more compact representation compared with their counterparts. In majority of cases, also, they achieve the girth 8 at a shorter block length for the same degree distribution (code rate). Deterministic (explicit) constructions are also presented to expand the proposed parity-check matrices to larger block lengths and higher rates. The proposed long high-rate codes are often substantially shorter than regular girth-8 QC-LDPC codes of similar rate in the literature. Simulation results demonstrate that the proposed symmetric codes have competitive performance in comparison with similar existing QC-LDPC codes that lack symmetry.

In this paper, we propose an effective and efficient searching method for constructing quasi-cyclic low-density parity-check (QC-LDPC) codes with a desired girth g. We begin with an arbitrary QC-LDPC code with girth-4 and we evaluate only the number of cycles with length 4. When all the cycles with length 4 are removed by adjusting the elements of the QC-LDPC code, we form a QC-LDPC code with girth-6. Subsequently, we consider only the numbers of cycles with length 4 and length 6. In general, knowing that the current QC-LDPC code has a girth of g', we only consider the numbers of cycles with length up to g' even though g' may be smaller than the desired girth g. By using an adaptive cost function, which is defined as the number of cycles of length g', in the optimization/searching process, we are able to reduce the computational effort tremendously compared with Wang's searching algorithm [1]. Consequently, our proposed method can generate QC-LDPC codes with the desired girth much more efficiently.

In order to construct girth-8 quasi-cyclic (QC) low-density parity-check (LDPC) codes with low encoding complexity, this paper introduces structural shaping techniques to generate QC-LDPC codes with two different structures. These two structures are QC-LDPC codes constructed with vertical symmetric structure and reverse structure without 4-cycles and 6-cycles. Novel constructions assume that the structures of the parity check matrix (PCM) are symmetric and reverse, respectively, and the greedy exhaustive search algorithm is used to find the exponent matrix with the smallest possible size P of the circulant permutation matrix (CPM). Due to its symmetrical and reverse structural characteristics, the representation of the new codes is more compact than other codes. The simulation results show that the proposed codes have certain competitiveness compared to existing QC-LDPC codes.