ADMM Decoding Algorithm With High Performance And Low Complexity

Linear programming(LP)decoding algorithm based on Alternating Direction Method of Multiplier(ADMM)is a decoding algorithm combining linear programming and LP decoding model.The ADMM-LP decoding algorithm decomposes a large decoding problem into several small local problems,and iteratively solves the solution of the Lagrangian operator.Currently,the ADMM-LP decoding algorithm is mainly applied to decoding of Low Density Parity Check(LDPC)codes.The performance of the LDPC code can approach the Shannon limit indefinitely,and the structure is simple.Originally,Belief Programming(BP)decoding algorithm was used on LDPC codes,but the performance of this algorithm is greatly limited by the case of short loops,so many researches have focused on linear programming decoding algorithm.Linear programming decoding is an approximation of the maximum likelihood decoding algorithm.The algorithm has the maximum likelihood authentication feature,but the decoding complexity of the algorithm is high,which makes it unable to be widely used.The ADMM-LP decoding algorithm solves this problem.The ADMM-LP decoding algorithm not only reduces the complexity of the LP decoding algorithm,but also ensures that it still has the maximum likelihood authentication feature and is easy to analyze.Although the complexity of the ADMM-LP decoding algorithm is reduced compared with the LP decoding algorithm,the complexity of the algorithm still has room for further optimization.The main factor that affects the complexity of the ADMM-LP decoding algorithm is that the Euclidean projection involved in the decoding process is an extremely complicated operation,and as the degree of LDPC code check nodes continues to increase,the complexity will increase significantly.This also means that the Euclidean projection operation consumes a lot of decoding time.When the ADMM-LP decoding algorithm is used for the LDPC code.But when the decoding algorithm is used for the HDPC code with high degree of check nodes,the complexity of the algorithm will rise sharply.In addition,when ADMM-LP decoding algorithm is applied to HDPC code,its basic polytope will appear a large number of pseudo-code words,which will cause the decoding performance to drop sharply.In order to reduce the projection complexity and improve the ADMM-LP decoding performance,and at the same time make it applicable to HDPC codes,this paper proposes line segment projection algorithm and ADMM-LP parallel decoding algorithm.The work done in this article is as follows:1.An ADMM decoding algorithm based on line segment projection algorithm is proposed.By analyzing the time-consuming Euclidean projection in the decoding model,this paper proposes a new approximate projection algorithm-line segment projection algorithm.This algorithm converts the solution of multi-dimensional space check polytope projection to the problem of finding points ononto line segments in two-dimensional plane,which greatly reduces the complexity of projection algorithm.Experimental results show that the line segment projection algorithm can save about 7%-43%of the projection time.In the case of the vector dimension to be projected up to 512,the time saved can even reach 95%.2.Propose a decoding algorithm suitable for high-density parity-check codes—parallel ADMM-LP decoding algorithm.The algorithm uses several ADMM decoders to decode at the same time,and takes the best decoding result as output,thereby greatly improving the performance of the decoder.In addition,in order to reduce the complexity of the decoder,the even vertex projection algorithm is applied to the ADMM decoder,which not only ensures that the decoding performance of the decoder does not decrease,but also greatly reduces the decoding complexity.Experimental results show that the algorithm can not only achieve 0.5dB-1dB decoding performance improvement on high-density parity-check codes,but also has low complexity.