多进制LDPC码的线性规划译码方法研究

Linear programming (LP) decoding is a hot research topic in the area of error-control coding and may become a competitive alternative of the traditional iterative decoding algorithms for linear codes. This project focuses on this hot topic and investigates the LP decoding of non-binary low-density parity-check (LDPC) codes constructed from the finite field GF(2^m). .In order to address the complexity and storage requirement issue of LP decoding of non-binary LDPC codes, a low-complexity and low-storage-requirement LP decoding algorithm without performance losses is to be proposed based on the theories of linear programming. .Compared with traditional iterative decoding, the performance of LP decoding is described by pseudocodewords, which makes it easier to theoretically analyze LP decoding. In this project, the properties of pseudocodewords of non-binary LDPC codes will be studied and the theoretical results of LP decoding performance will be obtained. In particular, the distributions of low-weight (minimal) pseudocodewords of some classes of algebraically-structured LDPC codes will be completely determined. Besides, the improved LP decoding algorithm will be developed in the project. The proposed algorithm will improve the decoding performance with a slight increase in computational complexity when the original LP decoder converges to a pseudocodeword that is not a codeword.

线性码的线性规划译码(LP decoding)方法是目前差错控制编码领域的研究热点，并且将成为传统的迭代译码算法的有力竞争者。本项目将瞄准这一热点，创新性地研究基于有限域GF(2^m)构造的多进制低密度奇偶校验(LDPC)码的线性规划译码。.针对多进制LDPC码线性规划译码复杂度高和存储量大的问题，拟利用线性规划理论，在不损失译码性能的前提下，创造性地提出一种低复杂度和存储量的线性规划译码方法。.相对于传统的迭代译码，LP译码的性能能够用伪码字刻画，使得LP译码易于理论分析。本项目拟对多进制LDPC码的伪码字性质进行研究，从而得到LP译码性能的理论分析结果。特别地，对于几类具有代数结构的LDPC码，拟确定其低重量的(最小)伪码字的重量分布。此外，本项目拟提出改进的LP译码算法，当标准LP译码收敛到非码字的伪码字时，增加少量复杂度，获得性能改善。

本项目对差错控制编码领域的研究热点——多进制低密度奇偶校验(LDPC)码的线性规划(LP)译码及其相关问题进行了深入研究。. 相对于传统的迭代译码，LP译码具有复杂度高和存储量大的缺点。为了克服这一问题，利用线性规划理论，提出了一种多进制LDPC码的降低复杂度和存储量的LP译码方法，其性能相对标准LP译码没有任何损失。. 线性规划译码的性能可以用伪码字进行刻画。利用线性规划理论，提出了LDPC码的改进LP译码算法，当标准LP译码收敛到非整数伪码字时，缩小标准LP译码问题的可行域，进行二次寻优，从而获得性能改善。. 研究了LDPC码的伪码字和码字分布。对于几类代数构造的多进制LDPC码，分别给出了其最小码字重量的上界和下界。此外，对于两类重要的具有代数结构的LDPC码——阵列LDPC码和RS-LDPC码的最小重量码字和伪码字结构进行了深入研究。