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

Information Theory and Applications Workshop (ITA)

A transform approach for analyzing and constructing quasi-cyclic low-density parity-check codes

Qiuju Diao, Qin Huang, Shu Hwa Lin, Khaled Abdel-Ghaffar

Published Feb 1, 2011• 14 citations
Publisher

Abstract

An approach for studying quasi-cyclic codes based on matrix transformations via Fourier transforms and row and column permutations is presented. These transformations put a parity-check matrix in the form of an array of circulant matrices into a diagonal array of matrices of the same size over an extension field. The approach is used to characterize certain structural properties of low-density parity-check (LDPC) codes such as the girths of their Tanner graphs. Many constructions of quasi-cyclic LDPC codes can be unified under the proposed approach.

DOI
10.1109/ita.2011.5743557

Related papers

A matrix-theoretic approach for analyzing quasi-cyclic low-density parity-check codes

Qiuju Diao, Qin Huang, Shu Lin +1 more

A matrix-theoretic approach for studying quasi-cyclic codes based on matrix transformations via Fourier transforms and row and column permutations is developed. These transformations put a parity-check matrix in the form of an array of circulant matrices into a diagonal array of matrices of the same size over an extension field. The approach is amicable to the analysis and construction of quasi-cyclic low-density parity-check codes since it takes into account the specific parity-check matrix used for decoding with iterative message-passing algorithms. Based on this approach, the dimension of the codes and parity-check matrices for the dual codes can be determined. Several algebraic and geometric constructions of quasi-cyclic codes are presented as applications along with simulation results showing their performance over additive white Gaussian noise channels decoded with iterative message-passing algorithms.

IEEE Transactions on Information Theory•Jan 18, 2012•83 citations

A transform approach for constructing quasi-cyclic Euclidean geometry LDPC codes

Qiuju Diao, Wei Gang Zhou, Shu Hwa Lin +1 more

A method for constructing quasi-cyclic Euclidean geometry (QC-EG) LDPC codes in the Fourier transform domain is presented. Given a Euclidean geometry over a finite field of characteristic 2, base matrices in the Fourier transform domain are first constructed. Then the inverse Fourier transforms of these base matrices, combined with row and column permutations, result in low-density arrays of circulant permutation matrices and/or zero matrices. The null spaces of these low-density arrays give a family of QC-EG-LDPC codes. Codes in a special subclass have large minimum distances and their Tanner graphs contain no harmful trapping sets with sizes smaller than their minimum distances.

Information Theory and Applications Workshop (ITA)•Feb 1, 2012•3 citations

Cyclic and Quasi-Cyclic LDPC Codes on Constrained Parity-Check Matrices and Their Trapping Sets

Qin Huang, Qiuju Diao, Shu Lin +1 more

This paper is concerned with construction and structural analysis of both cyclic and quasi-cyclic codes, particularly low-density parity-check (LDPC) codes. It consists of three parts. The first part shows that a cyclic code given by a parity-check matrix in circulant form can be decomposed into descendant cyclic and quasi-cyclic codes of various lengths and rates. Some fundamental structural properties of these descendant codes are developed, including the characterization of the roots of the generator polynomial of a cyclic descendant code. The second part of the paper shows that cyclic and quasi-cyclic descendant LDPC codes can be derived from cyclic finite-geometry LDPC codes using the results developed in the first part of the paper. This enlarges the repertoire of cyclic LDPC codes. The third part of the paper analyzes the trapping set structure of regular LDPC codes whose parity-check matrices satisfy a certain constraint on their rows and columns. Several classes of finite-geometry and finite-field cyclic and quasi-cyclic LDPC codes with large minimum distances are shown to have no harmful trapping sets of size smaller than their minimum distances. Consequently, their error-floor performances are dominated by their minimum distances.

IEEE Transactions on Information Theory•Jan 31, 2012•108 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

Cyclic and Quasi-Cyclic LDPC Codes on Row and Column Constrained Parity-Check Matrices and Their Trapping Sets

Qin Huang, Qiuju Diao, Shu Lin +1 more

This paper is concerned with construction and structural analysis of both cyclic and quasi-cyclic codes, particularly LDPC codes. It consists of three parts. The first part shows that a cyclic code given by a parity-check matrix in circulant form can be decomposed into descendant cyclic and quasi-cyclic codes of various lengths and rates. Some fundamental structural properties of these descendant codes are developed, including the characterizations of the roots of the generator polynomial of a cyclic descendant code. The second part of the paper shows that cyclic and quasi-cyclic descendant LDPC codes can be derived from cyclic finite geometry LDPC codes using the results developed in first part of the paper. This enlarges the repertoire of cyclic LDPC codes. The third part of the paper analyzes the trapping sets of regular LDPC codes whose parity-check matrices satisfy a certain constraint on their rows and columns. Several classes of finite geometry and finite field cyclic and quasi-cyclic LDPC codes with large minimum weights are shown to have no harmful trapping sets with size smaller than their minimum weights. Consequently, their performance error-floors are dominated by their minimum weights.

