基于交替方向乘子法的高效译码理论与算法研究

By using a decomposition-coordination procedure, the alternating direction method of multipliers (ADMM) decomposes large scale optimization problems into small problems which can be solved distributely. The high efficiency and distribution features of ADMM makes it suitable for decoding LDPC codes. This project aims to study the ADMM-based decoding theory and algorithms, and design practical decoding schemes with low complexity and excellent performance. The research contents of this project are summarized as follows: (1) Investigate dynamic message scheduling methods and design efficient message quantification schemes for ADMM decoding algorithms. (2) Design efficient ADMM decoding algorithms for cyclic/quasi-cyclic LDPC codes,and lower the computation and stroage overhead. (3) Estimate decoding performances of ADMM algorithms at error floor region by using the importance sampling technique, and investigate various methods to lower the error-floor performance. (4) Based on convext optimization and abstract algebra, we design efficient ADMM decoding algorithms for non-binary LDPC codes. (5) Study ADMM algorithms for joint detection and decoding problems with LDPC codes. It is expected that new theories and methods obtained during this research will explore intensive applications of optimization theory in the area of channel coding, and provide effient and reliable decoding schemes for future communication and storage systems.

交替方向乘子法(Alternating Direction Method of Multipliers,ADMM)通过分解-协作的方式将大规模优化问题分解为可分布式求解的多个小规模优化问题。ADMM的高效性和分布式特点，使其适用于LDPC码的译码。本项目旨在研究基于ADMM的译码理论及算法，设计具有极低复杂度且性能良好的实用译码方案。具体内容包括:研究ADMM译码算法动态消息调度策略，设计合理的消息量化机制；针对循环/准循环LDPC码，设计高效的ADMM译码算法，降低运算和存储开销；借助重要性抽样理论，估计ADMM译码在错误平层区域的性能，研究降低错误平层的各种方法；基于凸优化和抽象代数理论，设计多元LDPC码的ADMM译码算法；研究基于ADMM的LDPC码联合检测译码算法。通过本项目的研究，期望能够进一步探索基于优化技术的译码理论与算法，为未来的通信和存储系统提供可靠、高效的译码方案。

线性规划译码是LDPC码的一种重要的译码方法，但其译码复杂度很高。本项目旨在研究基于 ADMM 的低复杂度线性规划译码理论及算法，设计具有极低复杂度且性能良好的实用译码方案。本项目的主要研究内容和取得的成果概述如下：. (1) 在LDPC码的ADMM译码算法中，欧氏投影操作的计算复杂度较高。利用欧氏投影的对称性设计了基于查表法的ADMM译码算法，能够有效降低译码复杂度。对于IEEE 802.16e标准中的(576,288)LDPC码，所所提出的方法能节约大约35%的译码时间。. (2) 针对ADMM惩罚译码器，通过对不同变量节点引入不同的权重来增加所提出方法的灵活度，通过利用差分进化的方法优化权重因子，可以有效地改善译码性能。对于所仿真的3个LDPC码，所提出方法有0.3-0.5dB的编码增益。. (3) 一般可从两个角度来降低欧氏投影操作对ADMM译码的影响：降低投影操作的复杂度以及减少译码过程中调用投影操作的次数。我们考虑通过降低投影操作的次数来降低译码复杂度。仿真实验结果表明所提出方法可以降低20%的译码时间。. (4) 通过设计分段罚函数来有效的抑制伪码字从而改善ADMM译码算法。这样设计的罚函数在0和1附近更容易甄别伪码字和正确码字，从而改善译码性能。仿真结果表明所设计的分段罚函数能够加速ADMM译码收敛速度，改善译码性能。. (5) 提出了一种基于校验节点的消息调度策略，它通过计算消息残余来安排将要更新的校验节点，使得具有最大消息残余的节点先进行调度。仿真结果表明，所提出的调度策略与已有的调度策略相比，译码的收敛速度会加快。. 本项目的研究能够改善ADMM的译码性能，并有效降低译码复杂度。同时，所提出的基于查表法的ADMM译码算法由于逻辑简单，也便于硬件实现。这对于ADMM译码的实用化有一定的推动作用。