LDPC的BP译码算法要点.doc

课程名称： 现代编码理论
任课教师： 王琳 洪少华
论文题目： LDPC码的BP译码算法
姓 名： 曹沙沙 赵卜寒
学 号： 23320131153243 23320131153274

2014 年 07月06日

目录
摘要 II
Abstract III
第一章 LDPC码的概述 1
11 LDPC码的发展史 1
1.2、LDPC码的表示 1
1.3 二进制LDPC码的编码方法 3
1.3.1校验矩阵的生成 3
1.3.2编码算法 4
第二章 LDPC码译码算法 6
2.1 Gallager概率译码基本思路 6
2.2 BP算法研究 8
2.3 用对数似然比表示的BP算法 11
第三章 LDPC的性能分析 14
3.1 LDPC的仿真模型 14
3.2 LDPC的译码性能 15
3.2.1码长对性能的影响 15
3.2.2迭代次数对译码性能的影响 16
结论 18
参考文献 19

摘要
低密度奇偶校验码是Gallager提出的一种线性分组码，其性能可以非常接近香农极限。它是根据低密度稀疏校验矩阵H和二分图来构造的，本文详细的阐述了二进制，规则的LDPC的BP译码算法，其校验矩阵每一行和每一列的1的个数是相同的，分别为p和q,其Tanner图中比特节点的度和校验节点的度分别对应着一个固定值，通常用（m，n，p，q）表示。BP译码算法是一种迭代的概率译码算法，本文着重于BP译码算法及其简化运算。
本论文主要介绍了LDPC码的构造、编码和译码基本原理。阐述了LDPC编译码的过程，并通过MATLAB仿真工具对LDPC码在AWGN信道的误比特率性能进行了仿真，分析了信噪比、码长和迭代次数对误比特率性能的影响。

关键词：二进制LDPC BP算法 迭代概率译码 后验概率

LDPC码的BP译码算法

Abstract
Low 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-density 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 corresponds 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. Describes 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-decoding algorithm iterative probability posterior probability

LDPC码的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码一般化到多进制域上，并且研究结果表明QLDPC码在低码率（R<1/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矩阵如下图所示：

图1－1 （12，3，4）LDPC的校验矩阵
我们把H矩阵中的每一行看作一个校验点(check node)，每一列看作一个变量点(variable node)。则H矩阵反映了变量点与校验点的连接关系，如在第一行中有，表示模2加，表示第一个校验点约束、、、这四个变量点。从而我们可以知道行重k表示一个校验点约束k个变量点。我们再来看第一列，它表示了第一个变量点受到check2、check5、check7的约束。因此我们又可以推出列重j表示了一个变量点受到j个校验点的约束。
由于LDPC也是一种线性分组码，因此可以用（n,k）的形式表示。n表示码长，k表示信息位的个数。为了更形象的表示LDPC码中变量点与校验点的关系，九十年代中期科学家们引入双边图（biparttie graphs）来表示LDPC码。双边图是LDPC的一个有用的工具。它将节点分成两类，节点之间用无向的边进行连接，并且连接只存在于不同类的节点之间即只存在与校验点与变量点之间，而两个校验点之间或者两个变量点之间不存在边的连接。我们把LDPC校验矩阵H的每一行表示一个校验点用方框表示，每一列表示一个变量点用圆表示。则由上述可知一个校验点连接k个变量点，一个变量点连接j个校验点。当对应H矩阵中时，第i个变量点就与第j个校验点连接，否则不连接。并且校验点发出的边的总数等于变量点发出的边的总数。每个节点发出的边的个数称为这个点的度。如对于（12，3，4）码其双边图为：

