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):

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:

• array size (Nc, Nb) permutation matrix size (p)
• shift matrix (S-matrix)
• type of sum-product algorithm (original sum-product, min-sum, or modified min-sum)
• data precision (number of bits for integer and fractional parts)
• parallelization factor (v)
• number of checkpoints (For each checkpoint, the corresponding intermediate result can be stored)

Output:

• Synthesizable Verilog files for the decoder

You can download the file here (115 MB). the code is provided without any guarantees and free for non-commercial use.

Code Analysis

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

• How do the graph parameters (girth, diameter, and trapping set) affect the performance of CPA-structured codes (and more general QC-LDPC codes)?
• How can we refine the pseudo-random code construction method using the graph parameters?
• What are the post-processing methods to suppress early error floor caused by the SPA decoding?

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.

Copyrights to many of the above papers are held by the publishers. The attached PDF files are preprints. It is understood that all persons copying this information will adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder. Some links to papers above connect to IEEE Xplore with permission from IEEE, and viewers must follow all of IEEE's copyright policies.

More Information

For more information please send email to help (at) spiral dot net