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 Symposium on Computers and Communications (ISCC)

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

Francis C. M. Lau, Wai M. Tam

Published Jul 1, 2012• 13 citations
Publisher

Abstract

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.

DOI
10.1109/iscc.2012.6249279

Related papers

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

Jianhua Zhang

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.

Space Electronic technology•Jan 1, 2013•0 citations

Efficient Search of Girth-Optimal QC-LDPC Codes

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

In this paper, we study the cycle structure of quasi-cyclic (QC) low-density parity-check (LDPC) codes with the goal of obtaining the shortest code with a given degree distribution and girth. We focus on QC-LDPC codes, whose Tanner graphs are cyclic liftings of fully connected base graphs of size 3 × n, n ≥ 4, and obtain minimal lifting degrees that result in girths 6 and 8. This is performed through an efficient exhaustive search, and as a result, we also find all the possible non-isomorphic codes with the same minimum block length, girth, and degree distribution. The exhaustive search, which is ordinarily a formidable task, is made possible by pruning the search space of many codes that are isomorphic to those previously examined in the search process. Many of the pruning techniques proposed in this paper are also applicable to QC-LDPC codes with base graphs other than the 3 × n fully connected ones discussed here, as well as to codes with a larger girth. To further demonstrate the effectiveness of the pruning techniques, we use them to search for QC-LDPC codes with girths 10 and 12, and find a number of such codes that have a shorter block length compared with the best known similar codes in the literature. In addition, motivated by the exhaustive search results, we tighten the lower bound on the block length of QC-LDPC codes of girth 6 constructed from fully connected 3 × n base graphs, and construct codes that achieve the lower bound for an arbitrary value of n ≥ 4.

IEEE Transactions on Information Theory•Feb 3, 2016•78 citations

Flexible Construction of High-Girth QC-LDPC Codes

Gabofetswe Malema

This article presents a highly flexible method for constructing high-girth quasi-cyclic low-density parity-check (QC-LDPC) codes. The proposed algorithm constructs a Tanner graph formed by connecting groups of rows (check nodes) and columns (variable nodes) of the constructed code. To obtain a sub-matrix structure, rows and columns are divided into groups of equal sizes. Rows and columns in a group are connected in their numerical (positional) order to obtain a cyclic structure. Connected rows and columns must satisfy the desired minimum cycle length. We present conditions that guarantee desired girths. The proposed algorithm is by far more flexible in constructing a wide range (rates and lengths) of regular and irregular QC-LDPC codes compared to existing methods. The algorithm, which has linear complexity with respect to the number of rows or columns, provides an easy and fast way to construct QC-LDPC codes. Constructed codes show good bit error rate performances.

International journal of computer science and applications•Aug 1, 2012•2 citations

A time-saving algorithm for constructing QC-LDPC codes based on PEG algorithm

Ping Gong, Huang Liqun

We propose a new algorithm based on PEG algorithm to construct high-girth quasi-cyclic low-density parity check (QC-LDPC) codes. Before our improved algorithm in introduction, we depict the general algorithm based on PEG algorithm to construct QC - LDPC code, if necessary to eliminate the short cycles, that would bring in cycles-search. When code length of basic matrix is not too long, the algorithm is feasible, but with the code length growth, cycles-search will bring large of calculation and time-consuming sharply. Therefore we put forward an improved method by using the specific relation of basic matrix rows to replace traditional cycles-search, effectively eliminates short cycles, and largely reduces the time complexity at the same time. Through the simulation analysis, the performance can also be comparable with random constructed LDPC codes.

International Conference on Consumer Electronics, Communications and Networks (CECNet)•Apr 1, 2011•1 citation

Quasi-Cyclic LDPC Codes with Large Girth and Few Short Cycles

Yuanhua Liu

In this paper, we present an improved method for obtaining quasi-cyclic low-density parity-check (QC-LDPC) codes of larger length by combining some component QC-LDPC codes of smaller length.Large girth can be obtained by carefully designing one large girth component code of smaller length.The other component codes are properly designed to obtain a lot of QC-LDPC codes with much few short cycles.Simulations show that compared with CRT based QC-LDPC codes and PEG based QC-LDPC codes, the proposed QC-LDPC codes have much less short cycles and better performance.

