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

Canadian Workshop on Information Theory (CWIT)

Protograph-based LDPC codes with chordless short cycles and large minimum distance

Farzane Amirzade, Mohammad‐Reza Sadeghi, Daniel Panario

Published Jun 5, 2022• 1 citation
Publisher

Abstract

Controlling small size trapping sets and short cycles can result in LDPC codes with large minimum distance$d_{\min}$. We prove that short cycles with a chord are the root of several trapping sets and eliminating these cycles increases$d_{\min}$. We show that the lower bounds on$d_{\min}$of an LDPC code with chordless short cycles, girth 6 and column weights$\gamma$is$2\gamma$. This is a significant improvement compared to the existing bounds$\gamma+1$• Several exponent matrices of protograph-based LDPC codes with chordless short cycles are proposed for any type of pro-tographs, single-edge and multi-edge. These numerical results as well as simulations show that the removal of short cycles with a chord improves previous results in the literature.

DOI
10.1109/cwit55308.2022.9817675

Related papers

Construction of Protograph-Based LDPC Codes With Chordless Short Cycles

Farzane Amirzade, Mohammad‐Reza Sadeghi, Daniel Panario

There is a concept in graph theory known as a chord which has not been considered before in relation to trapping sets of Tanner graphs. A chord of a cycle is an edge outside the cycle which connects two vertices of that cycle. It is proved that short cycles with a chord are the root of several trapping sets and eliminating them increases the minimum distance$d_{\min }$of a code. We provide new analytic lower bounds on$d_{\min }$of LDPC codes with girths 6 and 8 and column weight$\gamma $in which the short cycles are all chordless. We prove, analytically, that$d_{\min }\geq 2\gamma $for girth 6 and$d_{\min }\geq \frac {3(\gamma -1)^{2}}{\gamma \ln \gamma -\gamma +1}$for girth 8. Comparing these bounds with the existing bound$\gamma +1$for girth-6 LDPC codes shows the positive and significant influence of eliminating these cycles. A method to construct protograph-based LDPC codes with different girths and free of short cycles with a chord is given which is applicable to any type of protographs, simple and multi-edge, regular and irregular. The conditions to remove small trapping sets from the Tanner graph of a multi-edge QC-LDPC code are given. Numerical results indicate that the application of our method to QC-LDPC codes improves existing results.

arXiv:2008.01322•IEEE Transactions on Information Theory•Aug 22, 2023•15 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

Short Protograph-Based LDPC Codes

D. Divsalar, Sam Dolinar, Christopher Jones

In this paper we design protograph-based LDPC codes with short block sizes. Mainly we consider rate 1/2 codes with input block sizes 64, 128, and 256 bits. To simplify the encoder and decoder implementations for high data rate transmission, the structure of the codes is based on protographs and circulants. These codes are designed for short block sizes based on maximizing the minimum distance and stopping set size subject to a constraint on the maximum variable node degree. In particular, we consider codes with variable node degrees between 3 and 5. Increasing the node degree leads to larger minimum distances, at the expense of smaller girth. Therefore, there is a trade-off between undetected error rate performance (improved by increasing minimum distance) and the degree of sub-optimality of the iterative decoders typically used (which are adversely affected by graph loops). Various LDPC codes are compared and simulation results are provided.

IEEE Military Communications Conference (MILCOM)•Oct 1, 2007•23 citations

Design of Multiple-Edge Protographs for QC LDPC Codes Avoiding Short Inevitable Cycles

Hosung Park, Seokbeom Hong, Jong-Seon No +1 more

There have been lots of efforts on the construction of quasi-cyclic (QC) low-density parity-check (LDPC) codes with large girth. However, most of them focus on protographs with single edges and little research has been done for the construction of QC LDPC codes lifted from protographs with multiple (i.e., parallel) edges. Compared to single-edge protographs, multiple-edge protographs have benefits such that QC LDPC codes lifted from them can potentially have larger minimum Hamming distance. In this paper, all subgraph patterns of multiple-edge protographs, which prevent QC LDPC codes from having large girth by inducing inevitable cycles, are fully investigated based on a graph-theoretic approach. By using combinatorial designs, a systematic construction method of multiple-edge protographs is proposed for regular QC LDPC codes with girth at least 12 and another method is proposed for regular QC LDPC codes with girth at least 14. Moreover, a construction algorithm of QC LDPC codes based on certain liftings of multiple-edge protographs is proposed and it is shown that the resulting QC LDPC codes have larger upper bounds on the minimum Hamming distance than those lifted from single-edge protographs. Simulation results are provided to compare the performance of the proposed QC LDPC codes with progressive edge-growth (PEG) LDPC codes and with PEG QC LDPC codes.

