Low-density parity-check (LDPC) codes were originally introduced in his doctoral thesis by Gallager in 1961. Since the discovery of Turbo codes in 1993 by Berrou, Glavieux, and Thitimajshima, and the rediscovery of LDPC codes by Mackay and Neal in 1995, there has been renewed interest in Turbo codes and LDPC codes, because their error rate performance approaches asymptotically the Shannon limit. Much research is devoted to characterizing the performance of LDPC codes and designing codes that have good performance. Commonly, a graph, the Tanner graph, is associated with the code and an important parameter affecting the performance of the code is the girth of its Tanner graph. In our work, we consider the design of structured regular LDPC codes whose Tanner graphs have large girth. The regularity and structure of LDPC codes utilize memory more efficiently and simplify the implementation of LDPC coders. The Tanner graph is a special type of graph, a bipartite graph, where the nodes divide into two disjoint classes with edges only between nodes in the two different classes. The problem we have been considering is a generic problem in graph theory, namely, that of designing bipartite graphs with large girth. We actually have studied a more special class of this generic problem, in particular, the design of undirected regular bipartite graphs with large girth.

Large girth speeds the convergence of iterative decoding and improves the performance of LDPC codes, at least in the high SNR range, by slowing down the onsetting of the error floor. We have developed several types of constructions for LDPC codes with large girth: geometry based (GB) and turbo structured (TS) LDPC codes. Simulations show that in the high SNR regime these codes exhibit better BER performance than random codes. The regularity of the codes provides additional advantages like simplicity of hardware implementation and fast encoding.

Journal Papers (additional papers in Journal Publications)

• José M. F. Moura, Jin Lu, and Haotian Zhang, “Structured LDPC Codes with Large Girth,” IEEE Signal Processing Magazine, vol. 21:1, pp.42-55, January 2004. Included in Special Issue on Iterative Signal Processing for Communications.

Conference Papers (additional papers in Conference Publications)

• Jin Lu, José M. F. Moura and Urs Niesen, “Grouping and Shifting Based LDPC Codes,” IEEE ISIT’04, IEEE International Symposium on Information Theory, Chicago, IL, June 2004.
• Haotian Zhang and José M. F. Moura, “Geometry Based Designs of LDPC Codes,” ICC 2004, IEEE International Conference on Communications, Communication Theory Symposium Coding III Session, Paris, France, June 20-24, 2004.
• Jin Lu, José M. F. Moura, and Urs Niesen, “A Class of Structured LDPC Codes with Large Girth,” ICC 2004, IEEE International Conference on Communications, Communication Theory Symposium LDPC Codes Session, Paris, France, June 20-24, 2004.
• Haotian Zhang and José M. F. Moura, “A Graph-Based Construction for Large-girth LDPC Codes,” 9th Joint MMM-Intermag 2004, Anaheim, CA, January 5-9 2004.
• Haotian Zhang and José M. F. Moura, “Structured regular {LDPC} codes with large girth,” IEEE Globecom, San Francisco, CA, December 2003.
• Haotian Zhang and José M. F. Moura, “Large-Girth LDPC Codes Based on Graphical Models,” SPAWC’03, IEEE Signal Processing and Wireless Communications Workshop, Rome, Italy, June 15-18, 2003.
• Jin Lu and José M. F. Moura, “Turbo Design for LDPC Codes with Large Girth,” SPAWC’03, IEEE Signal Processing and Wireless Communications Workshop, Rome, Italy, June 15-18, 2003.
• Jin Lu and José M. F. Moura, “Turbo Like Decoding of LDPC Codes,” INTERMAG ‘03, IEEE International Conference on Magnetics, May 2003.

Lab Members

1. Jin Lu
2. Haotian Zhang
3. Urs Niesen