图1－2 （12，3，4）LDPC码的因子图表示
当H矩阵中每列1的个数与（或）每行1的个数不同时称为不规则LDPC码。在双边图中表现为变量点与校验点的度允许改变。对于不规则LDPC码，它更喜欢具有高密度的变量点，因为它将从校验点接收更多的信息量，从而能更精确的判断变量点的值。另外，不规则LDPC码喜欢具有低密度的校验点，在这种情况下，校验点所传送的信息对于相邻点而言更有价值。从上分析可知不规则LDPC码比规则LDPC的性能更好的原因在于不规则LDPC码中存在波浪效应。高密度的变量点能够快速的收敛到正确的值，并且它能够帮助中等的变量点收敛到他们正确的值，从而由于循环可以帮助低密度的变量点。最终使得所有点的译码速度加快。由于不规则LDPC码中行重和列重都不是规则的，因此就不能用（n,j,k）的形式表示。因此不规则LDPC中采用度的表示方法。
， （1.1）
其中表示变量点的度的分布，表示校验方程点的度的分布；()表示从度为()的变量点（校验方程点）所发出的边数占总边数的比例。很显然。
对于规则的LDPC码，也可以用这样的方式进行表示。例如，对于规则的LDPC码(n,3,6)，则＝，＝。已知一个度的分布对（）后，可以确定一系列码字集合，其中校验方程个数以及码率如下式所示：
（12）
（1.3）
1.3 二进制LDPC码的编码方法
对于二进制LDPC码的编码，其编码基本步骤为：
（1）、按照一定的设置生成校验矩阵H。
（2）、由校验矩阵H，按照一定的编码算法生成最后的码字u。
1.3.1校验矩阵的生成
由于LDPC码是以校验矩阵H为特征的，不同的校验矩阵H对应不同的码字集合。因此，LDPC码的编码首先需要设计校验矩阵H，同时这也是LDPC码编码的关键。
在H矩阵的设计过程中，必须避免两种情况，一是出现短周期的环主要是长为四的环，二是避免变量点的连接过于集中，即校验点的度过大。
长为4的环(图中存在长度为4的圈)会导致信息在两组点间反复传递，难以更新，违背了迭代译码的初衷。长为4的环反映在H矩阵中是存在2×2的子矩阵。
当变量点所连接的校验方程过于集中时，常常导致LDPC码错误地板的发生。例如在图2－3中，变量点的度为3，但其中三个带阴影的变量点总共只连接了5个校验方程；除了最右边的一个校验方程以外，其它4个校验方程中，每个都连接了两个阴影的变量点。因此，如果这三个阴影的变量点都出错时，左边4个校验方程都不能检测到错误的存在。当分组长度增大时，出现这种拓扑结构的可能性也随之减少。

图2－3 变量点所连接校验方程过于集中的因子图
下面以准规则LDPC码的H矩阵的生成为例说明校验矩阵的生成步骤。
校验矩阵的生成步骤如下：
（1）、选择参数（码长，码率，列重，行重）。
（2）、构造一个全0矩阵。
（3）、随机选择Wc行加入非0元素。在实际的仿真中采用的是准规则的H矩阵，既列重相同，行重尽量相同。因此，先在每列选择Wc行，随机的插入非0元素。接着再对于低重的行添加非0元素，以避免出现低重的码字。
（4）、对已生成的H矩阵进行消4环。
1.3.2编码算法
按照上小节的方法求出校验矩阵H后，就可以按照一定的编码方法得到最后生成的码字。
常规的编码方法中，当H矩阵被构造出来后，可以得到生成矩阵G，则最后生成的码字U=S×G。但是实际的编码过程并不像其表达式这么简单。我们来看一个例子：一个10000，5000）线性分组码，其G＝[I|P]矩阵为5000×10000，假设P矩阵中1的密度为0.5，则在P矩阵中将有的1，即有次加法运算。从而所需的寄存器的数目将是很多的。
因此我们在编程的过程中采用的是具有系统形式的H矩阵的快速编码。假设生成的码字具有系统形式U=[C|S]，其中C为校验位，S表示信息位。则我们将校验矩阵H变换成[A|B]的形式，其中A为m×m的单位矩阵，B为（n-m）×m的矩阵，则根据,可得AC+BS=0,从而可以得到。在实验中，是把随机生成的校验矩阵经过列变换成系统形式，然后根据H与G的关系，求出生成矩阵G的前面部分，生成矩阵的后面是一个（n-m）×（n-m）的单位矩阵，从而得到校验位C。由于A是单位阵，从而降低了计算量。
这种方法降低了编码过程的运算量但是同时也降低了其性能。它要求H具有系统形式，就存在一个m×m的单位矩阵，使得剩余部分具有高密度的1。这就使矩阵的稀疏特性被破坏。但是其生成矩阵H较容易。编码时间与分组长度呈线性关系。
除了上述的两种方法外，中外学者还研究出了其他更适合硬件实现的编码算法。主要集中于H矩阵的设计上，如具有类似下三角的H矩阵的设计，具有线性的编码复杂度，节省了对寄存器的要求，易于硬件的实现。

