I. INTRODUCTION

Quasi-cyclic LDPC (QC-LDPC) codes, are attractive for implementation purposes since they can be encoded with low complexity using simple feedback shift-registers [1] and their structure leads to efficiencies in decoder design [2]. Moreover, QC-LDPC codes can be shown to perform well compared to random LDPC codes for moderate block lengths [3], [4]. However, unlike typical members of an asymptotically good protograph-based LDPC code ensemble, the QC sub-ensemble does not have linear distance growth. Indeed, if the protograph base matrix consists of only ones and zeros, then the minimum Hamming distance is bounded above by (n c + 1)!, where n c is the number of check nodes in the protograph, regardless of the lifting factor N [5]. This result was extended to multiedge protographs in [6]. Significant effort has been made in the coding theory community to design QC-LDPC code matrices with minimum distance and girth approaching these bounds, see [3], [4], [7]- [10] and references therein.

As a result of the rich structure of QC-LDPC codes, their matrix representations have been studied in a number of works. These include methods to construct a generator in standard form (e.g., [1]), which allows high throughput systematic encoding but the resulting generator matrix is typically dense. The sparse parity-check matrix is often represented as an array of circulant permutations, which facilitate efficient implementation, and will typically have a number of linearly dependent rows. Although Gaussian elimination can be employed to compute the rank with a complexity of O(n 3 ), it is desirable to have an analytic way to compute the rank, particularly for classes of algebraic QC-LDPC codes. Methods to compute the rank of QC-LDPC codes have been investigated, including approaches involving Fourier transforms [11], [12] and the matrix polynomial representation [13]. However, these approaches are limited to certain code parameters.

In this paper, we will use some previous results by Smarandache and Vontobel [6] to show how to construct polynomial generator matrices in various forms, including in standard form. The matrices are interesting from both the perspective of allowing for an encoding alternative to the methods in [1] as well as from the resulting codewords that are constructed from the method. In particular, the rows of the generator matrices we construct are codewords with relatively small weight, in some cases, equal to the minimum distance of the code. We exemplify these methods on some known codes. Our approach employs the minors of the polynomial matrix which also allow for a most general formula to compute the rank of any paritycheck matrix representing a QC-LDPC code, and hence, the dimension of any QC-LDPC code.

II. DEFINITIONS, NOTATIONS AND BACKGROUND

We use the following notation. For any positive integer L, [L] denotes the set {1, 2, . . . , L}. For any matrix M , we let M I,J be the sub-matrix of M that contains only the rows of M whose index appears in the set I and only the columns of M whose index appears in the set J ; if I equals the set of all row indices of M , we will simply write M J . We use the shorthand M J \i for M J \{i} . If I and J have the same cardinality, we use ∆ I,J = det(H I,J ), and

As usual, an LDPC code C is described as the null space of a parity-check matrix H to which we associate a Tanner graph [14] in the usual way. The girth of the Tanner graph, denoted by girth(H), is the length of its shortest cycle.

A protograph [15], [16] is a small bipartite graph represented by an n c × n v parity-check or base biadjacency matrix B with non-negative integer entries b ij . The paritycheck matrix H of a protograph-based LDPC block code can be created by replacing each non-zero entry b ij by a sum of b ij non-overlapping N ×N permutation matrices and a zero entry by the N × N all-zero matrix. Graphically, this operation is equivalent to taking an N -fold graph cover, or "lifting", of the protograph. We denote the N ×N circulant permutation matrix where the entries of the N ×N identity matrix I are shifted to the left by r positions modulo N as I r . A quasi-cyclic (QC) LDPC code of length n = n v N is a protograph-based LDPC code, for which the N × N lifting permutation matrices are all circulant matrices I r . Thus a QC code has an n c N × n v N parity-check matrix H of the form

where the N × N sub-matrices H i,j are circulant; applying equal circular shifts to each length-N sub-blocks of a codeword results in a codeword. With the help of the well-known isomorphism between the ring of circulant matrices over the binary field F 2 and the ring F 2 [x]/(x N -1) of F 2 -polynomials modulo x N -1 (see, e.g., [17]), a QC LDPC code can also be described by an n c × n v polynomial parity-check matrix over F 2 [x]/(x N -1). In particular, with the n c N × n v N parity-check matrix H described above we associate the polynomial parity-check matrix

