Generalized low-density parity-check (GLDPC) codes, where single parity-check constraints on the code bits are replaced with generalized constraints (an arbitrary linear code), are a promising class of codes for low-latency communication. The block error rate performance of the GLDPC codes, combined with a complementary outer code, has been shown to outperform a variety of state-of-the-art code and decoder designs with suitable lengths and rates for the 5G ultra-reliable low-latency communication (URLLC) regime. A major drawback of these codes is that it is not known how to construct appropriate polynomial matrices to encode them efficiently. In this paper, we analyze practical constructions of quasi-cyclic GLDPC (QC-GLDPC) codes and show how to construct polynomial generator matrices in various forms using minors of the polynomial matrix. The approach can be applied to fully generalized matrices or partially generalized (with mixed constraint node types) to find better performance/rate trade-offs. The resulting encoding matrices are presented in useful forms that facilitate efficient implementation. The rich substructure displayed also provides us with new methods of determining low weight codewords, providing lower and upper bounds on the minimum distance and often giving those of weight equal to the minimum distance. Based on the minors of the polynomial parity-check matrix, we also give a formula for the rank of any parity-check matrix representing a QC-LDPC or QC-GLDPC code, and hence, the dimension of the code. Finally, we show that by applying double graph-liftings, the code parameters can be improved without affecting the ability to obtain a polynomial generator matrix.

Generalized low-density parity-check (GLDPC) codes, where single parity-check constraints on the code bits are replaced with generalized constraints (an arbitrary linear code), are a promising class of codes for low-latency communication. The block error rate performance of the GLDPC codes, combined with a complementary outer code, has been shown to outperform a variety of state-of-the-art code and decoder designs with suitable lengths and rates for the 5G ultra-reliable low-latency communication (URLLC) regime. A major drawback of these codes is that it is not known how to construct appropriate polynomial matrices to encode them efficiently. In this paper, we analyze practical constructions of quasi-cyclic GLDPC (QC-GLDPC) codes and show how to construct polynomial generator matrices in various forms using minors of the polynomial matrix. We consider mixed QC-GLDPC constructions, where favorable tradeoffs can be found in code rate vs. error correcting performance by only generalizing a proportion of the constraint nodes, and show that our approach extends naturally to these constructions. Finally, we show that by applying double graph-liftings, the code parameters can be improved without affecting the ability to obtain a polynomial generator matrix.

In this paper, we present an efficient strategy to enumerate the number of k-cycles, g ≤ kc, nv)-regular and irregular QC-LDPC codes. In this approach, we note that the mth power of the polynomial adjacency matrix can be used to describe walks of length m in the protograph and can therefore be sufficiently described by the matrices ${B_m}(H) \triangleq {\left( {H{H^ \top }} \right)^{\left\lfloor {m/2} \right\rfloor }}{H^{(m\,\bmod \,2)}}$, where m ≥ 0. For example, in the case of QC-LDPC codes based on the 3 × nvfully-connected protograph, the complexity of determining the number of k-cycles, ${\mathcal{N}_k}$, for k = 4, 6 and 8, is $O\left( {n_v^2\log (N)} \right)$, $O\left( {n_v^2\log \left( {{n_v}} \right)\log (N)} \right)$ and $O\left( {n_v^4{{\log }^4}\left( {{n_v}} \right)\log (N)} \right)$, respectively. The complexity, depending logarithmically on the lifting factor N, gives our approach, to the best of our knowledge, a significant advantage over previous works on the cycle distribution of QC-LDPC codes.

This paper gives a simple method to construct generator matrices with polynomial entries (and hence offers an alternative encoding method to the one commonly used) for all quasi-cyclic low-density parity-check (QC-LDPC) codes, even for those that are rank deficient. The approach is based on constructing a set of codewords with the desired total rank by using minors of the parity-check matrix. We exemplify the method on several well-known and standard codes. Moreover, we explore the connections between the minors of the parity-check matrix and the known upper bound on minimum distance and provide a method to compute the rank of any parity-check matrix representing a QC-LDPC code, and hence the dimension of the code, by using the minors of the corresponding polynomial parity-check matrix.

