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

International Symposium on Information Theory and its Applications

Circulant decomposition: Cyclic, quasi-cyclic and LDPC codes

Qin Huang, Qiuju Diao, Shu Lin

Published Oct 1, 2010• 5 citations
Publisher

Abstract

This paper shows that a cyclic code can be put into quasi-cyclic form by decomposing a circular parity-check matrix through column and row permutations. Such a decomposition of a circular parity-check matrix of a cyclic code produces a group of shorter cyclic or quasi-cyclic codes and leads to a new method for constructing long cyclic codes from short cyclic codes. Also in this paper, new classes of cyclic and quasi-cyclic LDPC codes are derived from cyclic Euclidean geometry LDPC codes by decomposing their circular parity-check matrices. These new LDPC codes perform well and enlarge the repertoire of cyclic and quasi-cyclic LDPC codes.

DOI
10.1109/isita.2010.5649214

Related papers

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

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

Cyclic and quasi-cyclic LDPC codes: New developments

Qin Huang, Qiuju Diao, Shu Lin +1 more

This paper presents a technique to decompose a cyclic code given by a parity-check matrix in circulant form into descendant cyclic and quasi-cyclic codes of various length and rates. Based on this technique, cyclic finite geometry (FG) LDPC codes are decomposed into a large class of cyclic FG-LDPC codes and a large class of quasi-cyclic FG-LDPC codes.

Information Theory and Applications Workshop (ITA)•Feb 1, 2011•11 citations

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

Qiuju Diao, Qin Huang, Shu Hwa Lin +1 more

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.

Information Theory and Applications Workshop (ITA)•Feb 1, 2011•14 citations

Quasi-Cyclic LDPC Codes on Cyclic Subgroups of Finite Fields

Li Guo Zhang, Shu Lin, Khaled Abdel-Ghaffar +2 more

A new class of quasi-cyclic LDPC codes whose parity-check matrices are arrays of circulant permutation matrices constructed based on cyclic subgroups of finite fields is presented. This class of codes contains several known classes of algebraic quasi-cyclic LDPC codes as subclasses. Experimental results show that the codes constructed perform very well over the AWGN channel when decoded with iterative decoding based on belief propagation. This class of new QC-LDPC codes contains a subclass of codes which have large minimum distances. Combinatorial expressions for the ranks of the parity-check matrices of a subclass of codes constructed based on fields of characteristic two are given.

IEEE Transactions on Communications•Jun 28, 2011•34 citations

QC-LDPC Codes Construction by Concatenating of Circulant Matrices as Block-Columns

Mohammad Hesam Tadayon, Mohammad Mohammadi

In this paper a new low complexity method for constructing binary quasi-cyclic low-density parity-check (QC-LDPC) codes is introduced. In the proposed method, each block-column of the parity check matrix H is made by a circulant matrix in a way that the associated Tanner graph is free of cycle four. Each circulant matrix in H is made by a generator column. The generator columns should be selected in a way that each associated circulant matrix and every two distinct circulant matrices are free of cycle four. The generator columns are made by row distance sets. An algorithm for generating distance sets and obtaining circulant matrices with columns of weight three is presented separately. Simplicity of construction and having a good flexible family of quasi cyclic LDPC codes both in rate and length are the main properties of the proposed method. The performance of the proposed codes is compared with that of the random-like and Array LDPC codes over an AWGN channel. Simulation results show that from the performance perspective, the constructed codes are competitive with random-like and Array LDPC codes.

International Journal of Information & Communication Technology Research•Jun 15, 2016•0 citations
This paper shows that a cyclic code can be put into quasi-cyclic form by decomposing a circular parity-check matrix through column and row permutations. Such a decomposition of a circular parity-check matrix of a cyclic code produces a group of shorter cyclic or quasi-cyclic codes and leads to a new method for constructing long cyclic codes from short cyclic codes. Also in this paper, new classes of cyclic and quasi-cyclic LDPC codes are derived from cyclic Euclidean geometry LDPC codes by decomposing their circular parity-check matrices. These new LDPC codes perform well and enlarge the repertoire of cyclic and quasi-cyclic 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.
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.
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 new class of quasi-cyclic LDPC codes whose parity-check matrices are arrays of circulant permutation matrices constructed based on cyclic subgroups of finite fields is presented. This class of codes contains several known classes of algebraic quasi-cyclic LDPC codes as subclasses. Experimental results show that the codes constructed perform very well over the AWGN channel when decoded with iterative decoding based on belief propagation. This class of new QC-LDPC codes contains a subclass of codes which have large minimum distances. Combinatorial expressions for the ranks of the parity-check matrices of a subclass of codes constructed based on fields of characteristic two are given.
In this paper a new low complexity method for constructing binary quasi-cyclic low-density parity-check (QC-LDPC) codes is introduced. In the proposed method, each block-column of the parity check matrix H is made by a circulant matrix in a way that the associated Tanner graph is free of cycle four. Each circulant matrix in H is made by a generator column. The generator columns should be selected in a way that each associated circulant matrix and every two distinct circulant matrices are free of cycle four. The generator columns are made by row distance sets. An algorithm for generating distance sets and obtaining circulant matrices with columns of weight three is presented separately. Simplicity of construction and having a good flexible family of quasi cyclic LDPC codes both in rate and length are the main properties of the proposed method. The performance of the proposed codes is compared with that of the random-like and Array LDPC codes over an AWGN channel. Simulation results show that from the performance perspective, the constructed codes are competitive with random-like and Array LDPC codes.