论文部分内容阅读
低密度奇偶校验(Low-Density Parity-Check，LDPC)码是一种现有的能够逼近香农容量限的纠错码，受到国内外学者的广泛关注。近十年来，除了传统的置信传播(Belief Propagation，BP)译码算法，数学规划(Mathematical Programming，MP)译码算法凭借低误码平台、便于性能分析等优势引起了差错控制编码领域学者的广泛重视。但是其较高的译码复杂度限制了MP译码算法在实际场景中的应用和发展。交替方向乘子法(Alternating Direction Method of Multipliers，ADMM)作为求解大规模优化问题的一种有效的数学工具，目前在机器学习、统计学习等领域得到了广泛应用。本文通过将ADMM技术与MP译码模型相结合致力于研究计算复杂度低且纠错性能优异的二元/多元LDPC码译码算法，主要的工作和创新点如下：
1.针对传统的二元LDPC码线性规划(Linear Programming，LP)译码器复杂高的问题，提出了一种基于ADMM和度分解的二元LP译码算法。首先利用校验节点度分解的方法将一般二元校验方程等效为一组含有三变量的子校验方程，然后将每个子校验方程用若干个线性不等式等价表示，从而得到与二元最大似然(Maximum Likelihood，ML)译码问题等价的线性整数规划问题。再通过线性松弛方法将线性整数规划问题松弛为所需的基于度分解的二元LP译码问题。其次，基于ADMM算法对该LP译码问题进行求解，通过利用所设计的LP译码模型中约束矩阵的正交结构，使得每个ADMM更新步骤中的变量都可以并行求解，并指出所提出的二元LP译码算法在每次迭代中的计算复杂度线性正比于二元LDPC码的码长。最后，与现有的基于ADMM的二元LP译码算法相比，所提出的基于ADMM和度分解的二元LP译码算法不需要使用复杂高的奇偶多面体投影，从而提高了译码效率，并通过实验仿真验证了所提出的二元LP译码算法的有效性。
2.为了进一步提高二元LP译码算法在低信噪比区域的纠错能力，提出了一种改进的基于ADMM和度分解的二次规划(Quadratic Programming，QP)译码算法。首先，通过在基于度分解的二元LP译码模型的目标函数上增加一个非凸二次惩罚项，从而得到基于度分解的二元QP译码模型，然后利用ADMM算法对其进行求解。利用非凸二次惩罚项的变量可分离性和二元QP译码模型中约束矩阵的正交结构，使得每个ADMM更新步骤中的变量可以实现并行计算，而且指出所提出的二元QP译码算法在每次迭代过程中的计算复杂度随着二元LDPC码码长的增加呈线性增长。其次，从理论上证明了在序列收敛前提下，所提出的二元QP译码算法可以收敛到非凸QP问题的一个静态点；而且设计了一种简单的ML检测方法，能够快速检测二元QP译码算法输出的整数解是否为ML码字；同时还证明了所提出的二元QP算法满足“全零假设特性”。最后，仿真结果表明所提出的基于ADMM和度分解的二元QP译码算法大幅度提高了低信噪比区域的LP误码性能，从而获得比BP译码算法更低的误码率，并且与现有的基于ADMM方法的二元MP译码算法相比需要更少的译码时间。
3.针对多元LDPC码MP译码算法复杂度高的问题，提出了一种基于proximal-ADMM和度分解的多元QP译码算法。首先，通过利用校验节点度分解的方法将一般多元校验方程分解为一组含有三变量的子校验方程组，然后每个子校验方程经过映射和置换操作等价表示为二进制线性约束形式，从而得到与多元域GF(2q)上ML译码问题等效的二元线性整数规划问题。其次，通过将该线性整数规划模型进行线性松弛、增加线性冗余约束以及在其目标函数增加非凸二次惩罚项，进而设计出所需的多元域GF(2q)上基于度分解的QP译码模型。再次，基于proximal-ADMM算法对所设计的多元QP译码模型进行求解，通过充分利用该QP模型潜在的结构，则每个ADMM迭代步骤中的变量均能够实现并行更新，并且指出所提出的多元QP译码算法在每次迭代中的计算复杂度线性正比于多元LDPC码的码长。而且证明所提出的多元QP译码算法能够收敛到非凸QP问题的一个静态点。最后，通过实验仿真验证了基于proximal-ADMM和度分解的多元QP译码算法不仅可以获得比多元BP译码更强的纠错性能，而且与现有的基于ADMM的多元MP译码算法相比，具有更低的译码复杂度。
综上所述，本学位论文基于ADMM和校验节点度分解提出了三种具有线性复杂度且误码性能优异的LDPC码数学规划译码算法，并验证了所提译码算法优于现有译码算法，为LDPC码译码的理论研究和工程实践提供了新的思路和方法。
1.针对传统的二元LDPC码线性规划(Linear Programming，LP)译码器复杂高的问题，提出了一种基于ADMM和度分解的二元LP译码算法。首先利用校验节点度分解的方法将一般二元校验方程等效为一组含有三变量的子校验方程，然后将每个子校验方程用若干个线性不等式等价表示，从而得到与二元最大似然(Maximum Likelihood，ML)译码问题等价的线性整数规划问题。再通过线性松弛方法将线性整数规划问题松弛为所需的基于度分解的二元LP译码问题。其次，基于ADMM算法对该LP译码问题进行求解，通过利用所设计的LP译码模型中约束矩阵的正交结构，使得每个ADMM更新步骤中的变量都可以并行求解，并指出所提出的二元LP译码算法在每次迭代中的计算复杂度线性正比于二元LDPC码的码长。最后，与现有的基于ADMM的二元LP译码算法相比，所提出的基于ADMM和度分解的二元LP译码算法不需要使用复杂高的奇偶多面体投影，从而提高了译码效率，并通过实验仿真验证了所提出的二元LP译码算法的有效性。
2.为了进一步提高二元LP译码算法在低信噪比区域的纠错能力，提出了一种改进的基于ADMM和度分解的二次规划(Quadratic Programming，QP)译码算法。首先，通过在基于度分解的二元LP译码模型的目标函数上增加一个非凸二次惩罚项，从而得到基于度分解的二元QP译码模型，然后利用ADMM算法对其进行求解。利用非凸二次惩罚项的变量可分离性和二元QP译码模型中约束矩阵的正交结构，使得每个ADMM更新步骤中的变量可以实现并行计算，而且指出所提出的二元QP译码算法在每次迭代过程中的计算复杂度随着二元LDPC码码长的增加呈线性增长。其次，从理论上证明了在序列收敛前提下，所提出的二元QP译码算法可以收敛到非凸QP问题的一个静态点；而且设计了一种简单的ML检测方法，能够快速检测二元QP译码算法输出的整数解是否为ML码字；同时还证明了所提出的二元QP算法满足“全零假设特性”。最后，仿真结果表明所提出的基于ADMM和度分解的二元QP译码算法大幅度提高了低信噪比区域的LP误码性能，从而获得比BP译码算法更低的误码率，并且与现有的基于ADMM方法的二元MP译码算法相比需要更少的译码时间。
3.针对多元LDPC码MP译码算法复杂度高的问题，提出了一种基于proximal-ADMM和度分解的多元QP译码算法。首先，通过利用校验节点度分解的方法将一般多元校验方程分解为一组含有三变量的子校验方程组，然后每个子校验方程经过映射和置换操作等价表示为二进制线性约束形式，从而得到与多元域GF(2q)上ML译码问题等效的二元线性整数规划问题。其次，通过将该线性整数规划模型进行线性松弛、增加线性冗余约束以及在其目标函数增加非凸二次惩罚项，进而设计出所需的多元域GF(2q)上基于度分解的QP译码模型。再次，基于proximal-ADMM算法对所设计的多元QP译码模型进行求解，通过充分利用该QP模型潜在的结构，则每个ADMM迭代步骤中的变量均能够实现并行更新，并且指出所提出的多元QP译码算法在每次迭代中的计算复杂度线性正比于多元LDPC码的码长。而且证明所提出的多元QP译码算法能够收敛到非凸QP问题的一个静态点。最后，通过实验仿真验证了基于proximal-ADMM和度分解的多元QP译码算法不仅可以获得比多元BP译码更强的纠错性能，而且与现有的基于ADMM的多元MP译码算法相比，具有更低的译码复杂度。
综上所述，本学位论文基于ADMM和校验节点度分解提出了三种具有线性复杂度且误码性能优异的LDPC码数学规划译码算法，并验证了所提译码算法优于现有译码算法，为LDPC码译码的理论研究和工程实践提供了新的思路和方法。