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)

An unnoticed strong connection between algebraic-based and protograph-based LDPC codes, Part I: Binary case and interpretation

Juane Li, Keke Liu, Shu Lin, Khaled Abdel-Ghaffar, W.E. Ryan

Published Feb 1, 2015• 20 citations
Publisher

Abstract

This paper unveils a strong connection between two major constructions of LDPC codes, namely the algebraic-based and the protograph-based constructions. It is shown that, from a graph-theoretic point of view, an algebraic LDPC code whose parity-check matrix is an array of submatrices of the same size over a finite field is a protograph LDPC code. Conversely, from a matrix-theoretic point of view, since the parity-check matrix of a protograph code can be arranged as an array of submatrices of the same size over a finite field and its base graph (or base matrix) can be constructed algebraically, a protograph LDPC code is an algebraic LDPC code. These two major approaches have their advantages and disadvantages in code construction. Unification of these two approaches may lead to better designs and constructions of LDPC codes to achieve good overall performance in terms of error performance in waterfall region, error-floor location and rate of decoding convergence. This paper is the first part of a series of two parts, Part-I and Part-II. Part-I investigates only the binary LDPC codes constructed by the superposition and the protograph-based methods. Part-II explores nonbinary LDPC codes from both superposition and protograph points of view. Also included in Part II are specific superposition constructions of both binary and nonbinary quasi-cyclic LDPC codes.

DOI
10.1109/ita.2015.7308964

Related papers

A New Algebraic-Based Method for Constructing Protograph LDPC Codes

Xijin Mu, Huaan Li, Chao Chen +2 more

This paper focuses on the construction of protograph low-density parity-check (PTG-LDPC) codes. We first give a necessary condition for a PTG-LDPC code to avoid 4-cycles. Then, we propose a new method for constructing PTG-LDPC codes based on the decomposition of a base matrix and the algebraic construction of an exponent matrix. The proposed method owns a lower design complexity compared with the conventional graph-based methods. Numerical results show that the proposed codes perform well, and have no error floor down to a block error rate of 10-4.

International Symposium on Turbo Codes and Iterative Information Processing•Dec 1, 2018•1 citation

Conclusion and Remarks

Juane Li, Shu Lin, Khaled Abdel-Ghaffar +2 more

In this book, we unified several major types of LDPC code constructions using a single framework, namely, the SP-construction. Under this framework, the constructions of all these types of LDPC codes can be viewed as basically algebraic. In general, algebraically constructed LDPC codes have good overall performance in terms of both waterfall and error-floor performance, as well as a fast rate of decoding convergence. The unification of all these constructions may lead to better designs, and construction of high performing and more easily implementable codes for applications in next generations of communication and data storage systems. This book consists of seven parts. In the first part (Chapter 4), we gave an algebraic interpretation of the protograph-based (PTG-based) construction of LDPC codes and presented a simple and novel algebraic method for constructing PTG-LDPC codes. The proposed algebraic method is equivalent to the graphical copy-and-permute operation and uses a simple matrix decomposition-and-replacement process to construct PTG-LDPC codes. The algebraic method is based on decomposition of a small base matrix and is very flexible in code construction. The constructed codes perform well as supported by examples and simulation results. However, how to design decomposition base matrices so that the resultant PTG-LDPC codes can perform close to their decoding thresholds is still an unresolved problem which needs further investigation. In the second part of the book (Chapters 5 and 6), we re-interpreted the SP-construction of LDPC codes, one of the earliest methods for algebraic construction of LDPC codes, in a broader context, from both algebraic and graph-theoretic perspectives. We showed that the PTG-LDPC code construction is a special case of SP-construction. New constructions of RC-constrained base matrices and PW-RC-constrained replacement sets of matrices for the SP-construction of LDPC codes were presented. In Chapter 5, we showed that two major ensembles of SP-LDPC codes for a given rate can be formed. One ensemble is equivalent to the ensemble of PTG-LDPC codes. In forming this ensemble, the member matrices in the replacement set R for the SP-construction of LDPC codes are regular. Since this ensemble is equivalent to the ensemble of PTG-LDPC codes, the SP-LDPC codes in this ensemble have good asymptotic performance and structural properties. For the other ensemble, the member matrices in the replacement set R for the SP-construction of LDPC codes are not regular.