where h i,j (x) ∈ F 2 [x]/(x N -1). Moreover, with any vector c = (c 1,0 , . . . , c 1,N -1 , . . . , c nv,0 , . . . , c nv,N -1 ) in F nvN

2

, we associate the polynomial vector c(x) = c 1 (x), . . . , c nv (x)

We note the simple technique described in [6] to construct codewords of codes described by polynomial parity-check matrices, which extends a codeword construction technique by MacKay and Davey [5,Theorem 2].

Lemma 1. Let C be the QC code defined by the n c × n v polynomial parity-check matrix H(x) over F 2 [x]/(x N -1). Let S be an arbitrary size-(n c +1) subset of [n v ] and let c(x) = c 1 (x), c 2 (x), . . . , c nv (x) be a length-n v vector defined by

We also note the following bound from [6] based on the codewords created with Lemma 1:

where min * takes the minimum positive value of a set.

III. A GENERATOR MATRIX FOR A QC CODE GIVEN BY H

This section, and the two theorems within, give an alternative approach to the method in [13] to compute the rank of H by computing full minors of the polynomial matrix H(x). Moreover, it provides both a sparse generator matrix and a 1 The determinant of an m × m-polynomial

, where the summation is over all m! permutations of the set [m]. Then det T transposes the polynomials, i.e., the exponents are taken with the negative sign modulo N . systematic generator matrix for the associated code C. This method also yields the known upper bounds on the minimum distance of the code C, see [6].

Let H be the n c N × n v N parity-check matrix of a QC code C and let H(x) be its corresponding polynomial parity-check matrix over

If there exists a subset S of size n c of [n v ], and for simplicity and w.l.o.g. we assume that S = [n c ], such that

where

equivalent generator polynomial matrices for C:

with notation as above, and where the matrix I m×m is the identity matrix of size

Proof: The proof is a relatively straightforward consequence of Lemma 1 and is omitted for space constraints. Remark 3. In Theorem 2, we give two (new) equivalent representations for both H(x) and G(x), the first one both matrices are sparse, while the second, is a systematic representation, both of which could be of interest to design efficient encoding and decoding algorithms. Note that the first representation of G(x) contains the codewords from which the upper bound (1) can be deduced, see also [6], and hence provides a sparse representation that would be amenable to high throughput encoding following approaches such as [1]. The systematic version, as is typical, is not as sparse and, in most cases, the row codewords have weight larger than this upper bound. However, the systematic form may also be of interest, e.g., to avoid the need for encoder inverse operations.

In the following we give two examples and show how this method of creating sets of codewords based on the full size minors of a n c × (n c + 1) submatrix of H(x) can also display codewords of the weight equal to the minimum distance. The upper bound (1) on the minimum distance given by the minimum of the weights of these codewords is relevant because it is shown to be tight. Example 4. (AR4JA codes) Let H(x) be the polynomial parity-check matrix given by

The rows of the matrix G(x) below are linearly independent codewords for the code C given by H, and since

, the matrix G(x) has rank 2N = 8 and thus, forms a generator matrix for the code C:

Note that the vectors (∆ T 245 , ∆ T 145 , 0, ∆ T 125 , ∆ T 124 ), (∆ T 345 , 0, ∆ T 145 , ∆ T 135 , ∆ T 134 ), (0, ∆ T 345 , ∆ T 245 , ∆ T 235 , ∆ T 234 ), are also codewords, where ∆ 145 = det(H 145 ) = x + 1, ∆ 245 = det(H 245 ) = 0, and ∆ 345 = det(H 345 ) = x, but they are linear combinations of the ones displayed in the matrix G(x), so they are not needed for the generator matrix. Displaying them is useful, however, since the nonzero minimum of the weights of the five codewords gives an upper bound on the minimum distance of the code (see (1)), in this case, the codeword (∆ T 245 , ∆ T 145 , 0, ∆ T 125 , ∆ T 124 ) = (0, x + 1, 0, x + 1, 0) has weight 4, which is in fact the minimum distance of the code; this code has parameters [20,8,4].

Multiplying the two rows of G by (x 3 + x 2 + 1) -1 = x 2 + x + 1 gives a generator matrix in standard form,

is a polynomial parity-check matrix in systematic form.

We exemplify the method also on a 4N × 8N , N = 16, irregular matrix.

