TR2013-011

Hierarchical and High-Girth QC LDPC Codes


    •  Wang, Y.; Draper, S.C.; Yedidia, J.S., "Hierarchical and High-Girth QC LDPC Codes", IEEE Transactions on Information Theory, DOI: 10.1109/TIT.2013.2253512, ISSN: 0018-9448, Vol. 59, No. 7, pp. 4553-4583, July 2013.
      BibTeX Download PDF
      • @article{Wang2013jun1,
      • author = {Wang, Y. and Draper, S.C. and Yedidia, J.S.},
      • title = {Hierarchical and High-Girth QC LDPC Codes},
      • journal = {IEEE Transactions on Information Theory},
      • year = 2013,
      • volume = 59,
      • number = 7,
      • pages = {4553--4583},
      • month = jun,
      • doi = {10.1109/TIT.2013.2253512},
      • issn = {0018-9448},
      • url = {http://www.merl.com/publications/TR2013-011}
      • }
  • Research Area:

    Communications


We present an approach to designing capacityapproaching high-girth low-density parity-check (LDPC) codes that are friendly to hardware implementation, and compatible with some desired input code structure defined using a protograph. The approach is based on a mapping of any class of codes defined using a protograph into a family of hierarchical quasicyclic (HQC) LDPC codes. Whereas the parity check matrices of standard quasi-cyclic (QC) LDPC codes are composed of circulant sub-matrices, those of HQC LDPC codes are composed of a hierarchy of circulant sub-matrices that are in turn constructed from circulant sub-matrices, and so on, through some number of levels. Next, we present a girth-maximizing algorithm that optimizes the degrees of freedom within the family of codes to yield a high-girth HQC LDPC code, subject to bounds imposed by the fact that that HQC codes are still quasi-cyclic. Finally, we discuss how certain characteristics of a code protograph will lead to inevitable short cycles, and show that these short cycles can be eliminated using a "squashing" procedure that results in a high-girth QC LDPC code, although not a hierarchical one. We illustrate our approach with three design examples of QC LDPC codes -- two girth-10 codes of rates 1/3 and 0.45 and one girth-8 code of rate 0.7 -- all of which are obtained from protographs of one-sided spatially-coupled codes.