This paper presents a unifying framework to construct low-density parity-check (LDPC) codes with associated Tanner graphs of desired girth. Towards this goal, we highlight the role that a certain square matrix that appears in the product of the parity-check matrix with its transpose has in the construction of codes with graphs of desired girth and further explore it in order to generate the set of necessary and sufficient conditions for a Tanner graph to have a given girth between 6 and 12. For each such girth, we present algorithms to construct codes of the desired girth and we show how to use them to compute the minimum necessary value of the lifting factor. For girth larger than 12, we show how to use multi-step graph lifting methods to deterministically modify codes in order to increase their girth. We also give a new perspective on LDPC protograph-based parity-check matrices by viewing them as rows of a parity-check matrix equal to the sum of certain permutation matrices and obtain an important connection between all protographs and those with variable nodes of degree 2. We also show that the results and methodology that we develop for the all-one protograph can be used and adapted to analyze the girth of the Tanner graph of any parity-check matrix and demonstrate how this can be done using a well-known irregular, multi-edge protograph specified by the NASA Consultative Committee for Space Data Systems (CCSDS). Throughout the paper, we exemplify our theoretical results with constructions of LDPC codes with Tanner graphs of any girth between 6 and 14 and give sufficient conditions for a multi-step lifted parity-check matrix to have girth between 14 and 22.

This paper revisits the connection between the girth of a protograph-based LDPC code given by a parity-check matrix and the properties of powers of the product between the matrix and its transpose in order to obtain the necessary and sufficient conditions for a code to have given girth between 6 and 12, and to show how these conditions can be incorporated into simple algorithms to construct codes of that girth. To this end, we highlight the role that certain submatrices that appear in these products have in the construction of codes of desired girth. In particular, we show that imposing girth conditions on a parity-check matrix is equivalent to imposing conditions on a square submatrix obtained from it and we show how this equivalence is particularly strong for a protograph based parity-check matrix of variable node degree 2, where the cycles in its Tanner graph correspond one-to-one to the cycles in the Tanner graph of a square submatrix obtained by adding the permutation matrices (or products of these) in the composition of the parity-check matrix. We end the paper with exemplary constructions of codes with various girths and computer simulations. Although, we mostly assume the case of fully connected protographs of variable node degree 2 and 3, the results can be used for any parity-check matrix/protograph-based Tanner graph.

Spatially coupled (SC) low-density parity-check (LDPC) codes can achieve capacity approaching performance with low message recovery latency when using sliding window (SW) decoding. An SC-LDPC code constructed from a protograph can be generated by first coupling a chain of block protographs and then lifting the coupled protograph using permutation matrices. In this paper, we introduce a systematic design to eliminate 4-cycles in a coupled protograph. Further using a quasi-cyclic (QC) lifting, we introduce a procedure for constructing QC-SC-LDPC codes of girth at least eight. This can be interpreted as a multi-stage graph lifting process that yields a greater flexibility in designing QC-SC-LDPC codes with a large girth than previous approaches. Simulation results show the design leads to improved decoding performance, particularly in the error floor, compared to random constructions. Finally, we determine the minimum coupling width required to eliminate 4-cycles in a coupled protograph.

The minimum pseudoweight is an important parameter related to the decoding performance of LDPC codes with iterative message-passing decoding. In this paper, we consider ensembles of periodically time-varying spatially coupled LDPC (SC-LDPC) codes and the pseudocodewords arising from their finite graph covers of a fixed degree. We show that for certain (J,K)-regular SC-LDPC code ensembles and a fixed cover degree, the typical minimum pseudoweight of the unterminated (and associated tail-biting/terminated) SC-LDPC code ensembles grows linearly with the constraint (block) length as the constraint (block) length tends to infinity. We prove that one can bound the the free pseudodistance growth rate over a BEC from below (respectively, above) using the associated tail-biting (terminated) SC-LDPC code ensemble and show empirically that these bounds coincide for a sufficiently large period, which gives the exact free pseudodistance growth rate for the SC-LDPC ensemble considered.

Spatially coupled (SC) low-density parity-check (LDPC) codes can achieve capacity approaching performance with low message recovery latency when using sliding window (SW) decoding. An SC-LDPC code constructed from a protograph can be generated by first coupling a chain of block protographs and then lifting the coupled protograph using permutation matrices. This paper introduces a systematic design of SC-LDPC codes to eliminate 4-cycles in the coupled photograph. Using a quasi-cyclic (QC) lifting, we obtain QC-SC-LDPC codes of girth at least eight. Coupling a chain of block protographs implies spreading edges from one protograph to the others. Our protograph-based design can be viewed as guiding the edge spreading and also the graph-lifting process. Simulation results show the design leads to improved decoding performance, particularly in the error floor, compared to random designs.

