基于交替方向乘子法的LDPC码译码方法研究

作     者：梁宁静 

作者单位：西安电子科技大学 

学位级别：硕士

导师姓名：慕建君

授予年度：2014年

学科分类：07[理学] 08[工学] 070104[理学-应用数学] 081101[工学-控制理论与控制工程] 0701[理学-数学] 0811[工学-控制科学与工程] 

主      题：低密度奇偶检验码 基于ADMM的LP译码 图形处理器 并行化方法 

摘      要：低密度奇偶检验(Low-Density Parity-Check, LDPC)码是一种性能逼近香农极限的线性分组码,是信道编码领域的研究热点之一,目前已经广泛应用于无线通信和数字存储等领域。随着信息技术不断发展,通信系统要求信息能更快速和更可靠地传输,存储系统则要求更高的存储密度,设计性能优异且具有极低译码复杂度的编译码算法对未来通信和存储系统十分重要。基于交替方向乘子法(Alternating Direction Method of Multipliers, ADMM)的LDPC码线性规划(Linear Programming,LP)译码算法不仅具有传统LP译码的最大似然认证和便于分析的特点,而且大幅度降低了基于优化理论设计的译码算法的复杂度。基于A DMM的LP译码算法应用于规模较大的LDPC码时译码时间较长,不利于仿真分析和实际的工程实现。近年来图形处理器(Graphic Processing Unit,GPU)在浮点运算以及内存带宽方面突飞猛进的发展极大地推动了并行计算的研究,基于ADMM的LP译码算法具有很好的并行化结构,非常适合在GPU上实现。为了大幅度提高译码速度,本文借助GPU对基于ADMM的LP译码方法进行了研究。本文主要工作概括如下：1.介绍了LDPC码及其Tanner图模型的理论基础,概述了LDPC码的置信传播(Belief Propagation,BP)和最大似然译码算法,阐述了GPU的Fermi体系架构和统一计算设备架构(Compute Unified Device Architecture,CUDA)编程技术,分析了GPU的纹理存储器(texture memory)及全局存储器(global memory)的访问特点。2.给出了基于ADMM的线性规划译码模型,分析了译码方法中计算量大的欧几里得投影算法,在加性高斯白噪声(A dditive White Gaussian Noise)信道下对ADMM译码算法进行了仿真。仿真结果表明,基于ADMM的译码算法具有较好的性能,并且译码速度可以达到BP算法的2倍。3.根据ADMM译码算法的迭代消息传递思想,设计了一种基于GPU的并行化译码方案,详细分析了节点消息更新的并行化实现方法。根据页锁定内存(pinned memory)和纹理存储器的访问特点,在并行化译码过程中设计了两种优化方法,给出了基于ADMM的并行化译码方法的仿真实现。仿真结果表明,在译码性能接近的情况下,借助GPU实现的ADMM译码方法与纯CPU实现相比最高可以获得19倍的加速比,有效利用GPU的多核架构提高了译码效率。