19

第二章 LDPC码译码算法
信道编码的译码算法是决定编码性能和应用前景的一个重要因素，尤其是在长码的条件下，译码算法的复杂度决定了编码的前途。通常分组码的译码长度与码长成指数关系，码长增加到一定的程度后，复杂度的增加将是不可控制的，无法得到实际的应用。LDPC码则不同，由于其奇偶校验矩阵的稀疏性，使它存在高效的译码算法，其译码复杂度与码长成线性关系，克服了分组码在码长比较长时面临的巨大译码计算复杂度问题。
Gallager提出LDPC码时曾给出两种译码算法：硬判决算法和概率译码软判决算法。硬判决不能达到LDPC码的最佳性能，软判决则有非常好的性能。BP算法是在Gallager提出的概率译码算法的基础上发展起来的。
2.1 Gallager概率译码基本思路
假设发送端发送一个码长为n的二进制序列（）,接收端收到的信号为（），如果发送的二进制比特是相互独立的，则可以根据接收信号和信道模型估计出发送的各比特位0或1的概率。考虑其中的某一比特，如果，则就认为发送的为1，否则为0。这是对应于没有信道编码的情况下。如果经过了信道编码，此时的二进制序列各比特之间就不是相互独立的。假设这个二进制序列是一个LDPC码字，那么这n个比特就要满足由该码的校验矩阵所确定的一系列校验方程。假设其中一个校验方程是（模2加法），此时=1的概率，除了接收信号提供的信息外，还要考虑比特间的相关性。
假定，，，满足校验方程这一事件记为S，现要计算概率。根据条件概率的贝叶斯公式：

当然包含比特的校验方程可能不止一个，这些校验方程的某些比特又包含在其他更多的校验方程中。由于码字中的各比特的相关性，除了利用对于该比特的接收信号外，还可以利用其他比特的接收信号来修正该比特的后验概率。
为了直观的表示这种关系，引入校验集合树的概念。如下图所示

　　　　　　　　　　　　　　　图2-1　校验集合树
具体算法Gallager的论文中已有详细的阐述，这里我们只对结果做下说明。
通过校验集合树，在传送码字c时，码字中的各比特满足包含比特d的j个校验方程。当接收到相应的符号序列时y时，比特d为1的条件概率可以表示为。同理，比特d为0 的条件概率表示为。令当不考虑发送比特间的相关性时，d为1的概率表示为，它与信道模型有关。有下面公式：
令，表示d的校验集合树第一层中包含d的第i个校验方程的第l个比特位1 的概率，那么有：
(2.1)
则概率译码的步骤可以描述如下：对每一个比特，画出相应的校验集合树，从最高层的节点开始，应用上式逐层计算出各节点的后验概率分布，直至求出根节点的后验概率分布。根据后验概率分布判决该比特是0或者1：

若
其它
综上可见，概率译码的算法的运算量是相当大的，因为没计算一个比特的后验概率分布，都需要利用所有比特的相关信息，运算量随码数的增加呈指数增长。
2.2 BP算法研究
校验集合树虽然在描述计算单个节点的后验概率时非常直观，但针对不同的节点有不同的校验集合树，因此在描述并行的计算整个码字各比特的后验概率时，使用校验集合树并不方便，我们这里采用Tanner图来对应前面提过的校验集合树。为了方便该图只画出了部分节点和校验节点。Tanner图的变量节点对应于校验集合树的节点，校验节点对应于校验集合树的边。

　　　　　　　　　　图2-2 校验集合树的部分Ｔanner图
设表示校验节点相连的所有变量节点的集合，即，表示集合去掉变量节点。设表示与变量节点相连的所有校验节点的集合，即，表示集合中去掉校验节点。

