Expander Codes: Constructions and Bounds

Speaker: Dr. Vitaly Skachek , Claude Shannon Institute, University College Dublin, Ireland


Low-density parity-check (LDPC) codes were introduced in 1962, but were almost forgotte n. In recent years, they have attracted a lot of attention due to the practical efficiency of “average” LDPC codes. However, the performance of explicitely constructed LDPC codes s till suffers performance disadvantages compared with “average” LDPC codes. The most promis ing 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. Recent ly, it was shown that expander codes can attain capacity of a variety of channels, while t he decoding error probability decreases exponentially with the code length. Moreover, it w as recently shown that binary expander codes surpass the so-called Zyablov bound. In this talk, we first survey some recent results relating to expander codes. Then, we present im provements on the known bounds on the parameters of expander codes; in particular, we impr ove the lower bound on the minimum distance of these codes. We show that expander codes ca n 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 sim ilar known codes. This approach allows us to use GMD decoding to decode expander codes, le ading to linear-time encoding and decoding algorithms. Further, we discuss other results r elated to expander codes. In particular, we discuss the decoding of expander codes that ar e based on a non-bipartite underlying graph. We present a new family of generalized expand er codes, which is different from all known families of expander codes, and discuss its pa rameters. 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 e xpander codes as outer codes. Finally, we focus on expander codes that use weak constituen t codes, and in some cases, we derive lower and upper bounds on the minimum distance of th e corresponding expander codes.