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

EURASIP Journal on Wireless Communications and Networking

High Girth Column-Weight-Two LDPC Codes Based on Distance Graphs

Gabofetswe Malema, Michael John Liebelt

Published Jan 28, 2007• 13 citations
Publisher

Abstract

LDPC codes of column weight of two are constructed from minimal distance graphs or cages. Distance graphs are used to represent LDPC code matrices such that graph vertices that represent rows and edges are columns. The conversion of a distance graph into matrix form produces an adjacency matrix with column weight of two and girth double that of the graph. The number of 1's in each row (row weight) is equal to the degree of the corresponding vertex. By constructing graphs with different vertex degrees, we can vary the rate of corresponding LDPC code matrices. Cage graphs are used as examples of distance graphs to design codes with different girths and rates. Performance of obtained codes depends on girth and structure of the corresponding distance graphs.

DOI
10.1155/2007/48158

Related papers

Row and Column Extensions of 4-Cycle Free LDPC Codes

Mohammad Gholami, Akram Nassaj

In this letter, an approach is proposed to increase the row (column)-weight of the parity-check matrix of a 4-cycle free LDPC code such that the constructed LDPC code has girth of at least 6. In fact, to each parity-check matrix H, a new graph Gr(H) (Gc(H)) is assigned in which the vertices correspond to the rows (columns) of H and two vertices are adjacent if and only if the associated rows (columns) have in common at least one nonzero element. Now, in a proper vertex coloring of Gr(H) (Gc(H)), each color is considered as a new column (row) whose nonzero elements happen in the rows (columns) in which the corresponding vertices have the same color. Based on this method, some high-rate LDPC codes with girth 6 and column-weight of at least 4 can be constructed from the recently proposed column-weight three LDPC codes with girth 6. Moreover, using the mutually orthogonal Latin squares, this approach is applied on the incidence matrices of some complete bipartite graphs to generate some girth-6 LDPC codes with different column-weights and large minimum-distances.

IEEE Communications Letters•Nov 4, 2015•3 citations

Maximum-Girth Cylinder-Type Block-Circulant LDPC Codes

Mohammad Gholami, Morteza Esmaeili

In this paper, a particular class of block-circulant low-density parity-check (BC-LDPC) codes referred to as cylinder-type BC-LDPC (CTBC-LDPC) codes is studied. We represent a cylinder-type parity-check matrix H by a graph called the block-structure graph of H and denoted by BSG(H). Using the properties of BSG(H) we show that CTBC matrices with column-weight two and girth an arbitrary multiple of 8 can be constructed, while for a CTBC matrix H with column-weight ℓ ≥ 3 this girth cannot exceed 12. An algorithm generating CTBC-LDPC codes of arbitrary possible girth is given. The algorithm produces a large group of codes with flexible rate, length and girth. From performance perspective over AWGN channel, the maximum girth-12 CTBC-LDPC codes with column-weight at least three generated by the given algorithm are at least as good as their random-like counterpart codes and outperform the codes of the same size constructed by successive-level-growth, progressive-edge-growth, and partition-and-shift methods.

IEEE Transactions on Communications•Mar 6, 2012•8 citations

Graph-based convolutional and block LDPC codes

Irina E. Bocharova, Boris D. Kudryashov, Roman V. Satyukov

We consider regular block and convolutional LDPC codes determined by paritycheck matrices with rows of a fixed weight and columns of weight 2. Such codes can be described by graphs, and the minimum distance of a code coincides with the girth of the corresponding graph. We consider a description of such codes in the form of tail-biting convolutional codes. Long codes are constructed from short ones using the “voltage graph” method. On this way we construct new codes, find a compact description for many known optimal codes, and thus simplify the coding for such codes. We obtain an asymptotic lower bound on the girth of the corresponding graphs. We also present tables of codes.

Problems of Information Transmission•Dec 1, 2009•12 citations

Double Cylinder Cycle codes of Arbitrary Girth

Mehdi Samadieh, Mohammad Gholami