Cambridge University Press eBooks•Dec 1, 2016•0 citations

Non-Binary Protograph-Based LDPC Codes: Enumerators, Analysis, and Designs

Lara Dolecek, D. Divsalar, Yizeng Sun +1 more

This paper provides a comprehensive analysis of nonbinary low-density parity check (LDPC) codes built out of protographs. We consider both random and constrained edge-weight labeling, and refer to the former as the unconstrained nonbinary protograph-based LDPC codes (U-NBPB codes) and to the latter as the constrained nonbinary protograph-based LDPC codes (C-NBPB codes). Equipped with combinatorial definitions extended to the nonbinary domain, ensemble enumerators of codewords, trapping sets, stopping sets, and pseudocodewords are calculated. The exact enumerators are presented in the finite-length regime, and the corresponding growth rates are calculated in the asymptotic regime. An EXIT chart tool for computing the iterative decoding thresholds of protograph-based LDPC codes is presented, followed by several examples of finite-length U-NBPB and C-NBPB codes with high performance. Throughout this paper, we provide accompanying examples, which demonstrate the advantage of nonbinary protograph-based LDPC codes over their binary counterparts and over random constructions. The results presented in this paper advance the analytical toolbox of nonbinary graph-based codes.

IEEE Transactions on Information Theory•Apr 9, 2014•95 citations

Partially Quasi-Cyclic Protograph-Based LDPC Codes

Roxana Smarandache, David G. M. Mitchell, Danniel J. Costello

A significant amount of the analysis of protograph-based low-density parity-check (LDPC) codes has been devoted to the subclass of quasi-cyclic (QC) LDPC codes. Despite their implementation advantages and algebraic properties that make them easy to analyze, protograph-based QC-LDPC codes have undesirable fixed upper limits on important code parameters. This implies that picking a QC code from an asymptotically good or capacity approaching ensemble is suboptimal, since long QC codes will not perform close to the ensemble asymptotic limits. Indeed, these limits can only be achieved by codes that are not QC. In this paper we present an overview together with some new results on partially-QC protograph-based LDPC codes, i.e., LDPC codes whose parity-check matrix is partially composed of circulant submatrices. We perform both a minimum Hamming distance and girth analysis of these codes. Moreover, we present explicit partially-QC LDPC code constructions with parameters that exceed the restricted QC upper bounds.

International Conference on Communications•Jun 1, 2011•10 citations

A Revolving Iterative Algorithm for Decoding Algebraic Cyclic and Quasi-Cyclic LDPC Codes

Keke Liu, Shu Lin, Khaled Abdel-Ghaffar

Cyclic and quasi-cyclic algebraic LDPC codes constructed based on finite fields, finite geometries, and combinatorial designs can achieve excellent performance in terms of error rate, error floor and rate of decoding convergence with iterative decoding. However, the relatively high density of the parity-check matrix of an algebraic cyclic or quasi-cyclic LDPC code makes the hardware implementation complexity of the decoder quite large, which may be a critical issue in practical applications. This paper presents an effective reduced-complexity algorithm for decoding algebraic cyclic and quasi-cyclic LDPC codes based on the block cyclic structure and cyclic grouping of the rows of their parity-check matrices. The decoding of a code is carried out based on a single small submatrix of the parity-check matrix of the code in a revolving manner. The proposed decoding algorithm significantly reduces the hardware implementation complexity and the size of memory required to store information.

IEEE Transactions on Communications•Sep 26, 2013•21 citations

The design of structured LDPC codes with algorithmic graph construction

Wojciech Sułek

