Quasi-cyclic LDPC codes: Construction and rank analysis of their parity-check matrices

A construction of binary and non-binary quasi-cyclic (QC)-LDPC codes based on partitions of finite fields of characteristic 2 is proposed. The construction is carried out in the Fourier transform domain. The parity-check matrices of these QC-LDPC codes are arrays of circulant permutation matrices. The ranks of these arrays are analyzed and combinatorial expressions are derived. Example codes are given and simulations show that they perform well over the AWGN channel decoded with message-passing decoding algorithms.

I. Introduction

The ever-growing needs for cheaper, faster, and more reliable communication systems have forced many researchers to seek means to attain the ultimate limits on reliable communications. Low-density parity-check (LDPC) codes are currently the most promising coding technique to achieve the Shannon capacities for a wide range of channels. These codes were first discovered by Gallager in 1962 [1] and then rediscovered in the late 1990's [2], [3]. Ever since their rediscovery, a great deal of research effort has been expended in design, construction, structural and performance analysis, encoding, decoding, generalizations, and applications of LDPC codes. Numerous papers have been published on these subjects. Many LDPC codes have been chosen as the standard codes for various next generations of communication systems and they are appearing in recent data storage products. More applications are expected to come.