多进制线性分组码的线性规划译码算法研究

发布时间：2018-07-25 16:01

【摘要】：纠错码理论理论提出60多年来,在理论和工程应用中均取得了丰硕的成果,线性规划(Linear Programming,LP)译码就是其中之一。本文提出了一种新的多项式时间复杂度的LP译码算法,通过理论及实验仿真验证了该方法在一定条件下满足“ML特性”和“码字独立性”,同时结果表明该算法比Flanagan提出的LP译码算法执行效率更高。主要内容和研究成果如下:1.首先介绍了线性分组码的基本概念及其Tanner图表示形式,并引入了线性规划的基本概念。由于线性规划最优值总在可行域组成的多面体顶点处取得,结合这个性质,Feldman等人创造性地提出了LP译码理论。其次讨论了Feldman的LP译码算法,并针对二进制线性分组码设计了基于奇偶校验多面体的LP译码算法。最后通过仿真实验验证该方法与Feldman LP译码算法性能相当。2.本文针对多进制线性分组码译码展开了深入的研究。首先结合多进制线性分组码的校验矩阵和Tanner图表示形式阐述了置信传播(Belief Propagation,BP)译码算法的流程。其次从最大似然(Maximum Likelihood,ML)译码算法出发,详细地介绍了Flanagan LP译码方法的原理及其数学优化模型。通过分析发现Flanagan LP译码算法的复杂度随着校验矩阵行重呈指数增长,在工程中难于实现,同时通过仿真实验验证了Flanagan LP译码模型复杂度过高这一问题。3.线性规划多面体结构的研究也是本文的一个重点。主要讨论了描述多元奇偶校验多面体的基本方法,并且构造了一种新的2q元奇偶校验多面体,同时给出了该多面体的几种重要特性,最后对这些理论进行分析并给予证明。4.本文主要讨论了多进制线性分组码的LP译码问题,并提出了一种新的多进制线性分组码的多项式时间复杂度的LP译码算法。对于多进制线性分组码,我们采用奇偶校验多面体将ML译码松弛为一种新的LP译码,该线性规划模型只含有多项式复杂度的辅助变量和约束条件。最后不仅证明了,如果多进制码字的等价二进制码字能够构成基于GF(2)的子空间并且信道满足对称特性,本文提出LP译码算法就具有“ML特性”和“码字独立性”。同时,通过仿真实验验证了该LP译码算法不仅能很好地逼近ML译码算法,并能获得与Flanagan LP译码算法相同的性能,而且在16QAM调制下其执行效率比Flanagan LP译码算法高了近15倍。
[Abstract]:Since the error-correcting code theory was put forward more than 60 years ago, great achievements have been made in both theory and engineering application, among which Linear programming LP decoding is one of them. In this paper, a new LP decoding algorithm with polynomial time complexity is proposed. The theoretical and experimental results show that the method satisfies the requirements of "ML characteristics" and "codeword independence" under certain conditions. The results show that the algorithm is more efficient than LP decoding algorithm proposed by Flanagan. The main contents and research results are as follows: 1. This paper first introduces the basic concept of linear block code and its Tanner graph representation, and introduces the basic concept of linear programming. Since the optimal value of linear programming is always obtained at the vertex of polyhedron composed of feasible domains, Feldman and others creatively put forward LP decoding theory. Secondly, the LP decoding algorithm of Feldman is discussed, and the LP decoding algorithm based on parity check polyhedron is designed for binary linear block codes. Finally, the simulation results show that the performance of this method is equivalent to that of Feldman LP decoding algorithm. In this paper, the decoding of multiary linear block codes is studied. Firstly, the flow of Belief propagation BP decoding algorithm is described by combining the check matrix of multiary linear block codes and the representation of Tanner diagram. Secondly, the principle of Flanagan LP decoding method and its mathematical optimization model are introduced in detail from the Maximum LikelihoodML decoding algorithm. It is found that the complexity of the Flanagan LP decoding algorithm increases exponentially with the line repetition of the check matrix, and it is difficult to be implemented in engineering. At the same time, the problem of high complexity of the Flanagan LP decoding model is verified by simulation experiments. The study of linear programming polyhedron structure is also an important part of this paper. This paper mainly discusses the basic method of describing multivariate parity check polyhedron, constructs a new 2Q element parity check polyhedron, and gives several important properties of the polyhedron. At last, it analyzes these theories and proves them. In this paper, the problem of LP decoding for multiary linear block codes is discussed, and a new LP decoding algorithm with polynomial time complexity for multiary linear block codes is proposed. For multi-ary linear block codes, the parity-check polyhedron is used to relax ML decoding into a new LP decoding. The linear programming model contains only auxiliary variables and constraints of polynomial complexity. Finally, it is not only proved that if the equivalent binary codeword of the multiary codeword can form the subspace based on GF (2) and the channel satisfies the symmetry characteristic, the LP decoding algorithm has "ML characteristics" and "codeword independence". At the same time, the simulation results show that the LP decoding algorithm not only approximates ML decoding algorithm, but also achieves the same performance as Flanagan LP decoding algorithm, and its execution efficiency under 16QAM modulation is nearly 15 times higher than that of Flanagan LP decoding algorithm.
【学位授予单位】：西安电子科技大学
【学位级别】：硕士
【学位授予年份】：2014
【分类号】：TN911.22

【相似文献】