arXiv:1210.3906•IEEE Transactions on Information Theory•Jun 14, 2013•30 citations

Minimum Distance Optimization with Chord Edge Growth for High Girth Non-Binary LDPC Codes

Changcai Han, Hui Li, Weigang Chen

Short or moderate-length non-binary low-density parity-check (NB-LDPC) codes have the potential applications in future low latency and high-reliability communication thanks to the strong error correction capability and parallel decoding. Because of the existence of the error floor, the NB-LDPC codes usually cannot satisfy very low bit error rate (BER) requirements. In this paper, a low-complexity method is proposed for optimizing the minimum distance of the NB-LDPC code in a progressive chord edge growth manner. Specifically, each chord edge connecting two non-adjacent vertices is added to the Hamiltonian cycle one-by-one. For each newly added chord edge, the configuration of non-zero entries corresponding to the chord edge is determined according to the so-called full rank condition (FRC) of all cycles that are related to the chord edge in the obtained subgraph. With minor modifications to the designed method, it can be used to construct the NB-LDPC codes with an efficient encoding structure. The analysis results show that the method for designing NB-LDPC codes while using progressive chord edge growth has lower complexity than traditional methods. The simulation results show that the proposed method can effectively improve the performance of the NB-LDPC code in the high signal-to-noise ratio (SNR) region. While using the proposed scheme, an NB-LDPC code with a quite low BER can be constructed with extremely low complexity.

Electronics•Dec 17, 2020•2 citations

Trade-Based LDPC Codes

Farzane Amirzade, Daniel Panario, Mohammad‐Reza Sadeghi

LDPC codes based on multi-edge protographs potentially have larger minimum distances compared to their counterparts, single-edge protographs. However, considering different features of their Tanner graph, such as short cycles, girth and other graphical structures, is harder than for Tanner graphs from single-edge protographs. Here, we provide a novel approach to construct the parity-check matrix of an LDPC code which is based on trades obtained from block designs. We employ our method to construct multi-edge quasi-cyclic (QC) LDPC codes.We use those trade-based matrices to define base matrices of multi-edge protographs. The construction of exponent matrices corresponding to these base matrices has less complexity than the ones proposed in the literature. We prove that these base matrices result in QC-LDPC codes with smaller lower bounds on the lifting degree than existing ones.

