论文部分内容阅读
基于交替方向乘子法(Alternating Direction Method of Multiplier,ADMM)的线性规划(Linear Programming,LP)译码算法是一种将线性规划和LP译码模型相结合后得到的译码方法。ADMM-LP译码算法的核心思想是将大的译码问题分解成几个小的局部问题,通过迭代的方式求增广拉格朗日算子的解。当前,ADMM-LP译码算法主要应用于低密度奇偶校验(Low Density Parity Check,LDPC)码的译码。LDPC码的性能优越,能够无限接近香农极限,且构造简单,因此广受关注。LDPC码一般采用置信度传播(Belief Programming,BP)译码算法进行译码,但是该算法在有短环的情况下,性能会大幅度下降,因此许多研究人员都将研究重点转向了线性规划译码算法。线性规划译码算法是最大似然译码算法的一种近似,该算法具有最大似然认证特性,但是其译码复杂度较高,限制了其在早期被广泛应用。ADMM-LP译码算法在一定程度上降低了线性规划译码算法的复杂度。ADMM-LP译码算法不仅降低了 LP译码算法的复杂度,还保证了其仍然具备最大似然认证特性,易于理论分析。尽管和LP译码算法相比,ADMM-LP译码算法的复杂度降低了,但是依然有进一步优化的空间。当前影响ADMM-LP译码算法复杂度的主要因素是其译码过程中涉及到的欧几里德投影操作,且随着LDPC码校验节点的度的不断提升,其投影的复杂度会有大幅度的上升。这表明,欧几里德投影操作会消耗大量的译码时间,采用ADMM-LP译码算法对校验节点度比较低的LDPC码进行译码时,ADMM-LP译码算法在算法复杂度上受限较小,但是应用在校验节点度很高的HDPC码进行译码,算法的复杂度会急剧上升。此外,ADMM-LP译码算法应用在HDPC码时,其对应的校验多胞体会出现大量的伪码字,从而造成译码性能急剧下降。为了降低投影复杂度,提升ADMM-LP译码性能,同时也能将其应用在HDPC码中,本文提出了线段投影算法和ADMM-LP并行译码算法。本文所做的工作如下:1.提出了基于线段投影算法的ADMM译码算法。通过分析译码模型中耗时最长的欧几里德投影,本文提出了一种新的近似投影算法——线段投影算法。该算法将求解多维空间校验多胞体投影转换为在二维平面求点到线段上投影的问题,大幅度降低了投影算法的复杂度。实验结果表明,线段投影算法可以节省约7%-43%的投影时间,在待投影向量维度高达512的情况下,节省的时间甚至可以达到95%。2.提出一种适用于高密度奇偶校验码的译码算法——ADMM-LP并行译码算法。该算法利用多个ADMM译码器同时译码,取最好的译码结果作为输出,从而大幅度地提升了译码器性能。此外,为了降低译码器复杂度,将偶数顶点投影算法应用在ADMM译码器上,既保证了译码器的译码性能不下降,还大幅度降低了译码复杂度。实验结果表明,该算法不仅能够在高密度奇偶校验码上获得0.5dB-1dB的译码性能提升,还具有较低复杂度。