图 2-3 Tanner图中关于变量节点和校验节点的局部关系
图中表示不考虑比特间的相关性，仅仅根据比特的接收信号值以及信道特性而得出的比特取值为x的概率，其中。显然有。可以把看成变量节点的固有性质。
设表示基于接收信号并根据校验节点集合的信息而得出的比特的概率，其中。同样有。可以认为是变量节点向校验节点传递的信息。
表示当比特，并给定其他比特的一组概率时，校验节点m对应的校验方程成立的概率。可以看做校验节点向变量节点传递的信息。
根据和的定义，考虑到校验方程都是模2加法，校验节点m对应的校验方程成立的概率即为比特序列中包含偶数个1的概率；校验节点m对应的校验方程成立的概率即为比特序列中包含奇数个1 的概率。在进行简易的推导易得

（2.2））
（2.3）
根据式(2.1)以及，，以及的定义，可以得到
（2.4）

完整的BP算法描述。对满足的m,l执行如下步骤。
（1）初始化：
,,其中表示信道的先验概率。
（2）校验节点更新： ，则有
（2.5）
（2.6）
（2.7）（3）变量节点更新：

（2.8）
（2.9）
其中是一个使得的值。
（4）似后验概率更新：

（2.10）
（2.11）
同样是一个使得的值。
（5） 比特判决：如果，则判,(l=1,2,......,N).
若，或者迭代次数达到最大迭代次数，则结束迭代，把作为译码输出，否则转到步骤（2）继续迭代。
2.3 用对数似然比表示的BP算法
上述介绍的BP算法比较复杂。一方面该算法需要在每个变量节点和校验节点分别计算各比特为0或者为1 的概率，并且在计算和时，要选择合适的系数和使之满足概率和为1 的条件；另一方面，算法的表述太过复杂，采用很多相乘运算，耗费较多的运算时间和硬件资源，不利于硬件实现。采用对数似然比描述的BP算法会有一个非常简单明了的形式。
考虑一个随机变量x，它的对数似然比L(x)定义为

根据对数似然比的定义，令

那么根据式（2.2）和（2.3）得

因为反曲正切函数在开区间（-1.1）内单调增加，是关于原点对称的奇函数。这样上式变为简洁形式：

因为 ，上式右端各项除以 ，右端各项分母再除以 ，可得下式：

再引用的定义得下式：
这里为了使形式更简洁，引用双曲正切函数：，它是在内单调增加，函数值，以y=+1,-1为渐近线，关于原点对称的奇函数。最后得到：
（2.12）
根据式（1.8）和（1.9）有
（2.13）
同理有：
（2.14）
BP算法的步骤整理如下：对于校验矩阵元素的m,l执行如下步骤运算。
(1) 初始化：
(2) 校验节点更新：
(3) 变量节点更新：
(4) 似后验概率更新
(5) 比特判决：如果，则判；否则判，（l=1,2,....,N）。
若，或者迭代次数达到最大迭代次数，则结束迭代，把作为译码输出，否则转到步骤（2）继续迭代。
上述是完整的的ＬＤＰＣ码译码的BP算法，但还没有说明如何去求得在译码的初始化过程中所需要的或，这些值是与信道有关的。下面以ＡＷＧＮ信道为例，说明如何计算或的值。表示不考虑比特之间的相关性，仅根据比特的接收信号值以及信道特性而得出的比特取值为ｘ的概率，其中ｘ的取值为０或１。
假设ＡＷＧＮ信道是二进制无记忆对称信道，其输入是来自信源的二进制０、１数字信号，经发端的二相ＢＰＳＫ调制器后变为１，－１对极信号。经收端的二相相干解调器又把１，－１对极信号变为０，１数字信号还原输出。由于ＡＷＧＮ高斯白噪声的存在，相干解调的检测可能出现错误。用信号加噪以后的条件概率密度分布函数来分析误码的产生比较清楚。

第三章 LDPC的性能分析
3.1 LDPC的仿真模型

图3-1 LDPC仿真模型图
其中第二章详细介绍了LDPC码的译码算法，可知LDPC译码一般包括以下5个步骤：1、初始化2、校验节点更新3、变量节点更新4、判决5、停止。实际操作时发现判决时只需用到本轮迭代的校验节点的更新结果，变量节点的更新在下一轮迭代中才起作用。因此可以把步骤4和5安排在步骤3之前进行，这样可以节省一次变量节点的更新工作，译码流程图如下：