A particular class of low-density parity-check codes referred to as cylinder-type BC-LDPC codes is proposed by Gholami and Eesmaeili. In this paper We represent a double cylinder-type parity-check matrix H by a graph called the block-structure graph of H and denoted by BSG(H). Using the properties of BSG(H) we propose some mother matrices with column-weight two such that the rate of corresponding cycle codes are greater tan cycle codes constructed by Gholami with same girth.

arXiv:1403.0804•Feb 10, 2014•1 citation

Geometrically-structured maximum-girth LDPC block and convolutional codes

Morteza Esmaeili, Mohammad Gholami

Four classes of maximum-girth geometrically structured column-weight-two regular quasi-cyclic (QC) low-density parity-check (LDPC) codes are introduced. Two classes of these codes, referred to as Type-I and Type-II codes, are with row-weights 4 and 3, and maximum girths 16 and 24, respectively. The idea behind the construction of these two classes of codes, with rates at least 1/2 and 1/3, is slightly generalized to obtain two classes of variable-high-rate codes, referred to as Type-III1 and Type-III2 codes, with maximum girth 20 and 16, respectively. A low-complexity deterministic algorithm for constructing these four classes of codes is given. The algorithm generates maximum-girth Type-I and Type-II codes with almost arbitrary length eta not less than 216 and 243, respectively. The output of the algorithm substantially improves on some of the previously best known codes constructed using a randomized progressive edge-growth (RPEG) algorithm. For instance, we have rate-0.71 Type-III1 codes of lengths 308 and 728 with girths 10 and 12, respectively, versus the code lengths 385 and 840 obtained by the RPEG algorithm. Simulation results on AWGN channel confirm that, from BER performance perspective, the constructed LDPC codes are superior to the column-weight-two LDPC codes constructed by the previously reported methods. The generator matrix G(D) of the convolutional codes associated with Type-I and Type-II codes is given. The free distance dfreeof such a convolutional code is equal to the minimum distance of the corresponding QC block code.

IEEE Journal on Selected Areas in Communications•Jul 29, 2009•24 citations

Quasi-Cyclic LDPC Codes of Column-Weight Two Using a Search Algorithm

Gabofetswe Malema, Michael John Liebelt

This article introduces a search algorithm for constructing quasi-cyclic LDPC codes of column-weight two. To obtain a submatrix structure, rows are divided into groups of equal sizes. Rows in a group are connected in their numerical order to obtain a cyclic structure. Two rows forming a column must be at a specified distance from each other to obtain a given girth. The search for rows satisfying the distance is done sequentially or randomly. Using the proposed algorithm regular and irregular column-weight-two codes are obtained over a wide range of girths, rates, and lengths. The algorithm, which has a complexity linear with respect to the number of rows, provides an easy and fast way to construct quasi-cyclic LDPC codes. Constructed codes show good bit-error rate performance with randomly shifted codes performing better than sequentially shifted ones.

