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

Edge-Coloring Technique to Analyze Elementary Trapping Sets of Spatially-Coupled LDPC Convolutional Codes

Mohammad‐Reza Sadeghi, Farzane Amirzade

Published Dec 27, 2019• 15 citations
Publisher

Abstract

In this letter, for the first time, an edge-coloring technique is proposed to characterize a certain elementary trapping set (ETS) and to obtain sufficient conditions to avoid small ETSs from occurrence in the Tanner graph of SC-LDPC convolutional codes. This technique is applicable to all protograph-based LDPC codes with different girths whose protographs are single-edge, that is, the entries of their base matrices are 0, 1. To further demonstrate the effectiveness of our proposed technique, we apply it to Time-Invariant SC-LDPC-CCs with girths 6 and 8 and column weights up to 5.

DOI
10.1109/lcomm.2019.2962671

Related papers

Edge Coloring Technique to Remove Small Elementary Trapping Sets from Tanner Graph of QC-LDPC Codes with Column Weight 4

Mohammad‐Reza Sadeghi, Farzane Amirzade

One of the phenomena that causes high decoding failure rates is trapping sets. Characterization of $(a,b)$ elementary trapping sets (ETSs), their graphical properties and the lower bounds on their size in variable regular LDPC codes with column weights 3, 4, 5 and 6, where $a$ is the size of the ETS and $b$ is the number of degree-one check nodes, have been an interesting subject among researchers. Although progressive-edge-growth method (PEG) to construct LDPC codes free of an specific ETS has been proposed in the literature, it is mostly applied to LDPC codes with column weight 3. In this paper, we focus on constructing QC-LDPC codes with column weight 4 whose Tanner graphs are free of small ETSs. Using coloring the edges of the variable node (VN) graph corresponding to an ETS, we provide the sufficient conditions to obtain QC-LDPC codes with column weight 4, girth 6 and free of $(5,b)$ ETSs, where $b\leq4$, and $(6,b)$ ETs, where $b\leq2$. Moreover, for $(4,n)$-regular QC-LDPC codes with girth 8, we present a method to remove $(7,4)$ ETSs from Tanner graphs.

arXiv:1808.05258•Aug 15, 2018•3 citations

QC-LDPC Codes With Large Column Weight and Free of Small Size ETSs

Farzane Amirzade, Mohammad‐Reza Sadeghi, Daniel Panario

An approach to improve the performance of QC-LDPC codes is the removal of harmful trapping sets by increasing the girth. However, constructing these LDPC codes with large column weights and girth more than 8 is not easy. We are concerned with protograph-based LDPC codes with large column weights and free of small size trapping sets. We use the edge-coloring technique and some concepts from graph theory such as rainbow cycles to show that for large column weights the removal of all 8-cycles but the ones we call$\textit {rainbow 8-cycle}$causes the elimination of several small size trapping sets. We provide a detailed theoretical analysis of these harmful trapping sets. Then, we apply them to array-based LDPC codes to significantly simplify and optimize the necessary and sufficient conditions to eliminate those 8-cycles from the Tanner graph. The given exponent matrices and simulation results show the impact of this simplification and the removal of the above mentioned 8-cycles.

IEEE Communications Letters•Dec 27, 2021•11 citations

Connections Between Low-Weight Codewords and Cycles in Spatially Coupled LDPC Convolutional Codes

Massimo Battaglioni, Marco Baldi, Giovanni Cancellieri

In this paper, time-invariant spatially coupled low-density parity-check convolutional codes (SC-LDPC-CCs) are considered, and the connections existing between their low-weight codewords and cycles in their Tanner graphs are studied. Using the polynomial representation of these codes, we show that parity-check matrices having columns with weight ≥2 can be analyzed considering a certain number of parity-check sub-matrices having regular columns with weight 2. These sub-matrices are associated to cycles in the code Tanner graph and define as many codes we denote as component codes. Based on this observation, we find that codewords of the main code can be expressed as combinations of codewords of the component codes. The design of codes free of codewords up to a certain weight is also addressed. We show that low-weight codewords in the main code can be avoided by removing some types of cycles in its Tanner graph. Our design approach is applied to some well-known ensembles of SC-LDPC-CCs to prove its effectiveness.

IEEE Transactions on Communications•Mar 29, 2018•12 citations

Optimal Search for Girth-8 Quasi Cyclic and Spatially Coupled Multiple-Edge LDPC Codes

Mohammad‐Reza Sadeghi

