论文部分内容阅读
纠错码理论理论提出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倍。