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

arXiv:2610.03341

Low-Density Parity-Check Codes of High Girth from Permutation Polynomials

Tasawwar Hussain, Anthony Gómez-Fonseca, Tefjol Pllaha

Published Oct 2, 2026• 0 citations
arXivHTMLPDF

Abstract

Quasi-cyclic low-density parity-check (QC-LDPC) codes are widely used in modern communication standards due to their simple structure and efficient encoder and decoder implementations. However, the commutativity of the circulant permutation matrices used in their construction significantly limits their girth and minimum distance, affecting iterative decoding performance. In this paper, we investigate protograph-based codes constructed using permutation polynomials of higher degree, focusing on a closed family of non-commuting binomial permutation polynomials that enables these constructions to exceed both of these girth and minimum distance upper bounds while maintaining a simple representation. Simulation results demonstrate improved decoding performance compared to constructions based on affine permutation polynomials, which include QC-LDPC codes.

Related papers

Constructing good QC-LDPC codes by pre-lifting protographs

David G. M. Mitchell, Roxana Smarandache, Daniel J. Costello

Quasi-cyclic (QC) low-density parity-check (LDPC) codes are of great interest to code designers because of their implementation advantages and algebraic properties that facilitate their analysis. In this paper, we present some new results on QC-LDPC codes that are constructed using a two-step lifting procedure based on a protograph, and, by implementing this method instead of the usual one-step procedure, we are able to show improved minimum distance and girth properties. We also present two design rules to construct QC-LDPC codes: one uses only circulant permutation matrices at the first (pre-lifting) stage and the other uses a selection of non-commuting permutation matrices. For both techniques, we obtain a demonstrable increase in the minimum distance compared to a one-step circulant-based lifting. The expected performance improvement is verified by simulation results.

IEEE Information Theory Workshop (ITW)•Sep 1, 2012•4 citations

Quasi-Cyclic LDPC Codes Based on Pre-Lifted Protographs

David G. M. Mitchell, Roxana Smarandache, Daniel J. Costello

Quasi-cyclic low-density parity-check (QC-LDPC) codes based on protographs are of great interest to code designers because analysis and implementation are facilitated by the protograph structure and the use of circulant permutation matrices for protograph lifting. However, these restrictions impose undesirable fixed upper limits on important code parameters, such as minimum distance and girth. In this paper, we consider an approach to constructing QC-LDPC codes that uses a two-step lifting procedure based on a protograph, and, by following this method instead of the usual one-step procedure, we obtain improved minimum distance and girth properties. We also present two new design rules for constructing good QC-LDPC codes using this two-step lifting procedure, and in each case, we obtain a significant increase in minimum distance and achieve a certain guaranteed girth compared with one-step circulant-based liftings. The expected performance improvement is verified by simulation results.

arXiv:1407.5364•IEEE Transactions on Information Theory•Jul 24, 2014•58 citations

Low Density Parity-Check Codes Based on Affine Permutation Matrices

Zhongxun Wang, Ling Sun, Yang Xi

Recently, Low Density Parity-Check (LDPC) codes based on Affine Permutation Matrices (APM) drew lots of attention. Compared with the Quasi-Cyclic LDPC (QC-LDPC) codes, these kinds of codes have some advantages. APM-LDPC codes obtain lower cycle-distributions, minimum hamming distance and greater girth. This paper explains the importance of cyclic distribution by comparing APM-LDPC codes with QC-LDPC codes. Then a particular form of APM-LDPC codes is proposed and researched. The new codes can low down the cycle-distribution to larger extent. In the following research, an effective method, which constructs the new codes with fixed girth, is proposed. Simulations show that the construction method is reasonable and effective. The transmission performances are better than the traditional methods, as well. Finally, the implementation and verification are carried out on FPGA.

International Journal of Pattern Recognition and Artificial Intelligence•Jun 29, 2020•0 citations

Linear Permutation Polynomial Codes

Ryoichiro Yoshida, Kenta Kasai

Quasi-cyclic low-density parity-check (QC-LDPC) codes are one of the most important code classes of LDPC codes. They have two drawbacks: lack of randomness and limited girth lead to a degraded decoding performance in the waterfall and error floor regions, respectively. To tackle these problems, we present a new class of LDPC codes, named linear permutation polynomial (LPP) codes, whose parity-check matrix consists of permutation matrices based on LPPs. The girth of regular QC-LDPC codes is upper bounded by 12, while LPP codes break this limit. We demonstrate that LPP codes have error performance almost equivalent to random ones.

IEEE International Symposium on Information Theory (ISIT)•Jul 1, 2019•4 citations

Quasi-Cyclic Low-Density Parity-Check Codes From Circulant Permutation Matrices

M.P.C. Fossorier

In this correspondence, the construction of low-density parity-check (LDPC) codes from circulant permutation matrices is investigated. It is shown that such codes cannot have a Tanner graph representation with girth larger than 12, and a relatively mild necessary and sufficient condition for the code to have a girth of 6, 8,10, or 12 is derived. These results suggest that families of LDPC codes with such girth values are relatively easy to obtain and, consequently, additional parameters such as the minimum distance or the number of redundant check sums should be considered. To this end, a necessary condition for the codes investigated to reach their maximum possible minimum Hamming distance is proposed.

IEEE Transactions on Information Theory•Jul 27, 2004•1,234 citations

LDPC Block and Convolutional Codes Based on Circulant Matrices

R. Michael Tanner, Deepak Sridhara, Arvind Sridharan +2 more

