Using Minors to Construct Generator Matrices for Quasi-Cyclic 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.

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 multi-edge 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.