《LDPC的BP译码算法》由会员分享，可在线阅读，更多相关《LDPC的BP译码算法（24页珍藏版）》请在金锄头文库上搜索。
1、 课程名称： 现代编码理论 任课教师： 王琳 洪少华 论文题目： LDPC码的BP译码算法 姓 名： 曹沙沙 赵卜寒 学 号： 23320131153243 23320131153274 2014 年 07月06日目录摘要IIAbstractIII第一章 LDPC码的概述11.1 LDPC码的发展史11.2、LDPC码的表示11.3 二进制LDPC码的编码方法31.3.1校验矩阵的生成31.3.2编码算法4第二章 LDPC码译码算法62.1 Gallager概率译码基本思路62.2 BP算法研究82.3 用对数似然比表示的BP算法11第三章 LDPC的性能分析143.1 LDPC的仿真模型14
2、3.2 LDPC的译码性能153.2.1码长对性能的影响153.2.2迭代次数对译码性能的影响16结论18参考文献19 摘要低密度奇偶校验码是Gallager提出的一种线性分组码，其性能可以非常接近香农极限。它是根据低密度稀疏校验矩阵H和二分图来构造的，本文详细的阐述了二进制，规则的LDPC的BP译码算法，其校验矩阵每一行和每一列的1的个数是相同的，分别为p和q,其Tanner图中比特节点的度和校验节点的度分别对应着一个固定值，通常用（m，n，p，q）表示。BP译码算法是一种迭代的概率译码算法，本文着重于BP译码算法及其简化运算。本论文主要介绍了LDPC码的构造、编码和译码基本原理。阐述了LD
3、PC编译码的过程，并通过MATLAB仿真工具对LDPC码在AWGN信道的误比特率性能进行了仿真，分析了信噪比、码长和迭代次数对误比特率性能的影响。关键词：二进制LDPC BP算法 迭代概率译码 后验概率LDPC码的BP译码算法AbstractLow Density Parity Check(LDPC) codes are a class of linear block codesproposed by Gallager,which perform at a rate extremely closed to the Shannon capacity.It is based on low-dens
4、ity parity check matrix H and sparse bipartite graph is constructed, the paper elaborated binary, LDPC decoding algorithm of BP rule, the number of one of its check matrix each row and each column is the same , respectively, p and q, the Tanner graph of bit nodes and check nodes of degree correspond
5、s to a fixed value, respectively, usually expressed as (m, n, p, q). BP decoding algorithm is the probability of an iterative decoding algorithm, This paper focuses on its simplified operation. This paper describes the structure, the basic principles of the encoding and decoding of LDPC codes. Descr
6、ibes the LDPC encoding and decoding process, and through MATLAB simulation tool for LDPC codes in the bit error rate performance AWGN channel simulation, analysis of the impact of signal to noise ratio, code length and number of iterations of the bit error rate performance.Keywords: binary LDPC BP-d
7、ecoding algorithm iterative probability posterior probabilityLDPC码的BP译码算法第一章 LDPC码的概述1.1 LDPC码的发展史1、 1963年，Gallager发现的LDPC码被称作古典码型：规则LDPC。2、 1998年，MacKay and Spielman发明了不规则的LDPC。3、 Richardson and Urbanke开创了用译码分析设计码型的方法。4、针对B-LDPC码优异的纠错性能，M. Davey和D. Mackay进一步将B-LDPC码一般化到多进制域上，并且研究结果表明Q-LDPC码在低码率（R1/
8、2），AWGN信道下比B-LDPC码的纠错性能还要优越，Q-LDPC码的出现为LDPC码的研究开拓了一个全新的领域。1.2、LDPC码的表示LDPC是一种分组码，但是LDPC码与其他线性分组码不同的是，其他线性分组码由生成矩阵表征，而LDPC码是由校验矩阵来表征，其奇偶校验矩阵具有低密度的1。规则LDPC码可以用（n,j,k）的形式表示，其中n表示生成的码字的码长，j表示H矩阵的列重，k为行重。也可将j用表示，k用表示。如果用m表示H矩阵中的行数则有。一个规则的（12，3，4）LDPC码的H矩阵如下图所示： 图11 （12，3，4）LDPC的校验矩阵我们把H矩阵中的每一行看作一个校验点(che
9、ck node)，每一列看作一个变量点(variable node)。则H矩阵反映了变量点与校验点的连接关系，如在第一行中有，表示模2加，表示第一个校验点约束、这四个变量点。从而我们可以知道行重k表示一个校验点约束k个变量点。我们再来看第一列，它表示了第一个变量点受到check2、check5、check7的约束。因此我们又可以推出列重j表示了一个变量点受到j个校验点的约束。由于LDPC也是一种线性分组码，因此可以用（n,k）的形式表示。n表示码长，k表示信息位的个数。为了更形象的表示LDPC码中变量点与校验点的关系，九十年代中期科学家们引入双边图（biparttie graphs）来表示LD
10、PC码。双边图是LDPC的一个有用的工具。它将节点分成两类，节点之间用无向的边进行连接，并且连接只存在于不同类的节点之间即只存在与校验点与变量点之间，而两个校验点之间或者两个变量点之间不存在边的连接。我们把LDPC校验矩阵H的每一行表示一个校验点用方框表示，每一列表示一个变量点用圆表示。则由上述可知一个校验点连接k个变量点，一个变量点连接j个校验点。当对应H矩阵中时，第i个变量点就与第j个校验点连接，否则不连接。并且校验点发出的边的总数等于变量点发出的边的总数。每个节点发出的边的个数称为这个点的度。如对于（12，3，4）码其双边图为：图12 （12，3，4）LDPC码的因子图表示当H矩阵中每列
11、1的个数与（或）每行1的个数不同时称为不规则LDPC码。在双边图中表现为变量点与校验点的度允许改变。对于不规则LDPC码，它更喜欢具有高密度的变量点，因为它将从校验点接收更多的信息量，从而能更精确的判断变量点的值。另外，不规则LDPC码喜欢具有低密度的校验点，在这种情况下，校验点所传送的信息对于相邻点而言更有价值。从上分析可知不规则LDPC码比规则LDPC的性能更好的原因在于不规则LDPC码中存在波浪效应。高密度的变量点能够快速的收敛到正确的值，并且它能够帮助中等的变量点收敛到他们正确的值，从而由于循环可以帮助低密度的变量点。最终使得所有点的译码速度加快。由于不规则LDPC码中行重和列重都不是
12、规则的，因此就不能用（n,j,k）的形式表示。因此不规则LDPC中采用度的表示方法。 ， （1.1）其中表示变量点的度的分布，表示校验方程点的度的分布；()表示从度为()的变量点（校验方程点）所发出的边数占总边数的比例。很显然。 对于规则的LDPC码，也可以用这样的方式进行表示。例如，对于规则的LDPC码(n,3,6)，则，。已知一个度的分布对（）后，可以确定一系列码字集合，其中校验方程个数以及码率如下式所示： （1.2） （1.3）1.3 二进制LDPC码的编码方法对于二进制LDPC码的编码，其编码基本步骤为：（1）、按照一定的设置生成校验矩阵H。（2）、由校验矩阵H，按照一定的编码算法生成
13、最后的码字u。1.3.1校验矩阵的生成由于LDPC码是以校验矩阵H为特征的，不同的校验矩阵H对应不同的码字集合。因此，LDPC码的编码首先需要设计校验矩阵H，同时这也是LDPC码编码的关键。在H矩阵的设计过程中，必须避免两种情况，一是出现短周期的环主要是长为四的环，二是避免变量点的连接过于集中，即校验点的度过大。长为4的环(图中存在长度为4的圈)会导致信息在两组点间反复传递，难以更新，违背了迭代译码的初衷。长为4的环反映在H矩阵中是存在22的子矩阵。当变量点所连接的校验方程过于集中时，常常导致LDPC码错误地板的发生。例如在图23中，变量点的度为3，但其中三个带阴影的变量点总共只连接了5个校验
14、方程；除了最右边的一个校验方程以外，其它4个校验方程中，每个都连接了两个阴影的变量点。因此，如果这三个阴影的变量点都出错时，左边4个校验方程都不能检测到错误的存在。当分组长度增大时，出现这种拓扑结构的可能性也随之减少。图23 变量点所连接校验方程过于集中的因子图下面以准规则LDPC码的H矩阵的生成为例说明校验矩阵的生成步骤。校验矩阵的生成步骤如下：（1）、选择参数（码长，码率，列重，行重）。（2）、构造一个全0矩阵。（3）、随机选择Wc行加入非0元素。在实际的仿真中采用的是准规则的H矩阵，既列重相同，行重尽量相同。因此，先在每列选择Wc行，随机的插入非0元素。接着再对于低重的行添加非0元素，以
15、避免出现低重的码字。（4）、对已生成的H矩阵进行消4环。1.3.2编码算法按照上小节的方法求出校验矩阵H后，就可以按照一定的编码方法得到最后生成的码字。常规的编码方法中，当H矩阵被构造出来后，可以得到生成矩阵G，则最后生成的码字U=SG。但是实际的编码过程并不像其表达式这么简单。我们来看一个例子：一个（10000，5000）线性分组码，其GI|P矩阵为500010000，假设P矩阵中1的密度为0.5，则在P矩阵中将有的1，即有次加法运算。从而所需的寄存器的数目将是很多的。因此我们在编程的过程中采用的是具有系统形式的H矩阵的快速编码。假设生成的码字具有系统形式U=C|S，其中C为校验位，S表示信息位。则我们将校验矩阵H变换成A|B的形式，其中A为mm的单位矩阵，B为（n-m
