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•96 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

Quasi-cyclic expansion and encoding algorithms for protograph LDPC codes

Zhongliang Li, Guojiang Xia

Recently, a new class of Low-Density Parity-Check (LDPC) codes constructed from a template was introduced. This kind of codes were called protograph codes. The protograph serves as a blueprint for constructing LDPC codes of arbitrary size whose performance can be predicted by analyzing the protograph. Protograph LDPC codes perform very well and suit for high-speed encoding and decoding. However, there are few researches on expansion and encoding algorithms for them. In this paper, using isomorphism between matrix ring and polynomial ring, we propose efficient quasi-cyclic expansion and encoding algorithms for protograph LDPC codes. Simulation results show that the protograph LDPC codes which were constructed by the algorithm proposed in this paper, outperform the best known unstructured irregular LDPC codes with the same maximum node degrees.

Chinese Journal of Space Science•Jan 1, 2011•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.
Recently, a new class of Low-Density Parity-Check (LDPC) codes constructed from a template was introduced. This kind of codes were called protograph codes. The protograph serves as a blueprint for constructing LDPC codes of arbitrary size whose performance can be predicted by analyzing the protograph. Protograph LDPC codes perform very well and suit for high-speed encoding and decoding. However, there are few researches on expansion and encoding algorithms for them. In this paper, using isomorphism between matrix ring and polynomial ring, we propose efficient quasi-cyclic expansion and encoding algorithms for protograph LDPC codes. Simulation results show that the protograph LDPC codes which were constructed by the algorithm proposed in this paper, outperform the best known unstructured irregular LDPC codes with the same maximum node degrees.