Reversible Low-Density Parity-Check Codes
David Haley, Alex J. Grant
Low-density parity-check (LDPC) codes may be decoded using a circuit implementation of the sum-product algorithm which maps the factor graph of the code. By reusing the decoder for encoding, both tasks can be performed using the same circuit, thus reducing area and verification requirements. Motivated by this, iterative encoding techniques based upon the graphical representation of the code are proposed. Code design constraints which ensure encoder convergence are presented, and then used to design iteratively encodable codes, while also preventing 4-cycle creation. We show how the Jacobi method for iterative matrix inversion can be applied to finite field matrices, viewed as message passing, and employed as the core of an iterative encoder. We present an algebraic construction of4-cycle free iteratively encodable codes using circulant matrices. Analysis of these codes identifies a weakness in their structure, due to a repetitive pattern in the factor graph. The graph supports pseudo-codewords of low pseudo-weight. In order to remove the repetitive pattern in the graph, we propose a recursive technique for generating iteratively encodable codes. The new codes offer flexibility in the choice of code length and rate, and performance that compares well to randomly generated, quasi-cyclic and extended Euclidean-geometry codes.
IEEE Transactions on Information Theory•Apr 22, 2009•9 citations