LDPC 码

简单介绍一下LDPC码的基本原理，先说一下编码。学过通信原理的人应该有些印象，我们通过构建一个生成矩阵G，就可以进行编码了，当然这里仅仅介绍理论部分，硬件部分暂不介绍，我还没有学习到。具体如何利用生成矩阵编码在一般意义上不是很复杂的事情（只能说一般意义上，后面会提到非课本内容的部分），简单的说就是生成矩阵G和信息码的相乘，结果即为编码过后的码字，包括信息码和校验码。这样的码字在信道上传输可靠性会增大，虽然校验码增加了码长，降低了信息传输速率，可增加了纠错检错的能力，更加有利于解码的正确率即信息的正确传输（具体内容参考信息论的理论）。就我目前看到的为止，LDPC码的编码的问题主要有两类，第一类是校验矩阵H的构建（H矩阵是与G矩阵对偶的一个矩阵，代表了校验特征，也就是LDPC），第二类是编码的实现。H矩阵的构建在LDCP码领域是一个重要的问题，H矩阵的好坏影响着编码解码的性能。H矩阵分为正则H矩阵和非正则H矩阵，Gallager提出LDPC码时构建的H矩阵就是一个正则H矩阵，而理论和事实都证明非正则的H矩阵具有更加优良的特性。构建H矩阵的方法在Gallager第一次提出LDPC码的时候就已经给出一种方法，这在他1963年的那篇文章中给出了，具体内容就不介绍了，有兴趣的同学可以参考刚才提到的那篇文章。接下来就到了1996年，Mac Key开始接管LDPC领域的研究。他提出了一种随机构建H矩阵的方法，有1A、2A、1B、2B四种不同的方面，其实核心是一样的，每种方法有些许改进。这两种方法用于构建正则H矩阵。而随着后来的研究者越来越多，各种方法也都涌现出来，基本都是基于代数方法，也有基于启发式搜索的，有Xiao Yu Hu的PEG方法，这是被认为构建中、短码长低密度校验码当前所知具有参数最好的码，而这句话是Mac Key说得。还有Bit filling法等一系列方法，都是构建H矩阵最为常见的方法，后两者可以构建非正则H矩阵。后面两种方法还没有时间学习，但是构建H矩阵的核心即是围绕避免短的围长和增加码间距离展开，而这两者也有一定关系。从构建低密度校验矩阵方面看来，正则H矩阵的构建已经有了一定理论，而如何构建非正则H矩阵目前还没有严格的理论基础，这是一个值得研究的方面。

       编码研究的另一个方面就是具体编码的实现。课本上的原理前面已经介绍过了，通过H矩阵经过高斯消去很容易得到生成矩阵G，然后就很容易编码。而看到的文章提到由H到G消除了低密度的优点，然后就有不同的编码方法提出，也就引出了不同的理论和硬件实现。这方面暂时还没有开始看，才刚开始看，接触的都是最基本的，以后也许会做这方面的研究，现在先搞清楚有这个方向可以研究这个概念，为以后作准备。

       信道传输略过，这不是我们考虑的问题。再开始介绍解码。Gallager那篇经典文章中提到了两种方法，一种是比特翻转法（Gallager硬判决法），另一种是基于最大后验概率的解码方法（Gallager软判决法）。课本上介绍的解码方法是通过校验矩阵进行解码的，收到的码字和校验矩阵作相乘，如果结果为零矩阵，则收到的是正确码字，反之则不正确，再利用相乘的结果进行分析，进行纠错检错。比特翻转法，和常规的方法类似，主要就是设立门限，某一码字错误超过门限即翻转一次，然后反复迭代，直到解码正确或者超过迭代次数。第二种方法是利用码字每一比特的条件概率计算出另一码字的条件概率，然后又计算出另一个码字的条件概率，通过反复迭代直到每一比特为1的概率趋近于0或者1则译码输出。而迭代期间码字的选择可以通过奇偶校验树进行寻找，具体方法这里又不介绍了，有兴趣还可以参考前面提到的文章。还有基于Turner图的消息传播算法，其中的一种BP（置信传播）算法经过证明和Gallager的软判决算法等价的，可考虑问题的方法是不同的，很多思想是能够借鉴的。这种方法也是最好的最常用的方法，基于后验概率的解码在信息论的很多领域都一样的。不过需要说明的是，这是在BSC无记忆信道下推导出来一些理论，在高斯白噪声信道下以及记忆信道的理论暂时还没有涉及，前者有资料还没看，后者还没看到资料，这都是后期的工作了，既然工作总结就不再说了。