LDPC codes based on circulant permutation matrices for fast encoding

Zixi Song, Lijun Zhang

Seho Myung, Kyeongcheol Yang, Jaeyoel Kim

In this correspondence we present a special class of quasi-cyclic low-density parity-check (QC-LDPC) codes, called block-type LDPC (B-LDPC) codes, which have an efficient encoding algorithm due to the simple structure of their parity-check matrices. Since the parity-check matrix of a QC-LDPC code consists of circulant permutation matrices or the zero matrix, the required memory for storing it can be significantly reduced, as compared with randomly constructed LDPC codes. We show that the girth of a QC-LDPC code is upper-bounded by a certain number which is determined by the positions of circulant permutation matrices. The B-LDPC codes are constructed as irregular QC-LDPC codes with parity-check matrices of an almost lower triangular form so that they have an efficient encoding algorithm, good noise threshold, and low error floor. Their encoding complexity is linearly scaled regardless of the size of circulant permutation matrices.

Michael E. O’Sullivan, Marcus Greferath, Roxana Smarandache

Hideaki Fujita

Low-density parity-check (LDPC) codes are one of the most promising next-generation error-correcting codes. For practical use, efficient methods for encoding of LDPC codes are needed and have to be studied. However, it seems that no general encoding methods suitable for hardware implementation have been proposed so far and for randomly constructed LDPC codes there have been no other methods than the simple one using generator matrices. In this paper we show that some classes of quasi-cyclic LDPC codes based on circulant permutation matrices, specifically LDPC codes based on array codes and a special class of Sridhara-Fuja-Tanner codes and Fossorier codes can be encoded by division circuits as cyclic codes, which are very easy to implement. We also show some properties of these codes.

Douglas J. Leith

Cycle distribution of LDPC(Low-Density Parity-Check) codes affects the codes decoding performance and encoding complexity,however it is commonly NP hard to analyse.We propose the rotation-distance for analysis of QC-LDPC(Quasi-Cyclic Low-Density Parity-Check) code based on circulant matrices.The circulant sub-matrices within the parity-check are treated as a matrix node to simplify theTanner graphs of the codes.Thus cycles of QC-LDPC codes can be found efficiently,and we demonstrate the usefulness of the new method by a simple proof of the known result that 12 is an upper limit of the girth of the QC-LDPC codes we considered.Moreover,the cycle analysis based on the new method also reveals relations between decoding performance and the cycle distribution of the code.

Xiao Yuan Wu, Yupeng Li, Yanyue Zhang