Studies On Construction Algorithm Of Bipartite Graphs For LDPC Erasure Codes

In recent years, binary erasure channel (BEC) model has received widespread attention as a result of its availability in modeling the Internet transmission system. Because of its encoding and decoding algorithms'linear time complexity and ability to arbitrarily approach the erasure channel capacity, Low density parity check (LDPC) erasure codes based on sparse random bipartite graph become one of the most optimal coding techniques and attract more and more attentions. While the bipartite graph construction is always a key issue in the construction of LDPC erasure codes.this dissertation mainly focus on the construction algorithms of random bipartite graphs for LDPC erasure codes, some results are obtained and summarized as follow:1. The basic principle of LDPC codes is illuminated; two kinds of graph model formats of LDPC and their advantages and disadvantages are analyzed. The encoding and decoding principles of LDPC erasure codes and two kinds of capacity-approaching the erasure channel distribution sequences are introduced.2. Some key issues in construction of Tornado codes are investigated, the degree sequence amendment algorithm, the degree distributing algorithm and multiple-edge eliminating algorithm of bipartite graph are designed, based on these algorithms, the construction algorithm of random bipartite graphs in the designs of Tornado codes is proposed. By analyzing some parameters'affections on Tornado codes'performance with simulation experiences, the parameter-selection rules are generalized.3. Based on the investigation of degree sequence for right regular erasure codes, the parameter-optimization algorithm of degree sequences for right regular erasure codes is designed. Based on this algorithm, the construction algorithm of random bipartite graphs in the designs of right regular erasure codes is proposed. Simulation results demonstrate the effectiveness of the proposed parameter-optimization algorithm of degree sequences and the validity of the construction algorithm of random bipartite graphs.4. The influence of cycles in bipartite graphs on LDPC decoder's performance is analyzed, and the methods for computing the value of approximate cycle extrinsic message degree (ACE) in cycles are introduced. The bipartite graphs'construction method for right regular erasure codes using progressive edge-growth (PEG) algorithm is proposed. Simulation results show that the right regular erasure codes with bipartite graph constructed in this method will raise the performance significantly.