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 Access

Protograph Based Low-Density Parity-Check Codes Design With Mixed Integer Linear Programming

Wojciech Sułek

Published Dec 12, 2018• 10 citations
Publisher

Abstract

An approach to design protograph-based low-density parity-check (LDPC) codes utilizing mixed integer linear programming (MILP) optimization is presented in this paper. The protograph (base graph) cyclic lifting for a class of quasi-cyclic LDPC codes is considered. In general, the short cycles elimination is the primary optimization goal, possibly weighted by a metric of cycles connectivity. A notion of closed walks in the base graph is shown to be a convenient way for representing sources of cycles in the lifted graph. We express the condition for non-existence of a cycle in the lifted graph corresponding to a closed walk in the base graph in the form of a set of linear inequalities. Such inequalities, collected for all closed walks shorter than a desired limit corresponding to girth, form a set of linear constraints. Meanwhile, the longer closed walks can be reflected in a linear objective function of the optimization. The proposed combination of constraints and objective function forms an input to a MILP solver. As a result, a globally optimized code graph can be obtained. The method can be utilized for binary as well as nonbinary LDPC codes. The numerical results show that the constructed codes can outperform similar codes deigned with reference heuristic search methods.

DOI
10.1109/access.2018.2886527

Related papers

Design of Protograph-Based Quasi-Cyclic Spatially Coupled Ldpc Codes

Shuoshuo Wang, Zhanji Wu, Qihao Wu

In this paper, we deal with time-varing quasi-cyclic (QC) spatially-coupled (SC) low-density parity-check (LDPC) codes by lifting the coupled protographs. The construction method of girth-6 protographs for any code rate is proposed. We provide a theoretical lower bound on the syndrome former constraint length under condition of the protographs without 4-cycles in their Tanner graphs. Then we use periodic QC lifting method to search the QC-SC-LDPC matrices with larger girth based on the protographs. The minimum dimension size of QC-SC-LDPC codes is given to count the girth of QC-SC-LDPC codes with a semi- infinite binary-check matrix structure. The performance of such constructed codes with lower complexity and delay is superior to the LDPC block codes.

IEEE Wireless Communications and Networking Conference Workshops (WCNCW)•Apr 1, 2020•2 citations

On the girth of (3,L) quasi-cyclic LDPC codes based on complete protographs

Sudarsan V. S. Ranganathan, D. Divsalar, Richard D. Wesel

We consider the problem of constructing (3,L) quasi-cyclic low-density parity-check (LDPC) codes from complete protographs. A complete protograph is a small bipartite graph with two disjoint vertex sets such that every vertex in the variable-node set is connected to every vertex in the check-node set by a unique edge. This paper analyzes the required lifting factor for achieving girths of six or eight in the resulting quasi-cyclic codes with constraints on lifting. The required lifting factors provide lower bounds on the block-length of such codes.

arXiv:1504.04975•IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2015•16 citations

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

Hosung Park Seokbeom Hong

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 are focused on protographs with single edges and little research has been done for the construction of QC LDPC codes lifted from protographs with multiple 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 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 also other method is proposed for regular QC LDPC codes with girth at least 14. A construction algorithm of QC LDPC codes by lifting 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, the progressive edge-growth (PEG) LDPC codes, and the PEG QC LDPC codes.

•Jan 1, 2014•26 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

Quasi-Cyclic LDPC Codes based on Pre-Lifted Protographs

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

Quasi-cyclic low-density parity-check (QC-LDPC) codes based on protographs are of great interest to code designers because analysis and implementation are facilitated by the protograph structure and the use of circulant permutation matrices for protograph lifting. However, these restrictions impose undesirable fixed upper limits on important code parameters, such as minimum distance and girth. In this paper, we consider an approach to constructing QC-LDPC codes that uses a two-step lifting procedure based on a protograph, and, by following this method instead of the usual one-step procedure, we obtain improved minimum distance and girth properties. We also present two new design rules for constructing good QC-LDPC codes using this two-step lifting procedure, and in each case we obtain a significant increase in minimum distance and achieve a certain guaranteed girth compared to one-step circulant-based liftings. The expected performance improvement is verified by simulation results.

arXiv:1407.5364•Jul 21, 2014•1 citation

On the girth of quasi cyclic protograph LDPC codes

Mehdi Karimi, Amir H. Banihashemi