Low-Density Parity-Check (LDPC) codes are among the most effective modern error-correcting codes due to their excellent correction performance and highly parallel decoding scheme. Moreover, the nonbinary extension of such codes further increases performance in the short-block regime. In this paper, we review the key elements for the construction of implementation-oriented binary and nonbinary codes. These Quasi-Cyclic LDPC (QC-LDPC) codes additionally feature efficient encoder and decoder implementation frameworks. We then present a versatile algorithm for the construction of both binary and nonbinary QC-LDPC codes that have low encoding complexity and an optimized corresponding graph structure. Our algorithm uses a progressive edge growth algorithm, modified for QC-LDPC graph construction, and then performs an iterative global search for optimized cyclic shift values within the QC-LDPC circulants. Strong error correction performance is achieved by minimizing the number of short cycles, and cycles with low external connectivity, within the code graph. We validate this approach via error rate simulations of a transmission system model featuring an LDPC coder-decoder, digital modulation, and additive white Gaussian noise channels. The obtained numerical results validate the effectiveness of the proposed construction algorithm, with a number of constructed codes exhibiting either similar or superior performance to industry standard binary codes and selected nonbinary codes from the literature.

Bulletin of the Polish Academy of Sciences Technical Sciences•May 30, 2022•0 citations
This paper unveils a strong connection between two major constructions of LDPC codes, namely the algebraic-based and the protograph-based constructions. It is shown that, from a graph-theoretic point of view, an algebraic LDPC code whose parity-check matrix is an array of submatrices of the same size over a finite field is a protograph LDPC code. Conversely, from a matrix-theoretic point of view, since the parity-check matrix of a protograph code can be arranged as an array of submatrices of the same size over a finite field and its base graph (or base matrix) can be constructed algebraically, a protograph LDPC code is an algebraic LDPC code. These two major approaches have their advantages and disadvantages in code construction. Unification of these two approaches may lead to better designs and constructions of LDPC codes to achieve good overall performance in terms of error performance in waterfall region, error-floor location and rate of decoding convergence. This paper is the first part of a series of two parts, Part-I and Part-II. Part-I investigates only the binary LDPC codes constructed by the superposition and the protograph-based methods. Part-II explores nonbinary LDPC codes from both superposition and protograph points of view. Also included in Part II are specific superposition constructions of both binary and nonbinary quasi-cyclic LDPC codes.
This paper focuses on the construction of protograph low-density parity-check (PTG-LDPC) codes. We first give a necessary condition for a PTG-LDPC code to avoid 4-cycles. Then, we propose a new method for constructing PTG-LDPC codes based on the decomposition of a base matrix and the algebraic construction of an exponent matrix. The proposed method owns a lower design complexity compared with the conventional graph-based methods. Numerical results show that the proposed codes perform well, and have no error floor down to a block error rate of 10-4.
In this book, we unified several major types of LDPC code constructions using a single framework, namely, the SP-construction. Under this framework, the constructions of all these types of LDPC codes can be viewed as basically algebraic. In general, algebraically constructed LDPC codes have good overall performance in terms of both waterfall and error-floor performance, as well as a fast rate of decoding convergence. The unification of all these constructions may lead to better designs, and construction of high performing and more easily implementable codes for applications in next generations of communication and data storage systems. This book consists of seven parts. In the first part (Chapter 4), we gave an algebraic interpretation of the protograph-based (PTG-based) construction of LDPC codes and presented a simple and novel algebraic method for constructing PTG-LDPC codes. The proposed algebraic method is equivalent to the graphical copy-and-permute operation and uses a simple matrix decomposition-and-replacement process to construct PTG-LDPC codes. The algebraic method is based on decomposition of a small base matrix and is very flexible in code construction. The constructed codes perform well as supported by examples and simulation results. However, how to design decomposition base matrices so that the resultant PTG-LDPC codes can perform close to their decoding thresholds is still an unresolved problem which needs further investigation. In the second part of the book (Chapters 5 and 6), we re-interpreted the SP-construction of LDPC codes, one of the earliest methods for algebraic construction of LDPC codes, in a broader context, from both algebraic and graph-theoretic perspectives. We showed that the PTG-LDPC code construction is a special case of SP-construction. New constructions of RC-constrained base matrices and PW-RC-constrained replacement sets of matrices for the SP-construction of LDPC codes were presented. In Chapter 5, we showed that two major ensembles of SP-LDPC codes for a given rate can be formed. One ensemble is equivalent to the ensemble of PTG-LDPC codes. In forming this ensemble, the member matrices in the replacement set R for the SP-construction of LDPC codes are regular. Since this ensemble is equivalent to the ensemble of PTG-LDPC codes, the SP-LDPC codes in this ensemble have good asymptotic performance and structural properties. For the other ensemble, the member matrices in the replacement set R for the SP-construction of LDPC codes are not regular.
This paper provides a comprehensive analysis of nonbinary low-density parity check (LDPC) codes built out of protographs. We consider both random and constrained edge-weight labeling, and refer to the former as the unconstrained nonbinary protograph-based LDPC codes (U-NBPB codes) and to the latter as the constrained nonbinary protograph-based LDPC codes (C-NBPB codes). Equipped with combinatorial definitions extended to the nonbinary domain, ensemble enumerators of codewords, trapping sets, stopping sets, and pseudocodewords are calculated. The exact enumerators are presented in the finite-length regime, and the corresponding growth rates are calculated in the asymptotic regime. An EXIT chart tool for computing the iterative decoding thresholds of protograph-based LDPC codes is presented, followed by several examples of finite-length U-NBPB and C-NBPB codes with high performance. Throughout this paper, we provide accompanying examples, which demonstrate the advantage of nonbinary protograph-based LDPC codes over their binary counterparts and over random constructions. The results presented in this paper advance the analytical toolbox of nonbinary graph-based codes.
A significant amount of the analysis of protograph-based low-density parity-check (LDPC) codes has been devoted to the subclass of quasi-cyclic (QC) LDPC codes. Despite their implementation advantages and algebraic properties that make them easy to analyze, protograph-based QC-LDPC codes have undesirable fixed upper limits on important code parameters. This implies that picking a QC code from an asymptotically good or capacity approaching ensemble is suboptimal, since long QC codes will not perform close to the ensemble asymptotic limits. Indeed, these limits can only be achieved by codes that are not QC. In this paper we present an overview together with some new results on partially-QC protograph-based LDPC codes, i.e., LDPC codes whose parity-check matrix is partially composed of circulant submatrices. We perform both a minimum Hamming distance and girth analysis of these codes. Moreover, we present explicit partially-QC LDPC code constructions with parameters that exceed the restricted QC upper bounds.
Cyclic and quasi-cyclic algebraic LDPC codes constructed based on finite fields, finite geometries, and combinatorial designs can achieve excellent performance in terms of error rate, error floor and rate of decoding convergence with iterative decoding. However, the relatively high density of the parity-check matrix of an algebraic cyclic or quasi-cyclic LDPC code makes the hardware implementation complexity of the decoder quite large, which may be a critical issue in practical applications. This paper presents an effective reduced-complexity algorithm for decoding algebraic cyclic and quasi-cyclic LDPC codes based on the block cyclic structure and cyclic grouping of the rows of their parity-check matrices. The decoding of a code is carried out based on a single small submatrix of the parity-check matrix of the code in a revolving manner. The proposed decoding algorithm significantly reduces the hardware implementation complexity and the size of memory required to store information.
Low-Density Parity-Check (LDPC) codes are among the most effective modern error-correcting codes due to their excellent correction performance and highly parallel decoding scheme. Moreover, the nonbinary extension of such codes further increases performance in the short-block regime. In this paper, we review the key elements for the construction of implementation-oriented binary and nonbinary codes. These Quasi-Cyclic LDPC (QC-LDPC) codes additionally feature efficient encoder and decoder implementation frameworks. We then present a versatile algorithm for the construction of both binary and nonbinary QC-LDPC codes that have low encoding complexity and an optimized corresponding graph structure. Our algorithm uses a progressive edge growth algorithm, modified for QC-LDPC graph construction, and then performs an iterative global search for optimized cyclic shift values within the QC-LDPC circulants. Strong error correction performance is achieved by minimizing the number of short cycles, and cycles with low external connectivity, within the code graph. We validate this approach via error rate simulations of a transmission system model featuring an LDPC coder-decoder, digital modulation, and additive white Gaussian noise channels. The obtained numerical results validate the effectiveness of the proposed construction algorithm, with a number of constructed codes exhibiting either similar or superior performance to industry standard binary codes and selected nonbinary codes from the literature.