Example 5. Let H (128,64) , shown below, be the 4N × 8N , N = 16, protograph-based matrix of the [128, 64, 14] irregular, multi-edge protograph specified by the NASA Consultative Committee for Space Data Systems (CCSDS) [16], [18]:

Let S = {5, 6, 7, 8}. We use the notation ∆ abcd = det(H {a,b,c,d} ) and compute ∆ 5678 = x 14 +x 12 +x 3 , which is invertible in F 2 [x]/(x 16 +1), since x 16 +1 = (x+1) 16 has only (x + 1) as irreducible factor in F 2 [x]. We compute ∆ -1 5678 = (x 14 +x 12 +x 3 ) -1 = x 13 +x 12 +x 11 +x 10 +x 9 +x 8 +x 7 +x+1, so that we can compute the values δ abcd ∆ abcd (∆ S ) -1 that appear in the the systematic parity-check matrix H (x) and the systematic generator matrix G(x) given as

δ2568 =x 14 + x 13 + x 12 + x 10 + x 9 + x 6 + x 3 + 1, δ2567 =x 11 + x 5 + x 4 + 1, δ3678 = x 15 + x 11 + x 8 + 1, δ3578 =(x + 1)(x 14 + x 12 + x 10 + x 7 + x 6 + x 4 + 1), δ3568 =x 15 + x 12 + x 11 + x 9 + x 7 + x 5 + x 2 + x + 1, δ3567 =x 14 + x 11 + x 10 + x 9 + x 5 + x 2 + x + 1, δ4678 =x 15 + x 12 + x 11 + x 10 + x 8 + x 6 + x 4 + x 2 , δ4578 =x 14 + x 10 + x 8 + x 7 + x 6 + x 5 + x 4 + x 2 , δ4568 =x 15 + x 11 + x 10 + x 7 + x 5 + x 4 + x 3 + x 2 , δ4567 =x 15 + x 14 + x 12 + x 10 + x 5 + x + 1, where δ T abcd is the transpose of δ abcd , which changes the exponents to their negatives modulo N .

A sparser but "systematic-like" generator matrix is, however, the following,

with a corresponding "systematic-like" parity-check matrix

2022 IEEE International Symposium on Information Theory (ISIT) ∆2578 = (x + 1)(x 14 + x 12 + x 10 + x 4 ) + 1, ∆2568 = (x 2 + 1)(x 12 + x 11 + x 5 + x 2 + x) + x + 1, ∆2567 = x 12 + x 9 + x 8 + x 2 + x + 1, ∆3678 = x 13 + x 12 + x 9 + x 7 + x 6 + x 4 + x 3 + x 2 , ∆3578 = x 13 + x 11 + x 9 + x 8 + x 4 + x 2 , ∆3568 = x 14 + x 11 + x 9 + (x + 1)(x 4 + x 2 + 1), ∆3567 = x 15 + x 14 + x 12 + x 10 + x 9 + x 6 + x 4 + 1, ∆4678 = x 15 + x 10 + x 5 + x 2 , ∆4568 = x 15 + x 11 + x 10 + x 9 , ∆4578 = x 14 + x 13 + x 12 + x 11 + x 9 + x 7 ,

The rows of the matrix G (x) represent codewords of weight that equal the upper bound on the minimum distance from (1). The last row, for example, gives d min (C) ≤ 24.

If instead we take S = {1, 5, 6, 8}, the polynomial ∆ 1578 = x 15 + x 11 + x 10 + x 9 + x 8 + x 6 + x 3 + 1 is not invertible in F 2 [x]/(x 16 + 1), so we cannot obtain the identity matrix. B. Case of n c N × n v N rank deficient matrices H This section considers the case in which, for any subset S of size In this case, we can still construct the matrix G 1 of codewords similar to the one formed in Section III-A:

However, unlike the case in which ∆ S is invertible, this matrix does not generate the entire code C, but only a subcode of C because its rank is lower that the dimension of the code. In this case, we will need to add to this matrix a few rows of "obvious" codewords to increase the rank. We exemplify this on the famous [155, 64, 20] Tanner code below. All 3 × 3 minors and X 31 + 1 have common factor (x + 1), so H(x) does not have any irreducible 3 × 3 submatrix H S .

