Structured LDPC Codes: FPGA Implementation and Analysis

Explanation

We consider a class of structured low density parity check (LDPC) codes, called CPA-structured. For these codes we are developing FPGA implementations that offer a user-specified area-performance trade-off. Further, using these implementation, we investigate the relationship between code performance and parameters of the underlying Tanner graph.

CPA Structured LDPC Codes

Low density parity check (LDPC) codes have been shown to achieve information rates very close to the Shannon limit when iteratively decoded by the sum-product algorithm (SPA). For practical purposes, structured LDPC codes have been considered that allow for encoding and decoding with low complexity.  We consider a family of LDPC codes with the circulant permutation array (CPA) structure. i.e., the parity check matrix (H) is a Nc x Nb two dimensional array of pxp circulant permutation matrices.  The H-matrix can be equivalently represented by a Tanner graph, which is a bipartite graph with the check nodes on the top and check nodes on the bottom. Here is an example (sketched):

Parity check matrix (H matrix) of a
CPA structured LDPC code
Associated Tanner (factor) graph

With this structure, the position of 1’s in the parity check matrix can be stored in the decoder as the amount of shifts in each permutation matrix, which we call an S-matrix.  The existence of simple representation simplifies the analysis of the code [1], and makes it possible to construct CPA-structured codes in a pseudo-random manner [2][3].

Hardware Implementation

We have developed a generator for FPGA implementations of the entire class of CPA structured LDPC codes to enable the analysis of these codes in low BER regions.

Input:

Output:

Code Analysis

Using our hardware implementations, we hope to address the following questions.

Here are a few example experiments. g is the girth (shortest cycle), and d the diameter (longest distance between any 2 nodes) of the Tanner graph.

Four CPA(Nc=4,Nb=8, p=1023) structured codes with different girths are compared. The error floor region is not reached, the waterfall region is comparable. Four CPA(Nc=4,Nb=8, p=1023) codes with similar girths and different parameters. The performance in the waterfall region shows a strong relation with the diameter. Four CPA(Nc=3,Nb=9, p=500) codes with different girths (4, 6, 8, and 10) are compared. The plot suggests that the girth affects the performance in the error floor region.

References

  1. Sung-Chul Han
    A Flexible Decoder and Performance Evaluation of Array-Structured LDPC Codes
    PhD. thesis, Electrical and Computer Engineering, Carnegie Mellon University, 2007
  2. J. L. Fan
    Array codes as low-density parity-check codes
    Proc. Int. Symp. Turbo Codes and Related Topics, pp. 553–556, 2000
  3. J. M. F. Moura, J. Lu and U. Niesen
    Grouping-and-shifting designs for structured ldpc codes with large girth
    Proc. Int. Symp. on Information Theory (ISIT), p. 236, 2004
  4. J. Lu
    Designing structured low density parity check codes with large girth
    Ph.D. dissertation, Carnegie Mellon University, 2004.

More Information

For more information please send email to Sungchul Han: sungh (at) ece (dot) cmu (dot) edu