Codes, graphs and graph based codes

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.