Technical Report PHD-2007-01

Title: Low-Density Parity-Check Codes: Constructions and Bounds
Authors: Vitaly Skachek
Supervisors: Ronny Roth
Abstract: Low-density parity-check (LDPC) codes were introduced in 1962, but were almost forgotten. In recent years, they have attracted a lot of attention due to the practical efficiency of "average" LDPC codes. However, the performance of explicitly constructed LDPC codes still suffers from performance disadvantages compared with "average" LDPC codes. The most promising approach for constructing specific LDPC codes is based on using expander graphs. Some of such codes (called expander codes) allow both linear-time encoding and decoding. Recently, it was shown that expander codes can attain capacity of a variety of channels, while the decoding error probability decreases exponentially with the code length. Moreover, it was recently shown that binary expander codes surpass the so-called Zyablov bound.

In this thesis, we first survey some recent results relating to expander codes. Then, we present improvements on the known bounds on the parameters of expander codes; in particular, we improve the lower bound on the minimum distance of these codes. We show that expander codes can be viewed as a concatenation of a certain nearly-MDS code with an appropriate inner code. The alphabet size of those nearly-MDS codes is smaller than the alphabet size of any similar known codes. This approach allows us to use GMD decoding to decode expander codes, leading to linear-time encoding and decoding algorithms.

Further, we discuss other results related to expander codes. In particular, we focus on the rate of decrease of the decoding error probability for capacity-achieving codes, and show how this rate can be accelerated by using a concatenation with expander codes as outer codes. We present a new family of generalized expander codes, which is different from all known families of expander codes, and investigate its parameters. We discuss the decoding of expander codes that are based on a non-bipartite underlying graph. Finally, we focus on expander codes that use weak constituent codes, and in some cases, we derive lower and upper bounds on the minimum distance of the corresponding expander codes.

CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the PHD technical reports of 2007
To the main CS technical reports page

Computer science department, Technion