中文摘要：

传统代数码二元校验矩阵中"1"的个数较多，称之为高密度校验码，其相应的Tanner图模型称为高密度图模型。高密度校验码的现有译码算法中，硬判决译码性能较差、软判决译码复杂度过高，无法满足下一代存储和光通信系统的需求。本项目旨在研究高密度图模型下的迭代/线性规划译码理论及方法，设计逼近最大似然译码性能的实用译码方案。具体内容包括设计复杂度低、译码性能好的高密度校验码迭代译码算法，借助最优化及迭代译码分析理论分析高密度校验码迭代译码算法；探索如何寻找变量和约束不等式数量少的线性规划译码模型，消除低重量伪码字对线性规划译码的影响；利用组合数学工具设计性能与复杂度折中的中等密度校验码；研究高密度校验码迭代和线性规划译码的串行组合译码方案。通过本项目的研究，期望能够完善迭代和线性规划译码理论体系，为未来的存储和光通信系统提供高效实用的纠错编码方案。

结论摘要：

线性规划译码的研究隶属于差错控制编码与优化理论的交叉研究课题，旨在将优化理论中的概念及方法应用到差错控制编码的译码中，以提高译码性能并降低译码复杂度。因此，本项目的研究主要集中在两个方面(a) 提高线性分组码(LDPC码等)的线性规划译码性能；(b)降低线性规划译码的复杂度。所取得的主要研究成果概述如下 (1) 提出了线性分组码的一种新的校验节点分解方法，利用该方法能够有效降低线性规划译码的规模和复杂度； (2) 瞬子是一种线性规划译码器的输入结构，基于瞬子的输入能够导致译码器输出伪码字。提出了一种基于路径扩展的小重量瞬子的搜索算法，并利用搜索到的瞬子来设计LDPC码，降低错误平层； (3) 提出了两种方法来降低LDPC码错误平层。首先，提出了一种基于校验矩阵扩展的消除LDPC码陷阱集的校验矩阵构造方法；其次，结合LDPC码的构造和译码来同时降低LDPC码的错误平层； (4) 基于交替向量乘子法(ADMM)的LDPC码译码方法能有效降低线性规划译码复杂度。提出了一种更加快速的基于ADMM的线性规划译码算法，并针对非规则LDPC码提出一种加权1范数罚函数机制，能有效改善译码性能； (5) 提出了Davey-MacKay构造在IDS-AWGN信道下的迭代译码算法，并利用利用turbo均衡技术来改善译码性能。