International Conference on Manufacturing Science and Engineering (ICMSE)•Jan 1, 2018•0 citations

Construction of Large Girth QC-LDPC Codes Based on Finite Geometries and Fast Searching Method

Zhirong Wang, Liqian Wang, Dongdong Wang +5 more

We proposed a method which combines finite geometries and optimized searching algorithm to construct quasi-cyclic low-density parity check (QC-LDPC) codes which have large girth for high speed optical communications. Compared with other method, our algorithm has lower complexity and faster speed.

Asia Communications and Photonics Conference•Jan 1, 2016•0 citations
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.
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.
In this paper, we study the cycle structure of quasi-cyclic (QC) low-density parity-check (LDPC) codes with the goal of obtaining the shortest code with a given degree distribution and girth. We focus on QC-LDPC codes, whose Tanner graphs are cyclic liftings of fully connected base graphs of size 3 × n, n ≥ 4, and obtain minimal lifting degrees that result in girths 6 and 8. This is performed through an efficient exhaustive search, and as a result, we also find all the possible non-isomorphic codes with the same minimum block length, girth, and degree distribution. The exhaustive search, which is ordinarily a formidable task, is made possible by pruning the search space of many codes that are isomorphic to those previously examined in the search process. Many of the pruning techniques proposed in this paper are also applicable to QC-LDPC codes with base graphs other than the 3 × n fully connected ones discussed here, as well as to codes with a larger girth. To further demonstrate the effectiveness of the pruning techniques, we use them to search for QC-LDPC codes with girths 10 and 12, and find a number of such codes that have a shorter block length compared with the best known similar codes in the literature. In addition, motivated by the exhaustive search results, we tighten the lower bound on the block length of QC-LDPC codes of girth 6 constructed from fully connected 3 × n base graphs, and construct codes that achieve the lower bound for an arbitrary value of n ≥ 4.
This article presents a highly flexible method for constructing high-girth quasi-cyclic low-density parity-check (QC-LDPC) codes. The proposed algorithm constructs a Tanner graph formed by connecting groups of rows (check nodes) and columns (variable nodes) of the constructed code. To obtain a sub-matrix structure, rows and columns are divided into groups of equal sizes. Rows and columns in a group are connected in their numerical (positional) order to obtain a cyclic structure. Connected rows and columns must satisfy the desired minimum cycle length. We present conditions that guarantee desired girths. The proposed algorithm is by far more flexible in constructing a wide range (rates and lengths) of regular and irregular QC-LDPC codes compared to existing methods. The algorithm, which has linear complexity with respect to the number of rows or columns, provides an easy and fast way to construct QC-LDPC codes. Constructed codes show good bit error rate performances.
We propose a new algorithm based on PEG algorithm to construct high-girth quasi-cyclic low-density parity check (QC-LDPC) codes. Before our improved algorithm in introduction, we depict the general algorithm based on PEG algorithm to construct QC - LDPC code, if necessary to eliminate the short cycles, that would bring in cycles-search. When code length of basic matrix is not too long, the algorithm is feasible, but with the code length growth, cycles-search will bring large of calculation and time-consuming sharply. Therefore we put forward an improved method by using the specific relation of basic matrix rows to replace traditional cycles-search, effectively eliminates short cycles, and largely reduces the time complexity at the same time. Through the simulation analysis, the performance can also be comparable with random constructed LDPC codes.
In this paper, we present an improved method for obtaining quasi-cyclic low-density parity-check (QC-LDPC) codes of larger length by combining some component QC-LDPC codes of smaller length.Large girth can be obtained by carefully designing one large girth component code of smaller length.The other component codes are properly designed to obtain a lot of QC-LDPC codes with much few short cycles.Simulations show that compared with CRT based QC-LDPC codes and PEG based QC-LDPC codes, the proposed QC-LDPC codes have much less short cycles and better performance.