In [1], it was conjectured that the permanent of a P-lifting θ↑Pof a matrix θ of degree M is less than or equal to the Mth power of the permanent perm(θ), i.e., perm(θ↑P) ≤ perm(θ)Mand, consequently, that the degree-M Bethe permanent permM,B(θ) of a matrix θ is less than or equal to the permanent perm(θ) of θ, i.e., permM,B(θ) ≤ perm(θ). In this paper, we prove these related conjectures and show some properties of the permanent of block matrices that are lifts of a matrix. As a corollary, we obtain an alternative proof of the inequality permB(θ) ≤ perm(θ) on the Bethe permanent of the base matrix θ, which, in contrast to the one given in [2], uses only the combinatorial definition of the Bethe-permanent. The results have implications in coding theory. Since a P-lifting corresponds to an M-graph cover and thus to a protograph-based LDPC code, the results may help explain the performance of these codes.

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 with one-step circulant-based liftings. The expected performance improvement is verified by simulation results.

It was recently conjectured that a vector with components equal to the Bethe permanent of certain submatrices of a parity-check matrix is a pseudocodeword. In this paper, we analyze some important cases for which the conjecture is true and investigate the obtained families of pseudocodewords.

The interference in wireless networks is temporally correlated, since the node or user locations are correlated over time and the interfering transmitters are a subset of these nodes. For a wireless network where (potential) interferers form a Poisson point process and use ALOHA for channel access, we calculate the joint success and outage probabilities of n transmissions over a reference link. The results are based on the diversity polynomial, which captures the temporal interference correlation. The joint outage probability is used to determine the diversity gain (as the SIR goes to infinity), and it turns out that there is no diversity gain in simple retransmission schemes, even with independent Rayleigh fading over all links. We also determine the complete joint SIR distribution for two transmissions and the distribution of the local delay, which is the time until a repeated transmission over the reference link succeeds.

Quasi-cyclic (QC) low-density parity-check (LDPC) codes are of great interest to code designers because of their implementation advantages and algebraic properties that facilitate their analysis. In this paper, we present some new results on QC-LDPC codes that are constructed using a two-step lifting procedure based on a protograph, and, by implementing this method instead of the usual one-step procedure, we are able to show improved minimum distance and girth properties. We also present two design rules to construct QC-LDPC codes: one uses only circulant permutation matrices at the first (pre-lifting) stage and the other uses a selection of non-commuting permutation matrices. For both techniques, we obtain a demonstrable increase in the minimum distance compared to a one-step circulant-based lifting. The expected performance improvement is verified by simulation results.

We present a mathematical connection between channel coding and compressed sensing. In particular, we link, on the one hand, channel coding linear programming decoding (CC-LPD), which is a well-known relaxation of maximum-likelihood channel decoding for binary linear codes, and, on the other hand, compressed sensing linear programming decoding (CS-LPD), also known as basis pursuit, which is a widely used linear programming relaxation for the problem of finding the sparsest solution of an underdetermined system of linear equations. More specifically, we establish a tight connection between CS-LPD based on a zero-one measurement matrix over the reals and CC-LPD of the binary linear channel code that is obtained by viewing this measurement matrix as a binary parity-check matrix. This connection allows the translation of performance guarantees from one setup to the other. The main message of this paper is that parity-check matrices of “good” channel codes can be used as provably “good” measurement matrices under basis pursuit. In particular, we provide the first deterministic construction of compressed sensing measurement matrices with an order-optimal number of rows using high-girth low-density parity-check codes constructed by Gallager.

Quasi-cyclic (QC) low-density parity-check (LDPC) codes are an important instance of proto-graph-based LDPC codes. In this paper we present upper bounds on the minimum Hamming distance of QC LDPC codes and study how these upper bounds depend on graph structure parameters (like variable degrees, check node degrees, girth) of the Tanner graph and of the underlying proto-graph. Moreover, for several classes of proto-graphs we present explicit QC LDPC code constructions that achieve (or come close to) the respective minimum Hamming distance upper bounds. Because of the tight algebraic connection between QC codes and convolutional codes, we can state similar results for the free Hamming distance of convolutional codes. In fact, some QC code statements are established by first proving the corresponding convolutional code statements and then using a result by Tanner that says that the minimum Hamming distance of a QC code is upper bounded by the free Hamming distance of the convolutional code that is obtained by “unwrapping” the QC code.

