线性分组码的构造及其译码算法

本项目主要研究具有高纠错性能的线性分组码的构造及其高效快速译码算法的设计问题。利用代数、图论以及组合数学等工具，提出具有较大围长的LDPC码的新的构造方法。根据平衡环的拓扑结构，通过确定包含平衡环的最小关联矩阵，给出确定全部较短的平衡环的简单方法。利用低阶置换矩阵进行多次扩张，消除LDPC码中的短环从而提高其围长。针对一类在不降低纠错性能的前提下可以大大降低译码算法的计算复杂度的整数规划问题，通过规划问题的分裂，研究在参考向量的个数等于4，5，6时的快速求解问题。给出参考向量的选择标准，进而应用于一些广泛使用的译码算法，降低其计算复杂度。针对Chase-型译码算法，设计算法来计算或估计达到指定误码率所需搜索中心的最小数目，并对达到限界距离译码所需搜索中心的最小数目进行估计，进而提出设计对码长和信噪比都具备较大适用范围的好的译码算法。

本项目研究计划已顺利完成，具体如下：.① 我们通过对因子图中平衡环的拓扑结构的研究，对平衡环进行了分类。通过确定包含平衡环的最小关联矩阵，得到了一个计算和发现全部较短的平衡环的算法。提出了采用多次低阶扩张的办法消除这些较短的平衡环的一个有效算法。.② 针对一类可用来对译码算法设置加速条件的整数规划问题（IPP），我们首先通过将其分裂成一些子规划问题来简化。当参考向量的个数为4时，可以把原IPP分裂成至多12个自变量个数减半的子规划问题。当参考向量的个数为5时，原IPP可分裂成至多81个自变量个数减半的子规划问题。关于这些子规划问题的求解，我们将各子规划问题的定义域适当划分成一些小区，然后在各小区中适当选取一个种子，采用逐步修改种子的生长方向的办法来找到各小区里的最优解。.③ 关于Chase型译码算法，我们给出了达到限界距离译码的一些条件。当搜索中心的非零分量全部集中在不可靠的位置时，我们通过确定未搜索区域内的最小向量，给出达到限界距离译码的搜索中心的最小数目的上界和下界，得到了目前最好的结果。