Differences

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

--- en:projects:details:phd01 [2009/06/05 16:53]
cangiani
+++ en:projects:details:phd01 [2016/06/23 11:26] (current)
@@ Line 1: / Line 1: @@
-=== Expander graphs and error-correcting codes  ===
-foo
 ---- dataentry project ----
 title : Expander graphs and error-correcting codes
@@ Line 9: / Line 5: @@
 contacttel: 021 6937512
 contactroom: BC 110
-type : phd
+type : phd thesis
-status : completed
+state : completed
 table : projects
 created_dt : 2003-01-01
@@ Line 16: / Line 12: @@
 completed_dt : 2007-01-01
 by : Andrew Brown
-output_media400 : en:projects:andrewthesis.pdf
+output_media400 : en:projects:andrewthesis.pdf|Download Andrew's Thesis
 ======
 template:datatemplates:project
 ----
+=== 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.

Title

Sub-Title

Differences