arXiv:2107.07466•IEEE International Symposium on Information Theory (ISIT)•Jun 26, 2022•4 citations
Controlling small size trapping sets and short cycles can result in LDPC codes with large minimum distancedmin⁡d_{\min}dmin​. We prove that short cycles with a chord are the root of several trapping sets and eliminating these cycles increasesdmin⁡d_{\min}dmin​. We show that the lower bounds ondmin⁡d_{\min}dmin​of an LDPC code with chordless short cycles, girth 6 and column weightsγ\gammaγis2γ2\gamma2γ. This is a significant improvement compared to the existing boundsγ+1\gamma+1γ+1• Several exponent matrices of protograph-based LDPC codes with chordless short cycles are proposed for any type of pro-tographs, single-edge and multi-edge. These numerical results as well as simulations show that the removal of short cycles with a chord improves previous results in the literature.
There is a concept in graph theory known as a chord which has not been considered before in relation to trapping sets of Tanner graphs. A chord of a cycle is an edge outside the cycle which connects two vertices of that cycle. It is proved that short cycles with a chord are the root of several trapping sets and eliminating them increases the minimum distancedmin⁡d_{\min }dmin​of a code. We provide new analytic lower bounds ondmin⁡d_{\min }dmin​of LDPC codes with girths 6 and 8 and column weight$\gamma inwhichtheshortcyclesareallchordless.Weprove,analytically,thatin which the short cycles are all chordless. We prove, analytically, thatinwhichtheshortcyclesareallchordless.Weprove,analytically,thatd_{\min }\geq 2\gamma forgirth6andfor girth 6 andforgirth6andd_{\min }\geq \frac {3(\gamma -1)^{2}}{\gamma \ln \gamma -\gamma +1}forgirth8.Comparingtheseboundswiththeexistingboundfor girth 8. Comparing these bounds with the existing boundforgirth8.Comparingtheseboundswiththeexistingbound\gamma +1$for girth-6 LDPC codes shows the positive and significant influence of eliminating these cycles. A method to construct protograph-based LDPC codes with different girths and free of short cycles with a chord is given which is applicable to any type of protographs, simple and multi-edge, regular and irregular. The conditions to remove small trapping sets from the Tanner graph of a multi-edge QC-LDPC code are given. Numerical results indicate that the application of our method to QC-LDPC codes improves existing results.
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 we design protograph-based LDPC codes with short block sizes. Mainly we consider rate 1/2 codes with input block sizes 64, 128, and 256 bits. To simplify the encoder and decoder implementations for high data rate transmission, the structure of the codes is based on protographs and circulants. These codes are designed for short block sizes based on maximizing the minimum distance and stopping set size subject to a constraint on the maximum variable node degree. In particular, we consider codes with variable node degrees between 3 and 5. Increasing the node degree leads to larger minimum distances, at the expense of smaller girth. Therefore, there is a trade-off between undetected error rate performance (improved by increasing minimum distance) and the degree of sub-optimality of the iterative decoders typically used (which are adversely affected by graph loops). Various LDPC codes are compared and simulation results are provided.
There have been lots of efforts on the construction of quasi-cyclic (QC) low-density parity-check (LDPC) codes with large girth. However, most of them focus on protographs with single edges and little research has been done for the construction of QC LDPC codes lifted from protographs with multiple (i.e., parallel) edges. Compared to single-edge protographs, multiple-edge protographs have benefits such that QC LDPC codes lifted from them can potentially have larger minimum Hamming distance. In this paper, all subgraph patterns of multiple-edge protographs, which prevent QC LDPC codes from having large girth by inducing inevitable cycles, are fully investigated based on a graph-theoretic approach. By using combinatorial designs, a systematic construction method of multiple-edge protographs is proposed for regular QC LDPC codes with girth at least 12 and another method is proposed for regular QC LDPC codes with girth at least 14. Moreover, a construction algorithm of QC LDPC codes based on certain liftings of multiple-edge protographs is proposed and it is shown that the resulting QC LDPC codes have larger upper bounds on the minimum Hamming distance than those lifted from single-edge protographs. Simulation results are provided to compare the performance of the proposed QC LDPC codes with progressive edge-growth (PEG) LDPC codes and with PEG QC LDPC codes.
Short or moderate-length non-binary low-density parity-check (NB-LDPC) codes have the potential applications in future low latency and high-reliability communication thanks to the strong error correction capability and parallel decoding. Because of the existence of the error floor, the NB-LDPC codes usually cannot satisfy very low bit error rate (BER) requirements. In this paper, a low-complexity method is proposed for optimizing the minimum distance of the NB-LDPC code in a progressive chord edge growth manner. Specifically, each chord edge connecting two non-adjacent vertices is added to the Hamiltonian cycle one-by-one. For each newly added chord edge, the configuration of non-zero entries corresponding to the chord edge is determined according to the so-called full rank condition (FRC) of all cycles that are related to the chord edge in the obtained subgraph. With minor modifications to the designed method, it can be used to construct the NB-LDPC codes with an efficient encoding structure. The analysis results show that the method for designing NB-LDPC codes while using progressive chord edge growth has lower complexity than traditional methods. The simulation results show that the proposed method can effectively improve the performance of the NB-LDPC code in the high signal-to-noise ratio (SNR) region. While using the proposed scheme, an NB-LDPC code with a quite low BER can be constructed with extremely low complexity.
LDPC codes based on multi-edge protographs potentially have larger minimum distances compared to their counterparts, single-edge protographs. However, considering different features of their Tanner graph, such as short cycles, girth and other graphical structures, is harder than for Tanner graphs from single-edge protographs. Here, we provide a novel approach to construct the parity-check matrix of an LDPC code which is based on trades obtained from block designs. We employ our method to construct multi-edge quasi-cyclic (QC) LDPC codes.We use those trade-based matrices to define base matrices of multi-edge protographs. The construction of exponent matrices corresponding to these base matrices has less complexity than the ones proposed in the literature. We prove that these base matrices result in QC-LDPC codes with smaller lower bounds on the lifting degree than existing ones.