Research On Mathematical Programming Decoders For LDPC Codes Via ADMM And Degree Decomposition

Low-density parity-check(LDPC) codes have drawn significant attention from domestic and international scholars because of their performance approaching to Shannon capacity limits.In the past decade,besides traditional belief propagation(BP) decoding,mathematical programming(MP) decoding has gained much popularity in coding fields with its advantages of lower error floor,easily performance analysis and optimization,etc.However,high decoding complexity limits the application and development of MP decoding in practice.Up to now,the alternating direction method of multipliers(ADMM) as an efficient mathematical tool for solving large scale optimization problems,has been widely used in machine,statistical learning and related areas.Therefore,by combining ADMM technique with MP decoding model,this dissertation is devoted to designing decoding algorithms for binary/nonbinary LDPC codes with low complexity and good error-correction performance.The novelties and contributions are listed as follows.To solve the high-complexity problem of general-purpose linear programming(LP) decoders for binary LDPC codes,a binary LP decoding algorithm based on ADMM and degree decomposition is proposed.Specifically,we first transform the general parity-check equation into a set of three-variables parity-check equations by using check-node degree decomposition,then express each three-variables parity-check equation by several linear inequalities and obtain a linear integer programming problem which is equivalent to the binary ML decoding problem.Further,the linear integer programming problem is relaxed to the desired degree-decomposition-based LP decoding problem and an efficient algorithm based on the ADMM technique is developed to solve this LP relaxation.By exploiting the orthogonality structure of the constraint matrix in the LP model,each ADMM update step can be implemented in parallel.Moreover,complexity analysis shows that our proposed LP decoder in each iteration has linear complexity in terms of the LDPC code length.Finally,the proposed LP decoder eliminates the high-complexity Euclidean projection on the check polytope compared with the existing ADMM-based LP decoders and thus greatly improves decoding efficiency,which has been demonstrated by simulation results.To further enhance the error correction performance of LP decoding in low signal-to-noise(SNR) regions,an improved binary quadratic programming(QP) decoding algorithm based on ADMM and degree decomposition is proposed.Specifically,by adding a non-convex quadratic penalty term into the objective of the degree-decomposition-based binary LP decoding model,we can make non-integral solutions more costly and obtain the corresponding degree-decomposition-based binary QP decoding model.Then,an ADMM-based algorithm is customized to solve this QP decoding problem.Owing to the variable separability of the added quadratic penalty term and the orthogonality structure of the constraint matrix in the QP model,variables in each updated step can be solved analytically in parallel and the complexity of the proposed algorithm in each iteration is shown to be linear in terms of the LDPC code length.Moreover,it is proved that the proposed ADMM algorithm converges to a stationary point of the non-convex QP problem under the assumption of sequence convergence.We also verify that the proposed decoder satisfies the favorable property of the all-zeros assumption.Finally,simulation results shows that our proposed binary QP decoding algorithm not only improves the error correction performance of LP decoding at low SNRs and achieves lower error rate than the binary BP decoder,but also costs less decoding time than the state-of-the-art ADMM-based binary MP decoders.To solve the high-complexity problem of MP decoders for nonbinary LDPC codes,a nonbinary QP decoding algorithm based on proximal-ADMM and degree composition is proposed.First,the general nonbinary parity-check equation is equivalently transformed into a set of three-variables parity-check equations by check-node degree decomposition approach and each three-variables parity-check equation can be expressed by several binary linear inequalities via mapping and permutation,then an equivalent linear integral programming of the nonbinary ML decoding problem in finite fields GF(2~q) is obtained.Second,we relax the binary constraints of this linear integral programming to the box ones,add redundant linear constraints,and add a nonconvex quadratic penalty term into the objection function,which leads to our nonbinary QP decoding model in GF(2~q).Third,we design an algorithm based on proximal-ADMM technique to solve the resulting nonbinary QP decoding problem.By exploiting the potential structure of the QP model,variables in each ADMM iteration can be updated in parallel.Moreover,complexity analysis shows that the complexity of the proposed nonbinary QP decoding algorithm is linear to the LDPC code length.Furthermore,we verify that the proposed nonbinary QP decoding algorithm converges to some stationary point of the nonconvex QP problem.Finally,simulation results demonstrate that our proposed nonbinary QP decoder attains better error correction performance than the nonbinary BP decoder and has lower decoding complexity than the existing ADMM-based nonbinary MP decoding algorithm.In summary,this dissertation proposes three MP decoding algorithms based on the ADMM technique and check-node degree decomposition for LDPC codes with linear complexity and excellent error-correction performance,and verifies that the proposed algorithms are superior to the existing decoding algorithms,which provides new ideas and methods for the theoretical research and engineering practice of LDPC decoding.