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

Link to this comparison view

en:projects:details:phd01 [2010/03/26 10:34]
en:projects:details:phd01 [2016/06/23 11:26]
Line 1: Line 1:
----- dataentry project ---- 
-title : Expander graphs and error-correcting codes  
-contactname:​ Prof. Amin Shokrollahi 
-contactmail_mail:​ amin.shokrollahi@epfl.ch 
-contacttel: 021 6937512 
-contactroom:​ BC 110 
-type : phd theses 
-status : completed 
-table : projects 
-created_dt : 2003-01-01 
-taken_dt : 
-completed_dt : 2007-01-01 
-by : Andrew Brown 
-output_media400 : en:​projects:​andrewthesis.pdf|Download Andrew'​s Thesis 
-=== Abstract: === 
-This work is concerned with codes, graphs and their links. ​ 
-Graph based codes have recently become very prominent in both information theory 
-literature and practical applications. While most research has centered around their  
-performance under iterative decoding, another line of study has focused on more  
-combinatorial aspects such as their weight distribution. ​ 
-This is the angle we explore in the first part of this thesis, investigating the trade-off ​ 
-between rate and relative distance. More precisely, we show, using a probabilistic argument, ​ 
-that there exist graph-based codes approaching the asymptotic Gilbert-Varshamov bound, ​ 
-and that are encodable in time O(n1+ε) for any ε > 0, where n is the block length. ​ 
-The second part is concerned with more practical issues, more specifically the erasure channel. ​ 
-Although the codes mentioned above have been shown to perform very well in this setting, this  
-nonetheless requires their lengths to be quite large. When short blocks are required, certain ​ 
-algebraic constructions become viable solutions. In particular Reed-Solomon (RS-) codes are  
-used in a wide range of applications. However, there do not appear to be any practical uses of 
-the more general Algebraic-Geometric (AG-) codes, despite numerous advantages. ​ 
-We explore in this work the use of very short AG-codes for transmissions over the erasure channel. ​ 
-We present their advantages over RS-codes in terms of the encoder/​decoder running times, and  
-evaluate the drawbacks by designing an efficient algorithm for computing the error probabilities ​ 
-of AG-codes. The work was done as part of an industrial collaboration with specific transmission 
- ​problems in mind, and we include some practical data to illustrate the theoretical improvements. ​ 
-Graphs and codes can be related in different ways, and a graph being a good expander often yields 
- a code with certain desirable properties. In the third part we deal with graph products and their 
- ​expansion properties. Just as the derandomized squaring operation essentially takes the square ​ 
-of a graph and removes some edges according to a second graph, we introduce the derandomized 
- ​tensoring operation which removes edges from the tensor product of two graphs according to a  
-third graph. We obtain a bound on the expansion of the product in terms of the expansions of the  
-constituent graphs. We also apply the same ideas to a code product, leading to the derandomized 
- code concatenation operation and its analysis.