EURASIP Journal on Advances in Signal Processing•Apr 19, 2007•12 citations
LDPC codes of column weight of two are constructed from minimal distance graphs or cages. Distance graphs are used to represent LDPC code matrices such that graph vertices that represent rows and edges are columns. The conversion of a distance graph into matrix form produces an adjacency matrix with column weight of two and girth double that of the graph. The number of 1's in each row (row weight) is equal to the degree of the corresponding vertex. By constructing graphs with different vertex degrees, we can vary the rate of corresponding LDPC code matrices. Cage graphs are used as examples of distance graphs to design codes with different girths and rates. Performance of obtained codes depends on girth and structure of the corresponding distance graphs.
In this letter, an approach is proposed to increase the row (column)-weight of the parity-check matrix of a 4-cycle free LDPC code such that the constructed LDPC code has girth of at least 6. In fact, to each parity-check matrix H, a new graph Gr(H) (Gc(H)) is assigned in which the vertices correspond to the rows (columns) of H and two vertices are adjacent if and only if the associated rows (columns) have in common at least one nonzero element. Now, in a proper vertex coloring of Gr(H) (Gc(H)), each color is considered as a new column (row) whose nonzero elements happen in the rows (columns) in which the corresponding vertices have the same color. Based on this method, some high-rate LDPC codes with girth 6 and column-weight of at least 4 can be constructed from the recently proposed column-weight three LDPC codes with girth 6. Moreover, using the mutually orthogonal Latin squares, this approach is applied on the incidence matrices of some complete bipartite graphs to generate some girth-6 LDPC codes with different column-weights and large minimum-distances.
In this paper, a particular class of block-circulant low-density parity-check (BC-LDPC) codes referred to as cylinder-type BC-LDPC (CTBC-LDPC) codes is studied. We represent a cylinder-type parity-check matrix H by a graph called the block-structure graph of H and denoted by BSG(H). Using the properties of BSG(H) we show that CTBC matrices with column-weight two and girth an arbitrary multiple of 8 can be constructed, while for a CTBC matrix H with column-weight ℓ ≥ 3 this girth cannot exceed 12. An algorithm generating CTBC-LDPC codes of arbitrary possible girth is given. The algorithm produces a large group of codes with flexible rate, length and girth. From performance perspective over AWGN channel, the maximum girth-12 CTBC-LDPC codes with column-weight at least three generated by the given algorithm are at least as good as their random-like counterpart codes and outperform the codes of the same size constructed by successive-level-growth, progressive-edge-growth, and partition-and-shift methods.
We consider regular block and convolutional LDPC codes determined by paritycheck matrices with rows of a fixed weight and columns of weight 2. Such codes can be described by graphs, and the minimum distance of a code coincides with the girth of the corresponding graph. We consider a description of such codes in the form of tail-biting convolutional codes. Long codes are constructed from short ones using the “voltage graph” method. On this way we construct new codes, find a compact description for many known optimal codes, and thus simplify the coding for such codes. We obtain an asymptotic lower bound on the girth of the corresponding graphs. We also present tables of codes.
Four classes of maximum-girth geometrically structured column-weight-two regular quasi-cyclic (QC) low-density parity-check (LDPC) codes are introduced. Two classes of these codes, referred to as Type-I and Type-II codes, are with row-weights 4 and 3, and maximum girths 16 and 24, respectively. The idea behind the construction of these two classes of codes, with rates at least 1/2 and 1/3, is slightly generalized to obtain two classes of variable-high-rate codes, referred to as Type-III1 and Type-III2 codes, with maximum girth 20 and 16, respectively. A low-complexity deterministic algorithm for constructing these four classes of codes is given. The algorithm generates maximum-girth Type-I and Type-II codes with almost arbitrary length eta not less than 216 and 243, respectively. The output of the algorithm substantially improves on some of the previously best known codes constructed using a randomized progressive edge-growth (RPEG) algorithm. For instance, we have rate-0.71 Type-III1 codes of lengths 308 and 728 with girths 10 and 12, respectively, versus the code lengths 385 and 840 obtained by the RPEG algorithm. Simulation results on AWGN channel confirm that, from BER performance perspective, the constructed LDPC codes are superior to the column-weight-two LDPC codes constructed by the previously reported methods. The generator matrix G(D) of the convolutional codes associated with Type-I and Type-II codes is given. The free distance dfreeof such a convolutional code is equal to the minimum distance of the corresponding QC block code.
This article introduces a search algorithm for constructing quasi-cyclic LDPC codes of column-weight two. To obtain a submatrix structure, rows are divided into groups of equal sizes. Rows in a group are connected in their numerical order to obtain a cyclic structure. Two rows forming a column must be at a specified distance from each other to obtain a given girth. The search for rows satisfying the distance is done sequentially or randomly. Using the proposed algorithm regular and irregular column-weight-two codes are obtained over a wide range of girths, rates, and lengths. The algorithm, which has a complexity linear with respect to the number of rows, provides an easy and fast way to construct quasi-cyclic LDPC codes. Constructed codes show good bit-error rate performance with randomly shifted codes performing better than sequentially shifted ones.