A class of algebraically structured quasi-cyclic (QC) low-density parity-check (LDPC) codes and their convolutional counterparts is presented. The QC codes are described by sparse parity-check matrices comprised of blocks of circulant matrices. The sparse parity-check representation allows for practical graph-based iterative message-passing decoding. Based on the algebraic structure, bounds on the girth and minimum distance of the codes are found, and several possible encoding techniques are described. The performance of the QC LDPC block codes compares favorably with that of randomly constructed LDPC codes for short to moderate block lengths. The performance of the LDPC convolutional codes is superior to that of the QC codes on which they are based; this performance is the limiting performance obtained by increasing the circulant size of the base QC code. Finally, a continuous decoding procedure for the LDPC convolutional codes is described.

IEEE Transactions on Information Theory•Nov 30, 2004•583 citations
Quasi-cyclic low-density parity-check (QC-LDPC) codes are widely used in modern communication standards due to their simple structure and efficient encoder and decoder implementations. However, the commutativity of the circulant permutation matrices used in their construction significantly limits their girth and minimum distance, affecting iterative decoding performance. In this paper, we investigate protograph-based codes constructed using permutation polynomials of higher degree, focusing on a closed family of non-commuting binomial permutation polynomials that enables these constructions to exceed both of these girth and minimum distance upper bounds while maintaining a simple representation. Simulation results demonstrate improved decoding performance compared to constructions based on affine permutation polynomials, which include QC-LDPC codes.
Quasi-cyclic (QC) low-density parity-check (LDPC) codes are of great interest to code designers because of their implementation advantages and algebraic properties that facilitate their analysis. In this paper, we present some new results on QC-LDPC codes that are constructed using a two-step lifting procedure based on a protograph, and, by implementing this method instead of the usual one-step procedure, we are able to show improved minimum distance and girth properties. We also present two design rules to construct QC-LDPC codes: one uses only circulant permutation matrices at the first (pre-lifting) stage and the other uses a selection of non-commuting permutation matrices. For both techniques, we obtain a demonstrable increase in the minimum distance compared to a one-step circulant-based lifting. The expected performance improvement is verified by simulation results.
Quasi-cyclic low-density parity-check (QC-LDPC) codes based on protographs are of great interest to code designers because analysis and implementation are facilitated by the protograph structure and the use of circulant permutation matrices for protograph lifting. However, these restrictions impose undesirable fixed upper limits on important code parameters, such as minimum distance and girth. In this paper, we consider an approach to constructing QC-LDPC codes that uses a two-step lifting procedure based on a protograph, and, by following this method instead of the usual one-step procedure, we obtain improved minimum distance and girth properties. We also present two new design rules for constructing good QC-LDPC codes using this two-step lifting procedure, and in each case, we obtain a significant increase in minimum distance and achieve a certain guaranteed girth compared with one-step circulant-based liftings. The expected performance improvement is verified by simulation results.
Recently, Low Density Parity-Check (LDPC) codes based on Affine Permutation Matrices (APM) drew lots of attention. Compared with the Quasi-Cyclic LDPC (QC-LDPC) codes, these kinds of codes have some advantages. APM-LDPC codes obtain lower cycle-distributions, minimum hamming distance and greater girth. This paper explains the importance of cyclic distribution by comparing APM-LDPC codes with QC-LDPC codes. Then a particular form of APM-LDPC codes is proposed and researched. The new codes can low down the cycle-distribution to larger extent. In the following research, an effective method, which constructs the new codes with fixed girth, is proposed. Simulations show that the construction method is reasonable and effective. The transmission performances are better than the traditional methods, as well. Finally, the implementation and verification are carried out on FPGA.
Quasi-cyclic low-density parity-check (QC-LDPC) codes are one of the most important code classes of LDPC codes. They have two drawbacks: lack of randomness and limited girth lead to a degraded decoding performance in the waterfall and error floor regions, respectively. To tackle these problems, we present a new class of LDPC codes, named linear permutation polynomial (LPP) codes, whose parity-check matrix consists of permutation matrices based on LPPs. The girth of regular QC-LDPC codes is upper bounded by 12, while LPP codes break this limit. We demonstrate that LPP codes have error performance almost equivalent to random ones.
In this correspondence, the construction of low-density parity-check (LDPC) codes from circulant permutation matrices is investigated. It is shown that such codes cannot have a Tanner graph representation with girth larger than 12, and a relatively mild necessary and sufficient condition for the code to have a girth of 6, 8,10, or 12 is derived. These results suggest that families of LDPC codes with such girth values are relatively easy to obtain and, consequently, additional parameters such as the minimum distance or the number of redundant check sums should be considered. To this end, a necessary condition for the codes investigated to reach their maximum possible minimum Hamming distance is proposed.
A class of algebraically structured quasi-cyclic (QC) low-density parity-check (LDPC) codes and their convolutional counterparts is presented. The QC codes are described by sparse parity-check matrices comprised of blocks of circulant matrices. The sparse parity-check representation allows for practical graph-based iterative message-passing decoding. Based on the algebraic structure, bounds on the girth and minimum distance of the codes are found, and several possible encoding techniques are described. The performance of the QC LDPC block codes compares favorably with that of randomly constructed LDPC codes for short to moderate block lengths. The performance of the LDPC convolutional codes is superior to that of the QC codes on which they are based; this performance is the limiting performance obtained by increasing the circulant size of the base QC code. Finally, a continuous decoding procedure for the LDPC convolutional codes is described.