In this paper, we study the relationships between the girth of the Tanner graph of a quasi cyclic (QC) protograph low-density parity-check (LDPC) code, on one hand, and the lifting degree and the size and the structure of the base graph, on the other hand. As a result, for a given base graph and a given lifting degree, we derive an upper bound on the girth of the resulting lifted graphs (codes). The upper bounds derived here are generally tighter than the existing bounds. The results presented in this work can be used to select an appropriate lifting degree for a given base graph, in order to have a desired girth, or to provide some insight in designing good base graphs, or to properly select the base graph's edge permutations.

IEEE International Symposium on Information Theory (ISIT)•Jul 1, 2012•6 citations
An approach to design protograph-based low-density parity-check (LDPC) codes utilizing mixed integer linear programming (MILP) optimization is presented in this paper. The protograph (base graph) cyclic lifting for a class of quasi-cyclic LDPC codes is considered. In general, the short cycles elimination is the primary optimization goal, possibly weighted by a metric of cycles connectivity. A notion of closed walks in the base graph is shown to be a convenient way for representing sources of cycles in the lifted graph. We express the condition for non-existence of a cycle in the lifted graph corresponding to a closed walk in the base graph in the form of a set of linear inequalities. Such inequalities, collected for all closed walks shorter than a desired limit corresponding to girth, form a set of linear constraints. Meanwhile, the longer closed walks can be reflected in a linear objective function of the optimization. The proposed combination of constraints and objective function forms an input to a MILP solver. As a result, a globally optimized code graph can be obtained. The method can be utilized for binary as well as nonbinary LDPC codes. The numerical results show that the constructed codes can outperform similar codes deigned with reference heuristic search methods.
In this paper, we deal with time-varing quasi-cyclic (QC) spatially-coupled (SC) low-density parity-check (LDPC) codes by lifting the coupled protographs. The construction method of girth-6 protographs for any code rate is proposed. We provide a theoretical lower bound on the syndrome former constraint length under condition of the protographs without 4-cycles in their Tanner graphs. Then we use periodic QC lifting method to search the QC-SC-LDPC matrices with larger girth based on the protographs. The minimum dimension size of QC-SC-LDPC codes is given to count the girth of QC-SC-LDPC codes with a semi- infinite binary-check matrix structure. The performance of such constructed codes with lower complexity and delay is superior to the LDPC block codes.
We consider the problem of constructing (3,L) quasi-cyclic low-density parity-check (LDPC) codes from complete protographs. A complete protograph is a small bipartite graph with two disjoint vertex sets such that every vertex in the variable-node set is connected to every vertex in the check-node set by a unique edge. This paper analyzes the required lifting factor for achieving girths of six or eight in the resulting quasi-cyclic codes with constraints on lifting. The required lifting factors provide lower bounds on the block-length of such codes.
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 are focused on protographs with single edges and little research has been done for the construction of QC LDPC codes lifted from protographs with multiple 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 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 also other method is proposed for regular QC LDPC codes with girth at least 14. A construction algorithm of QC LDPC codes by lifting 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, the progressive edge-growth (PEG) LDPC codes, and the PEG QC LDPC codes.
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.
Quasi-cyclic low-density parity-check (QC-LDPC) codes based on protographs are of great interest to code designers because analysis and implementation are facilitated by the protograph structure and the use of circulant permutation matrices for protograph lifting. However, these restrictions impose undesirable fixed upper limits on important code parameters, such as minimum distance and girth. In this paper, we consider an approach to constructing QC-LDPC codes that uses a two-step lifting procedure based on a protograph, and, by following this method instead of the usual one-step procedure, we obtain improved minimum distance and girth properties. We also present two new design rules for constructing good QC-LDPC codes using this two-step lifting procedure, and in each case we obtain a significant increase in minimum distance and achieve a certain guaranteed girth compared to one-step circulant-based liftings. The expected performance improvement is verified by simulation results.
In this paper, we study the relationships between the girth of the Tanner graph of a quasi cyclic (QC) protograph low-density parity-check (LDPC) code, on one hand, and the lifting degree and the size and the structure of the base graph, on the other hand. As a result, for a given base graph and a given lifting degree, we derive an upper bound on the girth of the resulting lifted graphs (codes). The upper bounds derived here are generally tighter than the existing bounds. The results presented in this work can be used to select an appropriate lifting degree for a given base graph, in order to have a desired girth, or to provide some insight in designing good base graphs, or to properly select the base graph's edge permutations.