This shows you the differences between two versions of the page.

Link to this comparison view

en:group:seminars:20071122 [2016/06/23 11:26] (current)
Line 1: Line 1:
 +---- dataentry seminar ----
 +date_dt : 2007-11-22
 +title : Expander Codes: Constructions and Bounds
 +speaker : Dr. Vitaly Skachek
 +affiliation :  Claude Shannon Institute, University College Dublin, Ireland
 +time : 16h15-17h15
 +room : BC129
 +table : seminars
 +=== Abstract ===
 +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.