arXiv:1012.3201•Dec 15, 2010•12 citations

Quasi-Cyclic Low Density Parity Check Codes

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 , and a relatively mild necessary and sufficient condition for the code to have a girth of or 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.

•Jan 1, 2003•0 citations
An approach for studying quasi-cyclic codes based on matrix transformations via Fourier transforms and row and column permutations is presented. These transformations put a parity-check matrix in the form of an array of circulant matrices into a diagonal array of matrices of the same size over an extension field. The approach is used to characterize certain structural properties of low-density parity-check (LDPC) codes such as the girths of their Tanner graphs. Many constructions of quasi-cyclic LDPC codes can be unified under the proposed approach.
A matrix-theoretic approach for studying quasi-cyclic codes based on matrix transformations via Fourier transforms and row and column permutations is developed. These transformations put a parity-check matrix in the form of an array of circulant matrices into a diagonal array of matrices of the same size over an extension field. The approach is amicable to the analysis and construction of quasi-cyclic low-density parity-check codes since it takes into account the specific parity-check matrix used for decoding with iterative message-passing algorithms. Based on this approach, the dimension of the codes and parity-check matrices for the dual codes can be determined. Several algebraic and geometric constructions of quasi-cyclic codes are presented as applications along with simulation results showing their performance over additive white Gaussian noise channels decoded with iterative message-passing algorithms.
A method for constructing quasi-cyclic Euclidean geometry (QC-EG) LDPC codes in the Fourier transform domain is presented. Given a Euclidean geometry over a finite field of characteristic 2, base matrices in the Fourier transform domain are first constructed. Then the inverse Fourier transforms of these base matrices, combined with row and column permutations, result in low-density arrays of circulant permutation matrices and/or zero matrices. The null spaces of these low-density arrays give a family of QC-EG-LDPC codes. Codes in a special subclass have large minimum distances and their Tanner graphs contain no harmful trapping sets with sizes smaller than their minimum distances.
This paper is concerned with construction and structural analysis of both cyclic and quasi-cyclic codes, particularly low-density parity-check (LDPC) codes. It consists of three parts. The first part shows that a cyclic code given by a parity-check matrix in circulant form can be decomposed into descendant cyclic and quasi-cyclic codes of various lengths and rates. Some fundamental structural properties of these descendant codes are developed, including the characterization of the roots of the generator polynomial of a cyclic descendant code. The second part of the paper shows that cyclic and quasi-cyclic descendant LDPC codes can be derived from cyclic finite-geometry LDPC codes using the results developed in the first part of the paper. This enlarges the repertoire of cyclic LDPC codes. The third part of the paper analyzes the trapping set structure of regular LDPC codes whose parity-check matrices satisfy a certain constraint on their rows and columns. Several classes of finite-geometry and finite-field cyclic and quasi-cyclic LDPC codes with large minimum distances are shown to have no harmful trapping sets of size smaller than their minimum distances. Consequently, their error-floor performances are dominated by their minimum distances.
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.
This paper is concerned with construction and structural analysis of both cyclic and quasi-cyclic codes, particularly LDPC codes. It consists of three parts. The first part shows that a cyclic code given by a parity-check matrix in circulant form can be decomposed into descendant cyclic and quasi-cyclic codes of various lengths and rates. Some fundamental structural properties of these descendant codes are developed, including the characterizations of the roots of the generator polynomial of a cyclic descendant code. The second part of the paper shows that cyclic and quasi-cyclic descendant LDPC codes can be derived from cyclic finite geometry LDPC codes using the results developed in first part of the paper. This enlarges the repertoire of cyclic LDPC codes. The third part of the paper analyzes the trapping sets of regular LDPC codes whose parity-check matrices satisfy a certain constraint on their rows and columns. Several classes of finite geometry and finite field cyclic and quasi-cyclic LDPC codes with large minimum weights are shown to have no harmful trapping sets with size smaller than their minimum weights. Consequently, their performance error-floors are dominated by their minimum weights.
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 , and a relatively mild necessary and sufficient condition for the code to have a girth of or 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.