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.

The problem of determining the existence of a protograph-based QC-LDPC code with girth$g$and shortest blocklength for a prescribed protograph has been investigated in the literature. In some of these works, the goal was to obtain an algebraic expression for the blocklength in terms of the dimensions of the biadjacency matrix of the protograph and a lifting factor$N$. An algebraic expression has been found for$N$when$g> 4$is desired in the case of the fully connected (all-one) protograph but only lower bounds for the cases with larger girth. Computer search has been used in most cases to determine the exact value for$N$that gives the shortest blocklength for a particular protograph. In this paper, we present a promising connection between the lifting factor$N$(and therefore the blocklength of a QC-LDPC code) and the product of the pivots of the Hermite normal form of a matrix constructed from certain substructures in the protograph called tailless backtrackless closed (TBC) walks.

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.