New Lower Bounds For The Minimum Distance Of Graph Code

The construction of new codes with good parameters is one of the most important topics in coding theory. In1981, Michael Tanner proposed a new code, which is now known as graph code or Tanner code, based on graph. In recent decades, much work has been done on the properties of graph codes. In1996Sipser and Spielman investigated the graph code based on expander graph with efficient decoding algorithm.In this thesis, we focus on the minimum distance of graph codes. Firstly, we obtain an upper bound on the dimension of graph code. Then a bound on the number of edges of a subgraph is given. As an application, we get a new lower bound on the minimum distance of graph codes. Our work is independent of the second largest eigenvalue of the underlying graph. A new class of graph code, whose minimum distance can be exactly determined, is constructed. Some examples of our bounds are given.