Research On Iterative Decoding And Linear Programming Decoding Algorithms For Low-density Parity-Check Codes

Low-density parity-check (LDPC) codes have become an attractive research area in the modern channel coding field owing to their capacity-approaching performance. Compared with other error-correcting codes, LDPC codes have several merits. First of all, it is easy to construct and implement LDPC codes because of their simple structure described by sparse Tanner graph. Secondly, LDPC codes have low decoding complexity and delay. Finally, LDPC codes have good distance characteristic which can lower undetectable error probability. So LDPC codes have broad application prospects in the field of next-generation wireless communication, digital storage, gigabit ethernet and optical communication network. In this dissertation, the iterative decoding and linear programming (LP) decoding of LDPC codes are investigated. Some main results are obtained and summarized as follows:1. The relationship between instantons and short cycles in Tanner graphs of regular LDPC codes decoded by LP decoding is investigated. An algorithm to search for instantons is proposed which based on the strategy of path extending around the short cycles. Moreover, the instanton search algorithm for irregular LDPC codes is also developed. Simulation results on some typical LDPC codes show that our scheme is effective, and more instantons can be obtained by the proposed scheme when compared with the existing instanton search method.2. Based on check node decomposition of Tanner graphs corresponding to LDPC codes, an improved algorithm to compute the fractional distance is proposed. The proposed algorithm can compute the fractional distance of LDPC codes which have relative dense degree distribution of check nodes and long code length.3. A new method is presented to suppress fractional pseudowords by eliminating small instantons in irregular LDPC codes under the LP decoding over the binary symmetric channel (BSC). By appending several new rows to the original parity-check matrix, the optimal distribution spectrum of BSC-instantons in the modified code is obtained. Computer simulation results show that the proposed method can improve the fractional distance of parity-check matrices and considerably enhance the error-correcting performance of irregular LDPC codes at the cost of a slightly loss of the original code rate.4. An efficient selection algorithm of multi-level iterative decoders (MLID) is presented for LDPC codes over the BSC. By taking advantages of the characteristics of decoding rules for variable nodes on Tanner graphical presentations, a set of candidate MLIDs is constructed for some typical LDPC codes. Based on the evaluation of decoding performance for the received channel messages with various additional bias noise inputs derived from trapping sets, the statistical optimal MLID can rapidly be selected from the candidate MLIDs. At last, simulation results show the validity of the proposed algorithm.5. To design a powerful and fast decoder for the tradeoff between complexity and performance, a hybrid decoding scheme for LDPC codes over the BSC is proposed which combines an iterative decoder with LP decoders. Simulation results show that the proposed hybrid decoder outperforms its component decoder with a short decoding time.