Two essential categories of LDPC codes that are more preferable to other types are quasi-cyclic LDPC (QC-LDPC) codes and spatially coupled LDPC convolutional codes (SC-LDPC-CCs) because of their excellent performance curves in waterfall and error floor regions. An efficient approach to construct these codes is protograph-based method that is categorized into two classes: single-edge (SE) and multiple-edge (ME) protographs. We, for the first time, provide a necessary and sufficient condition for exponent matrices of these codes with girth-8 and based on the ME-protographs. As a result, a lower bound on the lifting degree of girth-8 ME-QC-LDPC codes and a lower bound on the syndrome former memory order of girth-8 ME-SC-LDPC-CCs are obtained, which are tighter than the existing bounds in the literature.

IEEE Communications Letters•Jun 25, 2019•20 citations

Avoiding trapping sets in SC-LDPC codes under windowed decoding

Allison Beemer, Christine A. Kelley

Spatially coupled low-density parity-check (SC-LDPC) codes are sparse graph codes that have recently become of interest due to their capacity-approaching performance on memoryless binary input channels. Moreover, protograph SC-LDPC codes have been shown to be asymptotically good under certain conditions. SC-LDPC codes are amenable to a windowed decoder that allows decoding of blocks of bits to be done serially, making them good candidates for applications such as streaming. Depending on how they are constructed, however, the codes may still be prone to error floors. One key element in protograph SC-LDPC code design is the edge-spreading method used to couple copies of the base protograph in the construction of the SC-protograph. In this paper, we present an edge-spreading algorithm that is designed to remove trapping sets from the resulting SC-protograph that are harmful with respect to the windowed decoder, and we examine how to determine which trapping sets should be removed in the construction.

International Symposium on Information Theory and its Applications•Oct 1, 2016•12 citations

On Characterization of Elementary Trapping Sets of Variable-Regular LDPC Codes

Karimi, Mehdi, Amir H. Banihashemi

In this paper, we study the graphical structure of elementary trapping sets (ETS) of variable-regular low-density parity-check (LDPC) codes. ETSs are known to be the main cause of error floor in LDPC coding schemes. For the set of LDPC codes with a given variable node degree $d_l$ and girth $g$, we identify all the non-isomorphic structures of an arbitrary class of $(a,b)$ ETSs, where $a$ is the number of variable nodes and $b$ is the number of odd-degree check nodes in the induced subgraph of the ETS. Our study leads to a simple characterization of dominant classes of ETSs (those with relatively small values of $a$ and $b$) based on short cycles in the Tanner graph of the code. For such classes of ETSs, we prove that any set ${\cal S}$ in the class is a layered superset (LSS) of a short cycle, where the term "layered" is used to indicate that there is a nested sequence of ETSs that starts from the cycle and grows, one variable node at a time, to generate ${\cal S}$. This characterization corresponds to a simple search algorithm that starts from the short cycles of the graph and finds all the ETSs with LSS property in a guaranteed fashion. Specific results on the structure of ETSs are presented for $d_l = 3, 4, 5, 6$, $g = 6, 8$ and $a, b \leq 10$ in this paper. The results of this paper can be used for the error floor analysis and for the design of LDPC codes with low error floors.

