基于因子图的低密度校验码关键技术研究

论文摘要

随着对宽带、高速通信业务需求的不断增加和通信技术的不断进步,作为一种提高信息传输的可靠性和有效性的重要手段的前向纠错码技术近年来获得了快速的发展,同时作为通信理论的重要组成部分,更有效可靠的纠错码技术的理论研究与应用正在越来越受到人们的关注与重视。本文正是在国家高技术研究发展计划（863计划）“数字音视频编码、传输、测试与应用示范”（No.2002AA119010）的子课题“基于无线环境的联合信源信道系统框架研究”、国家自然科学基金重大项目“未来移动通信系统基础理论与技术研究（No.60496315）”等研究项目的资助下,对近年来在纠错码领域表现抢眼的低密度校验码（Low-Density Parity-Check Codes,LDPC）的若干关键技术展开了研究。LDPC最早是在1962年由Robert G.Gallager提出的,它是一类可以用稀疏校验矩阵或因子图进行描述的线性分组码,具有接近Shannon限的良好性能和因子图等有效的分析工具,因而近年来成为纠错码领域的研究热点。因子图最早是由Tanner提出的,它是表征校验节点与变量节点关系的二部图。因子图与校验矩阵一一对应,当校验矩阵的某位置为“1”时,在因子图上分别对应校验矩阵的行和列的校验节点与变量节点之间就有一条边相连。本文正是利用因子图这个工具,对LDPC码的编码、译码和密度进化这几个方面的关键技术进行了研究。在进行后续研究前,本文首先全面的介绍了LDPC码起源、发展和当前的研究与应用情况,给出了它的因子图表示和校验约束编码结构,并基于因子图推导了译码后验概率的表达式;介绍了规则码、非规则码和基于GF（q）域的LDPC码的编码结构,对不同编码结构下LDPC的性能进行了讨论,结果表明,非规则码性能优于规则码,在GF（q）域的LDPC码性能要好于二元LDPC码,域值越高性能越好。为了获得不含短环的LDPC码的编码算法,对因子图进行了具体的分析,探讨了因子图中环对码性能影响的成因,利用图论工具和构造辅助的校验点结构图邻接矩阵的方法,分析了因子图中形成环校验节点之间的关系,获得了一些有用的定理和性质,并在这些定理和性质的基础上提出了一种新的构造算法。新的构造算法能够有效的避免短环的出现,文章给出了无4-环、6-环和8-环的LDPC码的具体构造算法,在仿真实验中显示了比随机生成算法更好的性能。本文提出的构造算法并不限定于规则码或是非规则码,可根据设定的列重序列生成符合要求的规则码或是非规则码,因而具有更好的通用性。在LDPC码的译码算法研究方面,为了获得置信传播迭代译码算法的高性能,需要能减少因子图中环对它的影响,因此,在本文译码算法的研究部分分析了因子图中存在的环对置信传播译码算法的影响,给出了一种优化的译码算法。该算法在译码中通过动态检测信息的传递路径,适时的切断通过因子图上的环传回的消息,能够在一定程度上消除因子图中环对置信传播译码算法的影响,使原始信息在不受到经环传回的重复信息的污染下传播到尽可能多的节点。在仿真实验中,我们对比了本文算法与传统算法,分析了两种算法的计算复杂度与性能,结果表明,该算法在中短码长的情况下表现出比传统算法更好的性能,在信道状况较差时,在不降低性能的情况下,本文算法具有更小的计算复杂度。在LDPC码密度进化理论分析方面,由于现有的密度进化理论是建立在基于无环因子图假设的基础上的,没有考虑因子图上存在的环以及环对迭代译码消息进化的影响。因此,本文通过讨论,获得了一般LDPC码因子图上环存在的概率表述,在这个概率表述基础上,对离散密度进化和连续密度进化在AWGN信道上的表现分别进行了分析。在离散密度进化分析中,使用了Gallager最早提出的硬判决译码算法,获得了迭代译码中误码率的进化,得到在一定初始误码率的条件下,译码误码率的收敛情况。仿真实验结果显示,有环因子图下,其离散密度进化分析获得译码阈值低于无环因子图的情况。在连续密度进化中,使用基于对数似然比量度上的概率测度进行分析,获得了消息密度进化的计算表达式。连续密度进化的计算量非常大,可采用高斯逼近进行近似计算。

论文目录

• 摘要
• ABSTRACT
• 1 绪论
• 1.1 数字通信系统及其差错控制
• 1.2 信道编码理论及其发展
• 1.3 低密度校验码的研究与发展
• 1.4 本文研究内容及安排
• 2 LDPC 码原理及其构造
• 2.1 引言
• 2.2 LDPC 码的因子图表示
• 2.3 LDPC 码的构造
• 2.4 本章小结
• 3 无短环LDPC 码构造算法研究
• 3.1 引言
• 3.2 LDPC 码的编码
• 3.3 LDPC 码的因子图分析
• 3.4 无短环的LDPC 码构造算法
• 3.5 仿真结果及性能分析
• 3.6 本章小结
• 4 LDPC 码的优化译码算法研究
• 4.1 引言
• 4.2 置信传播译码算法
• 4.3 优化的译码算法及其实现
• 4.4 仿真结果及性能分析
• 4.5 本章小结
• 5 有环因子图上密度进化理论分析
• 5.1 引言
• 5.2 密度进化及其高斯逼近
• 5.3 因子图上环存在性分析
• 5.4 有环因子图上的离散密度进化
• 5.5 有环因子图上的连续密度进化
• 5.6 本章小结
• 6 全文总结与展望
• 6.1 本文贡献
• 6.2 展望
• 致谢
• 参考文献
• 附录1 攻读博士期间发表论文目录
• 附录2 英文缩写对照
• 附录3 数学符号说明
• 附录4 863 计划子课题任务合同书
• 附录5 国家自然科学基金委员会文件