In this paper the decoding capabilities of convolutional codes over the erasure channel are studied. Of special interest will be maximum distance profile (MDP) convolutional codes. These are codes which have a maximum possible column distance increase. It is shown how this strong minimum distance condition of MDP convolutional codes help us to solve error situations that maximum distance separable (MDS) block codes fail to solve. Towards this goal, two subclasses of MDP codes are defined: reverse-MDP convolutional codes and complete-MDP convolutional codes. Reverse-MDP codes have the capability to recover a maximum number of erasures using an algorithm which runs backward in time. Complete-MDP convolutional codes are both MDP and reverse-MDP codes. They are capable to recover the state of the decoder under the mildest condition. It is shown that complete-MDP convolutional codes perform in many cases better than comparable MDS block codes of the same rate over the erasure channel.

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.

Quasi-cyclic Low-Density Parity-Check (QC-LDPC) codes based on protographs are of great interest to code designers because of their implementation advantages and algebraic properties that make them easy to analyze. However, the protograph structure imposes undesirable fixed upper limits on important code parameters. In this paper, we show that the upper bound on the minimum Hamming distance of protograph-based QC codes can be improved by the careful application of a two-step lifting procedure applied to the protograph. The promised improvement is validated by constructing codes with minimum distance exceeding the upper bound for QC codes based on a particular protograph.

Low-density parity-check (LDPC) convolutional codes are capable of achieving excellent performance with low encoding and decoding complexity. In this paper, we discuss several graph-cover-based methods for deriving families of time-invariant and time-varying LDPC convolutional codes from LDPC block codes and show how earlier proposed LDPC convolutional code constructions can be presented within this framework. Some of the constructed convolutional codes significantly outperform the underlying LDPC block codes. We investigate some possible reasons for this “convolutional gain,” and we also discuss the-mostly moderate-decoder cost increase that is incurred by going from LDPC block to LDPC convolutional codes.

The performance of linear-programming decoding of a binary linear code described by a parity-check matrix depends on the set of pseudo-codewords associated to this matrix and in particular, on the set of minimal pseudo-codewords. This paper attempts to provide an algebraic characterization of the minimal pseudo-codewords. It also provides a connection between the fundamental cone of a Tanner graph and the fundamental cone of its Forney-style factor graph.

Families of asymptotically regular LDPC block code ensembles can be formed by terminating (J, K)-regular protograph-based LDPC convolutional codes. By varying the termination length, we obtain a large selection of LDPC block code ensembles with varying code rates, minimum distance that grows linearly with block length, and capacity approaching iterative decoding thresholds, despite the fact that the terminated ensembles are almost regular. In this paper, we investigate the properties of the quasi-cyclic (QC) members of such an ensemble. We show that an upper bound on the minimum Hamming distance of members of the QC sub-ensemble can be improved by careful choice of the component protographs used in the code construction. Further, we show that the upper bound on the minimum distance can be improved by using arrays of circulants in a graph cover of the protograph.

In this paper we analyze the bound on the additive white Gaussian noise channel (AWGNC) pseudo-weight of a (c, d)-regular linear block code based on the two largest values ¿1> ¿2of the eigenvalues of HTH: wpmin> (H) ¿ n = 2c-¿2/¿1-¿2. In particular, we analyze (c, d)-regular quasi-cyclic (QC) codes of length rL described by J × L block parity-check matrices with circulant block entries of size r × r. We proceed by showing how the problem of computing the eigenvalues of the rL × rL matrix HTH can be reduced to the problem of computing eigenvalues for r matrices of size L × L. We also give a necessary condition for the bound to be attained for a circulant matrix H and show a few classes of cyclic codes satisfying this criterion.

The linear-programming decoding performance of a binary linear code crucially depends on the structure of the fundamental cone of the parity-check matrix that describes the code. Towards a better understanding of fundamental cones and the vectors therein, we introduce the notion of absdet-pseudo-codewords and perm-pseudo-codewords: we give the definitions, we discuss some simple examples, and we list some of their properties.

This paper studies the decoding capabilities of maximum distance profile (MDP) convolutional codes over the erasure channel and compares them with the decoding capabilities of MDS block codes over the same channel. The erasure channel involving large alphabets is an important practical channel model when studying packet transmissions over a network, e.g, the Internet.

Message-passing iterative decoders for low-density parity-check (LDPC) block codes are known to be subject to decoding failures due to so-called pseudocodewords. These failures can cause the large signal-to-noise ratio (SNR) performance of message-passing iterative decoding to be worse than that predicted by the maximum-likelihood (ML) decoding union bound.