图3-2译码流程图
3.2 LDPC的译码性能
通过前面几章的介绍，LDPC的译码基本完成，为了了解实现的译码性能，下文中给出了LDPC的译码性能图。LDPC编译码实现的编码输入是函数rand()产生的二进制随机序列，并记录LDPC译码在不同性噪比下的误码率，再在matlab中画图。
仿真时LDPC码列重选择3，最大迭代次数设置为5次时进行仿验，分析研信噪比对LDPC码误码性能的影响，随着信噪比的增加，LDPC码的性能不断提高。BP译码算法下，可以看成是无穷比特量化译码，它充分利用接收的信道信息，信道信息利用率得到了极大的提高。信道信息的充分利用，极大地提高了译码性能，使得译码可以迭代进行充分挖掘接收的信道信息，最终获得出色误码性能

图3-3 BP算法的BER曲线
3.2.1码长对性能的影响
将LDPC码列重选择3，最大迭代次数设置为5次且信噪比为0.5dB时进行仿真实验，分析研究码长对LDPC码误码性能的影响，仿真得到了不同码长对LDPC码的性能仿真结果如下图所示。从图中可以看出，在同样的信噪比条件下，随着码长的增加，LDPC码的性能不断提高。在小信噪比区域，码长的增加对误码率的改进不大，但随着信噪比的增大，LDPC码的误码率得到了明显改善。但随着码长的增加，LDPC码性能的提高是相对的，当达到一定码长后，性能将会有很小的提高。这是因为一定码长下编码性能有一定的极限，随着码长的增大，编码和译码的复杂度也增加，编码性能就会更接近极限，性能随码长增加改善的就更少。

图3-4码长对LDPC性能的影响
3.2.2迭代次数对译码性能的影响
将码长为400的LDPC码，列重为3，信噪比为0dB的情况下进行了仿真实验。图中给出了上述情况下的不同迭代次数对LDPC码的性能仿真结果。可以看出，在相同的信噪比下，LDPC码的性能随着迭代次数的增加而逐渐提高。但是LDPC码的误码率并不能随着迭代次数的增加无限地减小，当迭代次数足够大的时候，再增加LDPC码的迭代次数，只能增加系统的时延和复杂度，而LDPC码的性能不会再有提高。

图3-5迭代次数对性能的影响

结论
LDPC码是迄今为止发现的最接近香农限的信道编码之一，在现代通信和数据传输系统中拥有广阔的应用前景。本文主要介绍了LDPC的基础知识包括构造、编码、译码。着重介绍了LDPC码的高斯消去法编码原理和概率译码算法，并在AWGH信道下对其进行了性能仿真，比较了LDPC码相对于Turbo码的优越性能。
作为一种优秀的码型，LDPC码只有在实际中得到应用才能体现其真正的价值，纠错编码技术在通信系统中起着关键的作用，为可靠性信息传输提供保障，这一技术不管在移动通信还是卫星通信抑或是磁盘存储中都得到了广泛的应用。

参考文献
[1] 王新梅，肖圉镇．纠错码一原理与方法．西安：西安屯子科技大学出版社，1991．
[2] 樊昌信，张甫翊，徐炳祥，吴成柯．“通信原理”(第五版)【M】．国防工业出版社，2001．
[3] 王育民，粱传甲．“信息与编码理论．西北电讯工程学院，1986．
[4] R.G．Gallager,Low-Density Parity-Check Codes【D】．Cambridge，MA：Mrr Press，1963．
[5] R.G．Gallager,Low-Dcmity Parity-Check Code．IRE Transactions on Information Theory,1962．8(1)：21-28．
[6] 王单.LDPC码编译码算法研究[D].西安:西安电子科技大学,2006:14~32
[7] 刘利军.LDPC译码算法研究[D].广州:华南理工大学,2011,52-55 
[8] Richardson T.J.Design of Capacity Approaching Irregular Low-Density Parity-Check Codes[J].IEETranson Inform Theory,2001,47(2):619-637．
[9]Mackay D.J.C,HeskethC.P. Performanceof Low Density Parity Check Codes as a Function of Actual and Assumed Noise Levels [J].Electr.Notes Throty Compute rScience,2002:74