Let S = {1, 2, 3}, and ∆ 123 det(H 123 ) = x 28 + x 18 + x 16 + x 14 + x 9 + x 8 . The matrix

is a matrix of two codewords. It has rank 60, so it only generates a subcode of C (of the same minimum distance 20).

To increase its rank and, thus, obtain a full generator matrix, we need to add some linearly independent codewords to this matrix. One would hope that the entire matrix of codewords

has the correct rank, but this is not the case since three of the 5 codewords above are linear combinations of the remaining two, and the rank of the matrix above is still 60 over F 2 . Although these 3 codewords are not necessary to construct a generator matrix, displaying them is useful, nonetheless, since they give the known upper bound on the minimum distance (1), d min (C) ≤ 4 • 6 = 24, see [6]. However, the matrix

, where f = 1 + x + x 2 + • • • + x 30 , has the correct rank 64, and its rows are codewords for the code given by H. Therefore, it is a generator matrix for the [155, 64, 20] Tanner code. This generator matrix is sparse and in "systematic-like" form. We can make it more systematic in the following way. Since gcd(∆ 123 , f ) = 1, over the polynomial ring F 2 [x], there exist A(x), B(x) ∈ F 2 [x], A = (x 3 + 1)(x 25 + x 5 ) + (x + 1)(x 18 + x 15 + x 14 + x 9 + x) B = (x + 1)(x 25 + x 22 + x 16 + x 12 + x 10 + 1) + x 9 ,

Adding the first row of G multiplied by A with the fifth row of G, and adding the second row of G multiplied by A with the sixth row of G, we obtain The following theorem gives the formula for the rank over F 2 of a scalar matrix using the computation of the degree of the minors of the corresponding polynomial matrix. Theorem 7. Let H be a n c N × n v N matrix over F 2 and H(x) be the corresponding n c × n v polynomial matrix. For all i ∈ [n c ], we define the following in F 2 [x]:

, where gcd(0/0, x N + 1) gcd(0, x N + 1) = x N + 1. Then,

Proof: In F 2 [x], H(x) is equivalent (after elementary row and column operations that leave its rank invariant) to its Smith normal form diag( γ1 γ0 (x), γ2 γ1 (x), . . . ,

Taking the gcd of the entries with (x N +1), we obtain a matrix equivalent to H(x) in F 2 [x]/(x N +1), therefore, the rank over F 2 of the n c N × n v N matrix H is equal to the sum of the ranks of the circulant matrices associated to

x 30 + x 24 x 12 + x 14 xfoot_2 + x 13 x + x 9   be a 3 × 5 polynomial matrix in F 2 [x]. Depending on N , its Tanner graph can have girth 6. We will keep N variable, and compute the rank of the 3N × 5N matrix H obtained from H(x) in the ring F 2 [x]/(x N + 1). We obtain (the following include relevant Magma commands):

Therefore, the same matrix gives a code of larger dimension if N is even. For example, N = 44, gives H of rank 128, and the code of dimension 92, while N = 45 gives a slightly longer code that has the same dimension 92.

We end with a theorem that shows how to obtain an equivalent upper triangular form for H(x) and thus, to provide an alternative proof to Theorem 7. 3 The proof is based on simple computations of determinants. Theorem 9. Let H(x) = (h ij ) i,j by an n c × n v polynomial matrix. We assume, w.l.o.g, that gcd(

, where the determinants and the divisions are performed in F 2 [x] first, followed by the modular operation mod (x N +1).

Example 10. Let H(x) be the polynomial parity-check matrix of Example 6. We compute γ 1 = 1, Note that there could be N for which simpler equivalent triangular forms can be obtained. For values N for which

where δ I,J ∆ I,J mod x N +1, the denominator γ i-1 can be dropped in Theorem 9. For example, the matrix H 2 (x) below gives also the same [155, 64, 20] code as H(x), for N = 31:

x 8

x 16 0 x 10 + x 6 x 20 + x 8 x 12 + x 9 x 20 + x 18 0 0 δ IV. CONCLUDING REMARKS This paper shows how to obtain a generator matrix for an LDPC code using minors of the polynomial parity-check matrix. The resulting matrices can be presented in several forms that may facilitate efficient encoder implementation as well as minimum distance analysis. Moreover, the approach was shown to provide a formula for the dimension of any QC-LDPC code based on the minors of its polynomial paritycheck matrix.