Reseach On Linear Programming Decoding Of Nonbinary Linear Block Codes

The error correcting coding theory has got thrive progress in both theoretical and practical for the fifty years. The linear programming decoding(LP) is one of the most important results. In this paper, a polynomial-sized LP decoder is proposed. It keeps the similar properties to the existing Flanagan LP decoders for general linear block codes, such as "ML certificate’’ and "codeword error-independent" uner some conditions. Moreover, it can execute faster than Flanagan LP decoding. The main contents and results are as follows:1. The concept and Tanner graph of linear block code are studied. Also basic theory of linear programming is introduced. The optimum values of linear programming are obtained at the vertex of polytope, which makes Feldman proposed LP decoding possible. Through discussing the Feldman LP decoding, a LP decoding for binary linear codes based on parity check polytope is designed. Finally, simulation results proves that such algorithm can obtain same performance as Feldman LP decoding algorithm.2. For nonbinary linear block codes, deep discussion is also presented. Firstly, belief propagation decoding method is analyzed by introducing parity check matrix and Tanner graph of nonbinary linear block codes. In addition, the Flanagan LP decoding algorithm is studied by relaxing the maximum likelihood decoding. However, Flanagan LP decoding is hard to realize in practice, for which its complexity grows with exponent. Finally, experimental results shows that the Flanagan LP algorithm has large complexity.3. The study of the polytope structure is also another key point. It mainly discussed the basic method on describing nonbinary parity check polytope. A new 2q-ary parity check polytope is designed and its several properties are proposed, which are proved by theoretical analysis.4. Deep discussion has been presented on the LP decoding for nonbinary linear block code. A polynomial-sized LP decoder is also proposed. Based on the formulated polytope, maximum likelihood decoding problem for the considered nonbinary linearblock codes is relaxed to a linear program, which consists of polynomial-sized auxiliary variables and constraints. Finally, we show that the resulting LP decoder keeps the similar properties to the existing LP decoders for general linear block codes, such as "ML certificate’’ and " codeword error-independent’’ if the equivalent binary codewords of the nonbinary linear block code form a subspace over GF(2) and the channel satisfies some specified symmetry condition. Simulation results for modulation systems are given to demonstrate the performance of the proposed LP decoder, which shows it not only can achieve the performance of maximum likelihood, but also it can obtain the same results as Flanagan LP decoding. Its results show that execution time is fifteen times faster than Flanagan LP decoding algorithm under the 16 QAM modulation.