In this paper we study the iterative decoding behavior of time-invariant and time-varying LDPC convolutional codes derived by unwrapping QC LDPC block codes. In particular, for a time-varying LDPC convolutional code, we show that the minimum pseudo-weight of the convolutional code is at least as large as the minimum pseudo-weight of the underlying QC code. We also prove that the unwrapped convolutional codes have fewer short cycles than the QC codes. These results taken together lead to improved BER performance in the low-to-moderate SNR region, where the decoding behavior is influenced by the complete pseudo-codeword spectra and by the Tanner graph cycle histogram, with the time-varying convolutional codes outperforming both the underlying QC block codes and their time-invariant convolutional counterparts.

We consider coded data transmission over a binary-input output-symmetric memoryless channel using a binary linear code. In order to understand the performance of maximum-likelihood (ML) decoding, one studies the codewords, in particular the minimal codewords, and their Hamming weights. In the context of linear programming (LP) decoding, one's attention needs to be shifted to the pseudo-codewords, in particular, to the minimal pseudo-codewords and their pseudo-weights. In this paper, we investigate some families of codes that have good properties under LP decoding, namely certain families of low-density parity-check (LDPC) codes that are derived from projective and Euclidean planes: we study the structure of their minimal pseudo-codewords and give lower bounds on their pseudo-weight. Besides this main focus, we also present some results that hold for pseudo-codewords and minimal pseudo-codewords of any Tanner graph, and we highlight how the importance of minimal pseudo-codewords under LP decoding varies depending on which binary-input output-symmetric memoryless channel is used.

Iterative message-passing decoders for low-density parity-check (LDPC) block codes are known to be subject to decoding failures due to so-called pseudo-codewords. These failures can cause the large signal-to-noise ratio performance of message-passing decoding to be worse than that predicted by the maximum-likelihood decoding union bound. In this paper we study the pseudo-codeword problem for the class of LDPC convolutional codes decoded continuously using an iterative, sliding window, message-passing decoder. In particular, for an LDPC convolutional code derived by unwrapping a quasi-cyclic LDPC block code, we show that the free pseudo-weight of the convolutional code is at least as large as the minimum pseudo-weight of the underlying quasi-cyclic code. This result parallels the well-known relationship between the free Hamming distance of convolutional codes and the minimum Hamming distance of their quasi-cyclic counterparts. Finally, simulation results are included that show improved performance for unwrapped LDPC convolutional codes compared to their underlying quasi-cyclic codes

Maximum-distance separable (MDS) convolutional codes have the property that their free distance is maximal among all codes of the same rate and the same degree. In this paper, a class of MDS convolutional codes is introduced whose column distances reach the generalized Singleton bound at the earliest possible instant. Such codes are called strongly-MDS convolutional codes. They also have a maximum or near-maximum distance profile. The extended row distances of these codes will also be discussed briefly.

In order to understand the performance of a code under maximum-likelihood (ML) decoding, it is crucial to know the minimal codewords. In the context of linear programming (LP) decoding, it turns out to be necessary to know the minimal pseudo-codewords. This paper studies the minimal codewords and minimal pseudo-codewords of some families of codes derived from projective and Euclidean planes. Although our numerical results are only for codes of very modest length, they suggest that these code families exhibit an interesting property. Namely, all minimal pseudo-codewords that are not multiples of a minimal codeword have an AWGNC pseudo-weight that is strictly larger than the minimum Hamming weight of the code. This observation has positive consequences not only for LP decoding but also for iterative decoding

A new method is given to construct low-density parity check codes the graphs of which are of designed girth. We give examples to illustrate the new method, and also present performance diagrams that suggest that these codes are as good as random codes in low SNR, and preferable to random codes at higher SNR.

In the past, several authors have considered quasicyclic LDPC codes whose circulant matrices in the parity-check matrix are cyclically shifted identity matrices. By composing a parity-check matrix not only with such matrices but also with sums of two cyclically shifted identity matrices and with zero matrices, one can increase the minimum distance while keeping the same regularity. Specifically, whereas for (3, 4)-regular codes in the first class the best minimum distance is 24, the best minimum distance in the second class is 32. We give examples of codes that achieve these bounds.

Maximum-distance separable (MDS) convolutional codes are characterized through the property that the free distance attains the generalized singleton bound. The existence of MDS convolutional codes was established by two of the authors by using methods from algebraic geometry. This correspondence provides an elementary construction of MDS convolutional codes for each rate k/n and each degree /spl delta/. The construction is based on a well-known connection between quasi-cyclic codes and convolutional codes.