低密度奇偶校验码编码研究

《低密度奇偶校验码编码研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、低密度奇偶校验码的编码研究StudyonEncodingofLDPCcodes报告人：何善宝东南大学移动通信国家重点实验室2004年9月东南大学移动通信国家重点实验室第1页内容提纲第一部分：LDPC码的发展历史第二部分：LDPC码的编码介绍第三部分：随机化的构造方法第四部分：系统化的构造方法第五部分：稀疏序列构造方法第六部分：总结与展望东南大学移动通信国家重点实验室第2页一、LDPC码的发展历史1962年前后Gallager首先提出LDPC码[1,2]，并给出LDPC码的简单构造和硬判决概率译码；1981年Tan

2、ner建立了编码的图模型概念[6]，证明了和积算法在无环图中译码的最佳性并提出了构造适合和积译码的图模型的代数方法；1996年前后MacKay和Neal[12][3]，Spiser和Spielman[10]，Wiberg[11]重新发现了LDPC码的良好性能；1998年Davey和MacKay提出了基于GF(q)的LDPC码[4]；1998年Luby等人提出了基于非正则图的LDPC码[5];2001年专辑“基于图的码和迭代解码”,IEEETrans.onInform.Theory,vol.47,Feb.2001;200

3、4年文集“LDPC码构造等”，IEEETrans.onInform.Theory,vol.50,June2004.东南大学移动通信国家重点实验室第3页二、LDPC码的编码介绍LDPC码基础简介校验矩阵完全随机的编码方法校验矩阵具有循环和准循环结构的编码方法东南大学移动通信国家重点实验室第4页LDPC码基础简介LDPC码就是一种普通的线性分组码，可以用生成矩阵和校验矩阵来表征；LDPC码又是一种特殊的分组码，特殊性就在于它的奇偶校验矩阵中‘1’的数目远小于‘0’的数目，称为稀疏性，“低密度”也来源于此；LDPC码又称为

4、稀疏图码，它可以用一个二分图来表征，在图论中一个图是由顶点和边组成的，二分图：图中所有的顶点分为两个子集，任何一个子集内部各个顶点之间没有边相连，任意一个顶点都和一个不在同一个子集里的顶点相连；LDPC码的二分图又称为Tanner图，这是由Tanner在1982年首次用它来表示低密度码的，一个Tanner图和一个校验矩阵完全对应；东南大学移动通信国家重点实验室第5页线性分组码(6,3,3)为例的校验方程和其二分图x1x2x30x1x2x3x4x5x6x3x4x50xxx0561xxx02

5、46东南大学移动通信国家重点实验室第6页v1v2v3v4v5v6cccc1234这也是一个简单的(6,3,3)码字的二分图，上面是变量节点，下面为校验节点；圈：由变量节点、校验节点和边首尾相连组成的闭合环路，即文献中的cycle；Girth的定义：码字二分图或Tanner图中最短圈的圈长；图中粗线构成了一个长度为6的圈，如果没有长度为4的圈，那么这个图的最小圈长，即girth，就是6；给出一个码的校验矩阵后，可以用文献[19]中MaoYongyi提的搜索方法得到该LDPC码的girth及其分布。东南大学移动通信国家重点

6、实验室第7页为什么提到LDPC码的girth？答：因为目前LDPC码的最好的解码方法是Sum-Product算法或者BeliefPropagation(BP)算法，这种算法是一种渐进最大似然的算法，如果Tanner图中不存在圈，也就是girth是无穷大，则这种算法等效于最大似然算法；当然，在码长固定的情况下，对于适用的码字来说无圈是不可能的；但是通过增大最小圈的圈长，也就是增大girth，可以提高码字的性能，girth达到一定的值就可以接近无圈时的性能。显然决定码字性能的是码间距，但是我们无法去直接约束控制码间距；控制Tann

7、er图的girth虽然也有很大的难度，但却是可以通过一些方法消除长度较短的圈；一般来说，girth大的码字其码间距也大，但是码间距大的其girth不一定就很大。因此，girth是目前设计LDPC码最常用到的关键词之一。东南大学移动通信国家重点实验室第8页校验矩阵完全随机的LDPC码编码方法LDPC码所面临的一个主要问题是其较高的编码复杂度和编码时延。对其采用普通的编码方法，LDPC码具有二次方的编码复杂度，在码长较长时这是难以接受的，幸运的是校验矩阵稀疏性使得LDPC码的编码成为可能。T.J.Richardson和R.L.Urb

8、anke在文献[7]中给出了利用校验矩阵的稀疏性对校验矩阵进行一定的预处理后，在线性时间内编码的有效算法，初步解决了LDPC码的应用所面临的一个主要问题。东南大学移动通信国家重点实验室第9页基于高斯消去的直接编码LDPC码的直接编码方法就是利用高斯消去法，产生一