Research On A Class Of Bipartite Graphs With Important Applications In LDPC Codes

As a popular topic in the field of current coding theory, Low-density Parity-check (LDPC) codes were proposed by Gallager in1962, and then in1995, the rediscovery of LDPC codes by Mackay and Neal caught people’s attention again. Due to their sparse parity-check matrices, LDPC codes have very good performance, and this makes them to be widely used in mobile communication system. LDPC codes still have quite well error performance for higher rate cases and hardware implementation, and this makes them have a broad prospect of application in optical fiber communication, deep space communication and magnetic recording channel.The error performance of general linear block codes will be restricted by their basic parameters. These parameters include the code rate, the code length and the minimum distance between codewords, etc. As a special class of linear block codes, the performance of a LDPC code is closely related to the inner structure of the Tanner graph or the bipartite graph which corresponding to the parity-check matrix of the LDPC code. When the girth of the bipartite graph is small, it may cause oscillations during passing information between nodes and check nodes, and results in insufficient decoding, the error performance is the degraded. So designing bipartite graph with large girth has become a popular topics for many coding scholars.In this thesis, we analyzed the influence of the structure of a bipartite graph to the performance of the corresponding LDPC code. then proposed a new construction method for a class of algebraic bipartite graphs D(k, q) of large girth, and give a proof for a known lower bound of their girth by analyzing the graph paths. Particularly, we proved a famous conjecture on the girth of D(k,q) for some special cases. This thesis is mainly arranged as follows:Firstly, we briefly reviewed the development of the theory of LDPC coding, which includes the definition and Tanner graph representation of LDPC codes, decoding methods of LDPC codes which are based on the graph model, as well as several important factors affecting the performance of LDPC codes.Then we described some related concepts about the bipartite graph D(k,q) of large girth, and constructed a new bipartite graph λ(k,q) which is isomorphic to D(k,q), then gave a close-form expression for the paths in the bipartite graph λ(k,q). By using this expression, we gave a new short proof for a known lower bound about the girth of D(k,q). Finally, we found the shortest cycle in the bipartite graph λ(k,q) under some special cases, and then obtained the exact girth. Particularly, we proved the following conjectureConjecture A: When k is odd and q≥4, the girth of D(k,q) is equal to k+5. is valid for q=p, k=2ps-5, where p is a prime and s. m are positive integers with ps>3.