Structured LDPC Codes: FPGA Implementation and Analysis
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 , and makes it possible to construct CPA-structured codes in a pseudo-random manner .
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.
- 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)
- Synthesizable Verilog files for the decoder
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.
- Sung-Chul Han
A Flexible Decoder and Performance Evaluation of Array-Structured LDPC Codes
PhD. thesis, Electrical and Computer Engineering, Carnegie Mellon University, 2007
- J. L. Fan
Array codes as low-density parity-check codes
Proc. Int. Symp. Turbo Codes and Related Topics, pp. 553556, 2000
- 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
- J. Lu
Designing structured low density parity check codes with large girth
Ph.D. dissertation, Carnegie Mellon University, 2004.
For more information please send email to Sungchul Han: sungh (at) ece (dot) cmu (dot) edu