arXiv:1308.1259•Aug 6, 2013•0 citations
In this letter, for the first time, an edge-coloring technique is proposed to characterize a certain elementary trapping set (ETS) and to obtain sufficient conditions to avoid small ETSs from occurrence in the Tanner graph of SC-LDPC convolutional codes. This technique is applicable to all protograph-based LDPC codes with different girths whose protographs are single-edge, that is, the entries of their base matrices are 0, 1. To further demonstrate the effectiveness of our proposed technique, we apply it to Time-Invariant SC-LDPC-CCs with girths 6 and 8 and column weights up to 5.
One of the phenomena that causes high decoding failure rates is trapping sets. Characterization of (a,b)(a,b)(a,b) elementary trapping sets (ETSs), their graphical properties and the lower bounds on their size in variable regular LDPC codes with column weights 3, 4, 5 and 6, where aaa is the size of the ETS and bbb is the number of degree-one check nodes, have been an interesting subject among researchers. Although progressive-edge-growth method (PEG) to construct LDPC codes free of an specific ETS has been proposed in the literature, it is mostly applied to LDPC codes with column weight 3. In this paper, we focus on constructing QC-LDPC codes with column weight 4 whose Tanner graphs are free of small ETSs. Using coloring the edges of the variable node (VN) graph corresponding to an ETS, we provide the sufficient conditions to obtain QC-LDPC codes with column weight 4, girth 6 and free of (5,b)(5,b)(5,b) ETSs, where b≤4b\leq4b≤4, and (6,b)(6,b)(6,b) ETs, where b≤2b\leq2b≤2. Moreover, for (4,n)(4,n)(4,n)-regular QC-LDPC codes with girth 8, we present a method to remove (7,4)(7,4)(7,4) ETSs from Tanner graphs.
An approach to improve the performance of QC-LDPC codes is the removal of harmful trapping sets by increasing the girth. However, constructing these LDPC codes with large column weights and girth more than 8 is not easy. We are concerned with protograph-based LDPC codes with large column weights and free of small size trapping sets. We use the edge-coloring technique and some concepts from graph theory such as rainbow cycles to show that for large column weights the removal of all 8-cycles but the ones we callrainbow 8-cycle\textit {rainbow 8-cycle}rainbow 8-cyclecauses the elimination of several small size trapping sets. We provide a detailed theoretical analysis of these harmful trapping sets. Then, we apply them to array-based LDPC codes to significantly simplify and optimize the necessary and sufficient conditions to eliminate those 8-cycles from the Tanner graph. The given exponent matrices and simulation results show the impact of this simplification and the removal of the above mentioned 8-cycles.
In this paper, time-invariant spatially coupled low-density parity-check convolutional codes (SC-LDPC-CCs) are considered, and the connections existing between their low-weight codewords and cycles in their Tanner graphs are studied. Using the polynomial representation of these codes, we show that parity-check matrices having columns with weight ≥2 can be analyzed considering a certain number of parity-check sub-matrices having regular columns with weight 2. These sub-matrices are associated to cycles in the code Tanner graph and define as many codes we denote as component codes. Based on this observation, we find that codewords of the main code can be expressed as combinations of codewords of the component codes. The design of codes free of codewords up to a certain weight is also addressed. We show that low-weight codewords in the main code can be avoided by removing some types of cycles in its Tanner graph. Our design approach is applied to some well-known ensembles of SC-LDPC-CCs to prove its effectiveness.
Two essential categories of LDPC codes that are more preferable to other types are quasi-cyclic LDPC (QC-LDPC) codes and spatially coupled LDPC convolutional codes (SC-LDPC-CCs) because of their excellent performance curves in waterfall and error floor regions. An efficient approach to construct these codes is protograph-based method that is categorized into two classes: single-edge (SE) and multiple-edge (ME) protographs. We, for the first time, provide a necessary and sufficient condition for exponent matrices of these codes with girth-8 and based on the ME-protographs. As a result, a lower bound on the lifting degree of girth-8 ME-QC-LDPC codes and a lower bound on the syndrome former memory order of girth-8 ME-SC-LDPC-CCs are obtained, which are tighter than the existing bounds in the literature.
Spatially coupled low-density parity-check (SC-LDPC) codes are sparse graph codes that have recently become of interest due to their capacity-approaching performance on memoryless binary input channels. Moreover, protograph SC-LDPC codes have been shown to be asymptotically good under certain conditions. SC-LDPC codes are amenable to a windowed decoder that allows decoding of blocks of bits to be done serially, making them good candidates for applications such as streaming. Depending on how they are constructed, however, the codes may still be prone to error floors. One key element in protograph SC-LDPC code design is the edge-spreading method used to couple copies of the base protograph in the construction of the SC-protograph. In this paper, we present an edge-spreading algorithm that is designed to remove trapping sets from the resulting SC-protograph that are harmful with respect to the windowed decoder, and we examine how to determine which trapping sets should be removed in the construction.
In this paper, we study the graphical structure of elementary trapping sets (ETS) of variable-regular low-density parity-check (LDPC) codes. ETSs are known to be the main cause of error floor in LDPC coding schemes. For the set of LDPC codes with a given variable node degree dld_ldl​ and girth ggg, we identify all the non-isomorphic structures of an arbitrary class of (a,b)(a,b)(a,b) ETSs, where aaa is the number of variable nodes and bbb is the number of odd-degree check nodes in the induced subgraph of the ETS. Our study leads to a simple characterization of dominant classes of ETSs (those with relatively small values of aaa and bbb) based on short cycles in the Tanner graph of the code. For such classes of ETSs, we prove that any set S{\cal S}S in the class is a layered superset (LSS) of a short cycle, where the term "layered" is used to indicate that there is a nested sequence of ETSs that starts from the cycle and grows, one variable node at a time, to generate S{\cal S}S. This characterization corresponds to a simple search algorithm that starts from the short cycles of the graph and finds all the ETSs with LSS property in a guaranteed fashion. Specific results on the structure of ETSs are presented for dl=3,4,5,6d_l = 3, 4, 5, 6dl​=3,4,5,6, g=6,8g = 6, 8g=6,8 and a,b≤10a, b \leq 10a,b≤10 in this paper. The results of this paper can be used for the error floor analysis and for the design of LDPC codes with low error floors.