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

Superposition Construction of Q-ary LDPC Codes by Jointly Optimizing Girth and Number of Shortest Cycles

Hengzhou Xu, Baoming Bai

Published Jan 1, 2016• 25 citations
Publisher

Abstract

In this letter, we consider the construction of q-ary low-density parity-check (LDPC) codes by jointly optimizing the girth and number of shortest cycles in the frame of superposition. We begin with constructing binary quasi-cyclic LDPC codes by superposition. By replacing the nonzero entries of the parity-check matrices of the resulting binary codes with the nonzero elements of GF(q), a class of q-ary LDPC codes is obtained. Furthermore, we analyze the cycle structure of the constructed codes for a given degree distribution and code length, and present a search algorithm for finding q-ary LDPC codes with few cycles of length g, where g is the optimized girth value. Simulation results show that the proposed codes perform well under the iterative decoding algorithms.

DOI
10.1109/lcomm.2016.2564401

Related papers

Construction of QC-LDPC Codes Based on Pre-Masking and Local Optimal Searching

Dongdong Wang, Liqian Wang, Xue Chen +3 more

In this letter, we consider the construction of quasi-cyclic (QC) low-density parity-check (LDPC) codes by jointly optimizing the girth g and the number of g-cycles. We first propose a sub-array detection method to accelerate the detection of cycles, and by detecting the non-repeated automatic enumerative cycles in the frame of sub-arrays, cycle detection time can be greatly reduced. Furthermore, a local optimal searching algorithm combined with pre-masking is presented, by orderly searching the local optimal p j,l for each circulant permutation matrix (CPM), a class of QC-LDPC codes with possibly enlarged g, less number of g-cycles, and arbitrary attainable degree distribution could be constructed. Simulation results show that the codes constructed by the proposed method perform well in error floor region.

IEEE Communications Letters•Sep 25, 2017•9 citations

A Method for Constructing Parity-Check Matrices of Quasi-Cyclic LDPC Codes Over GF(q)

Stanislav Kruglik, Valeriya Potapova, Alexey Frolov

Abstract An algorithm for constructing parity-check matrices of non-binary quasi-cyclic low-density parity-check (NB QC-LDPC) codes is proposed. The algorithm finds short cycles in the base matrix and tries to eliminate them by selecting the circulants and the elements of GF(q). The algorithm tries to eliminate the cycles with the smallest number edges going outside the cycle. The efficiency of the algorithm is demonstrated by means of simulations. In order to explain the simulation results we also derive upper bounds on the minimum distance of NB QC-LDPC codes.

Journal of Communications Technology and Electronics•Dec 1, 2018•2 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

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

Quasi-Cyclic Low-Density Parity-Check Codes Based on Progressive Cycle Growth Algorithm

Yuanhua Liu, Meiling Zhang, Niu Xin-Liang

Short cycles in the Tanner graph of a given LDPC code has negative effect on the performance of iterative decoding. To improve the performance, we presented an approach for constructing Quasi-Cyclic Low-Density Parity-Check (QC-LDPC) codes whose associated Tanner graph has large girth and a small amount of short cycles. Each column block of the parity check matrix was designed by adding circulant permutation sub-matrices one after another, provided the current parity check matrix has minimal number of short cycles. The condition for the proposed QC-LDPC codes to have girth at least 6 was also analyzed. Regular and irregular QC-LDPC codes with various lengths and rates can be constructed. Simulations show that the proposed QC-LDPC codes have less short cycles and better performance than existing progressive edge growth based QC-LDPC codes.

International Conference on Instrumentation and Measurement, Computer, Communication and Control (IMCCC)•Jul 1, 2016•1 citation

A method for constructing parity-check matrices of non-binary quasi-cyclic LDPC codes

Stanislav Kruglik, Valeriya Potapova, Alexey Frolov

An algorithm for constructing parity-check matrices of non-binary quasi-cyclic low-density parity-check (NB QC-LDPC) codes is proposed. The algorithm finds short cycles in the base matrix and tries to eliminate them by selecting the circulants and the elements of GF(q). Firstly the algorithm tries to eliminate the cycles with the smallest number edges going outside the cycle. The efficiency of the algorithm is demonstrated by means of simulations. In particular, it was shown that NB QC-LDPC codes constructed with use of our algorithm loose less that 0.1 dB in comparison to the best NB LDPC codes.

arXiv:1705.10717•May 30, 2017•0 citations
In this letter, we consider the construction of q-ary low-density parity-check (LDPC) codes by jointly optimizing the girth and number of shortest cycles in the frame of superposition. We begin with constructing binary quasi-cyclic LDPC codes by superposition. By replacing the nonzero entries of the parity-check matrices of the resulting binary codes with the nonzero elements of GF(q), a class of q-ary LDPC codes is obtained. Furthermore, we analyze the cycle structure of the constructed codes for a given degree distribution and code length, and present a search algorithm for finding q-ary LDPC codes with few cycles of length g, where g is the optimized girth value. Simulation results show that the proposed codes perform well under the iterative decoding algorithms.
In this letter, we consider the construction of quasi-cyclic (QC) low-density parity-check (LDPC) codes by jointly optimizing the girth g and the number of g-cycles. We first propose a sub-array detection method to accelerate the detection of cycles, and by detecting the non-repeated automatic enumerative cycles in the frame of sub-arrays, cycle detection time can be greatly reduced. Furthermore, a local optimal searching algorithm combined with pre-masking is presented, by orderly searching the local optimal p j,l for each circulant permutation matrix (CPM), a class of QC-LDPC codes with possibly enlarged g, less number of g-cycles, and arbitrary attainable degree distribution could be constructed. Simulation results show that the codes constructed by the proposed method perform well in error floor region.
Abstract An algorithm for constructing parity-check matrices of non-binary quasi-cyclic low-density parity-check (NB QC-LDPC) codes is proposed. The algorithm finds short cycles in the base matrix and tries to eliminate them by selecting the circulants and the elements of GF(q). The algorithm tries to eliminate the cycles with the smallest number edges going outside the cycle. The efficiency of the algorithm is demonstrated by means of simulations. In order to explain the simulation results we also derive upper bounds on the minimum distance of NB QC-LDPC codes.
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 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.
Short cycles in the Tanner graph of a given LDPC code has negative effect on the performance of iterative decoding. To improve the performance, we presented an approach for constructing Quasi-Cyclic Low-Density Parity-Check (QC-LDPC) codes whose associated Tanner graph has large girth and a small amount of short cycles. Each column block of the parity check matrix was designed by adding circulant permutation sub-matrices one after another, provided the current parity check matrix has minimal number of short cycles. The condition for the proposed QC-LDPC codes to have girth at least 6 was also analyzed. Regular and irregular QC-LDPC codes with various lengths and rates can be constructed. Simulations show that the proposed QC-LDPC codes have less short cycles and better performance than existing progressive edge growth based QC-LDPC codes.
An algorithm for constructing parity-check matrices of non-binary quasi-cyclic low-density parity-check (NB QC-LDPC) codes is proposed. The algorithm finds short cycles in the base matrix and tries to eliminate them by selecting the circulants and the elements of GF(q). Firstly the algorithm tries to eliminate the cycles with the smallest number edges going outside the cycle. The efficiency of the algorithm is demonstrated by means of simulations. In particular, it was shown that NB QC-LDPC codes constructed with use of our algorithm loose less that 0.1 dB in comparison to the best NB LDPC codes.