《无线通信报告LDPC码的线性规划译码算法.doc》由会员分享，可在线阅读，更多相关《无线通信报告LDPC码的线性规划译码算法.doc（11页珍藏版）》请在三一办公上搜索。
1、组合最优化课程论文论文题目：LDPC码的线性规划 译码算法 班 级： 13级电子A班 姓 名： 周珍珠 学 号： 13212895任课老师： 娄定俊 一 背景低密度奇偶校验（Low Density Parity Check, LDPC）码一类具有稀疏校验矩阵的线性分组码，也是一种性能非常接近Shannon极限的信道编码方案，具有很强的纠错抗干扰能力。LDPC码的线性规划（Linear Programming，LP）译码算法是将最大似然译码松驰成线性规划问题，译码码字具有最大似然特性。对于LDPC码，线性规划问题中的约束式的数量是随着校验节点度数的增加而呈指数增加，因此研究大规模的线性规划问题的
2、求解问题具有重要的意义。本文对LDPC码的最大似然(Maximum Likehood, ML)译码进行近似求解，建立了二进制分组码的松弛规划译码模型，从而提出了LP译码算法。作为ML译码的估计，理论证明该算法具有最大似然保持特性，也就是，一旦最优解为整数解，那么该解一定为最大似然码字。同时，当Tanner图中存在环时，可以通过添加限制条件，改进LP译码的性能。所以，LP译码可以避免短环对译码性能的影响，提高性能，在误码性能与复杂上的保持平衡。特别是对中短码长的LDPC码，利用线性规划译码算法性能更突出。二 LDPC码简介（一）LDPC码的H矩阵表示法LDPC码是一种线性分组码，它是把长度为k的
3、信息序列作为一个分组，然后按照一定规则将该信息序列映射为码长为n的码字，可表示为(n,k)线性分组码。对于LDPC码，可以由它的校验矩阵H确定。LDPC码的校验矩阵是m行n列的，一般 LDPC码的码字c就是与其对应的校验矩阵H的零空间，满足如下方程：cHT=0(2.1)图2-1 n=10的二进制LDPC码校验矩阵图-1显示的是一个码长为10的LDPC码校验矩阵。对于LDPC码的码率的计算则为:Rk/n=(n-m)/n (2.2)当且仅当校验矩阵H满秩的时候，等号成立。对于线性分组通常给出的是k行n列的生成矩阵G，生成矩阵G和校验矩阵H存在着正交的关系，即GHT=0或HGT=0。对于长度为k的信
4、息序列u就可以使用生成矩阵G生成长度为n的码字c，用公式表示如下：c=uG(2.3)而对于LDPC码，我们首先得到是它的校验矩阵H，要想完成编码过程必须得进行一些矩阵变换从校验矩阵H得到生成矩阵G，通常所用的方法为高斯消元法，现将校验矩阵H进行格式变化：H=Hp-1H=Imm PTmk(2.4)Hp-1是一个mm维的变换矩阵，假设不存在矩阵Hp，则表明H矩阵非满秩，这时我们只需保留矩阵中最大数目的线性相关行即可得到H矩阵，继而得到生成矩阵G：G=Pkm Ikk (2.5)（二）LDPC码的Tanner图表示LDPC码除了可以使用校验矩阵H进行表示之外，还可以用双向图模型进行表示,而且Tanne
5、r图与校验矩阵是一一对应的。Tanner图包含三类元素：变量节点(variable node)、校验节点(check node)和连接变量节点与校验节点的边(edge). 在Tanner图中，还有一个环(cycle)的概念：从某个节点出发经过一定的路径又回到了该节点，除了此节点外，其余节点均只出现一次。在这个过程中经过的边数被称为环长，最短的环的环长又被称为围长(girth)。图2-2 校验矩阵H和对应的Tanner图图2-2展现了一个校验矩阵和所对应的Tanner图。从图2-2可以看到，校验节点的度数为3，变量节点的度数为2，虚线所示的就是Tanner图中的一个环，由六条边组成，故环长为6。
6、注意到，因子图和校验矩阵的形式是一一对应的，对于一个给定的码，其可能的校验矩阵有很多个，相应地，可能的因子图也有很多个。很多译码算法都依赖于因子图的结构特性，采用这些译码算法时，因子图的多样性就显得尤为重要。三 LDPC码的译码LDPC码的译码算法可分为硬判决译码算法和软判决译码算法。硬判决算法操作简单，易于硬件实现，但是性能较差;软判决算法性能较好，但实现复杂度太高。在软判决算法方面，以Gallager提出的消息传递算法(Message Passing Algorithm, MPA)为主，在因子图上进行消息迭代地传播算法，也称置信传播(Belief Propagation, BP)算法。推广
7、和积(Sum-Product, SP)算法和变异算法，如最小和(Minimum Sum, MS)译码算法。软判决迭代译码算法均具有译码速度快，译码性能优良，复杂度较低的优点。然而，迭代算法在许多情况下，比如当Tanner图中存在环时，并不能保证算法收敛;并且，如果算法收敛，收敛点也不一定全是有意义的。也就是说对于迭代译码算法来讲，尽管在大多数情况下都能收敛到最大似然码字，依然缺乏理论根据，因此采用迭代译码时，译码性能难以分析。2005年，J.Feldman等人,利用线性规划(Linear Programming, LP)松弛，对LDPC码的最大似然(Maximum Likehood, ML)译
8、码进行近似求解，建立了二进制分组码的松弛规划译码模型，从而提出了LP译码算法。作为ML译码的估计，理论证明该算法具有最大似然保持特性，也就是，一旦最优解为整数解，那么该解一定为最大似然码字。同时，当Tanner图中存在环时，可以通过添加限制条件，改进LP译码的性能。四 线性规划译码算法（一） 线性规划以及线性规划松弛线性规划是指在一个线性目标函数下，求解一系列线性约束式集合的问题，即在由一系列线性约束式形成的可行域中寻找线性目标函数的最优值，是较简单的一种凸优化问题。许多简单的优化问题都可以利用线性规划求解。如果一个优化问题的目标函数是线性的，但当且仅当变量取整数时才有意义(比如变量代表候车厅
9、的座椅数目)，那么采用线性规划对此问题无法直接求解。这是因为线性规划的可行域是连续的，求解LP问题所得最优解可能不是整数，从而可能导致解无意义。这样的优化问题为整数线性规划(Integer Linear Programming, ILP)问题，其可行域由离散的整数点组成。LP问题可以通过优化算法高效地求解，ILP却通常是一个NP-hard问题。如果我们对ILP问题中限制变量为整数的条件进行修改，使可行域变为包含所有可行整数点在内的连续域，那么这个ILP问题便被松弛成一个LP问题，可以通过高效的优化算法来求解。此时LP问题的解可能是ILP问题的最优解，也可能不是，如果不是，可以采用现有方法修正结
10、果使其有意义。在很多问题中，只需简单的对每个值进行舍入处理，使其变成整数，就可以得到ILP的最优解。这种通过转化成LP问题来求解ILP问题的方法被称为线性规划松弛。线性规划松弛广泛应用在计算科学和组合优化上的近似求解算法中，用以解决各种难以求解的凸优化问题。（二）等价ILP问题ILP问题是指在有限个整数离散点组成的可行域中，找到使线性代价函数最小的可行点的问题，常见形式如下：（4.1） minimize: aTx subject to: xZn其中x表示一个n维的变量,a表示系数向量, aTx称为代价函数，minimize:aTx称为目标函数，Zn表示n维整数域。（4.2）对ML译码的目标函数
11、进行如下变换使得代价函数符合ILP中最小值优化的特点。假设信道具有离散无记忆的特性，那么，式（4.2）可等价为 （4.3）此时ML译码已变为最小化问题，但仍然是非线性的。对代价函数整体进行整数的加减乘除运算并不会改变最优解的值，在信道特性已知的情况下，为常数，将其加入到式（4.3）的代价函数中，有 （4.4） 称为发送符号yi的最大似然比。取值的正负决定了信道输入端符号取值的可能性。如果 0，则说明信道输入端发送0的可能性大于发送1的可能性。用表示发送端码字为y = (y1,y2,., yk)的代价，而最大似然码字就是码C中具有最小代价的码字。发送符号的最大似然比依赖于信道特性，在不同信道传输
12、下，最大似然比是不一样的。令可得ML译码的等价ILP问题如下式（4.5）所示。这样，就可通过求解ILP问题来获取ML码字。（4.5） minimize: Ty subject to: yC（三）等价LP松弛问题 ML译码虽然可等价为式(4.5)所示ILP译码形式，但求解算法依然具有较高的计算复杂度。通过LP松弛技术对式(4.5)进行初级松弛处理，可以得到一个等价的LP松弛问题，从而可以利用有效的优化算法进行求解。对于一个给定的码C，定义其码字多面体为码C中所有有效码字的凸包，记为Poly(C)，即 （4.6）从式(4.6)知码字多面体中每一点都是码字的凸组合，且码字多面体的顶点与码字一一对应。
13、事实上，LP问题的最优解总是在其可行多面体的顶点处取得。如果将码C的码字多面体Poly(C)作为线性规划松弛后的可行域，那么在Poly(C)中求解使得代价函数最小的点等价于求解式(4.5)所示整数规划问题。因此ML译码可等价为如下式(4.7)所示的LP问题。（4.7） minimize: subject to: f Poly(C)当码长n较大时，根据式（4.6)对码字多面体进行描述是十分复杂的，对式 (4.7)所示LP问题的求解难度也随之增大。因此，希望找到码字多面体的松弛或近似多面体，使其不仅包含所有的码字，而且具有确切的易于表达的可实现的描述形式。五 LP译码（一）等式约束LP译码模型基于
14、线性码的因子图结构，首先给出一个含辅助变量的LP松弛译码模型，对LP问题(4.7)做进一步松弛。建模时，每个变量节点I I对应一个一维变量fi，每个校验节点jJ对应一簇线性约束，且这些线性约束只对该校验节点邻域中的变量节点的码比特值产生影响。为了使约束条件更容易被表达，引入辅助LP变量，这些辅助变量对代价函数均不产生影响。定义校验节点j的本地码字为满足该校验节点的任意二进制向量，并称校验节点j本地码字的集合为校验节点j的本地码，记为Cj。在因子图中，每个校验节点对应一个本地码，码C是所有本地码的交集即C=jCj.每个本地码对应一个本地码字的凸包Poly(Cj),称为本地码字多面体。取所有码字多
15、面体的交集，记为，即= jPoly(Cj)。用变量f=(f1,f2,.,fn)表示码比特序列，通过松弛使码比特变量fi满足以下约束 （5.1）通过该约束，将变量f限制在一个n维的单位立方体中，因此式(5.1)称为箱限制。其次，考虑任意校验节点jJ，将校验节点j邻域N(j)中势为偶数的子集(包括空集)记为S，所有S的集合记为Ej。给定一个二进制码比特序列， 那么该二进制序列f就是校验节点j的本地码字。Ej中的每个S对应校验节点j的一个本地码字。对Ej中的每个S定义一个辅助LP变量wjs，变量wjs可以看成码字以此S结构满足校验节点j的标识:当wjs为1时，表示码字以此S结构满足校验节点j:当wj
16、s为0时，表示码字不以此S结构满足校验节点j。由于wjs为辅助LP变量，将其松弛后应同码比特变量一样，满足约束 （5.2）此外，对给定的校验节点j，Ej中的元素S与j的本地码字按一一对应的关系满足式(5.2)，因此对校验节点j的辅助变量应满足以下约束条件： （5.3）使得校验节点j的本地码字以某个特定的S结构满足该校验节点。相应的，变量节点i的码比特变量fi的值必须同由辅助变量决定的本地码字的S结构相一致,因此，对校验节点j的邻域变量节点的码比特变量，以下约束条件成立 （5.4）对任意一个校验节点jJ，定义多面体Qj如下式（5.5）： 其中w为由校验节点j所有辅助变量wjs组成的向量。记多面体
17、Qj在变量f所定义的空间上的投影为Proj(Qj),且Proj(Qj),就是校验节点j的本地码字多面体Poly(Cj)记为j。令Q=jQj,那么Q在变量f定义的子空间上的投影 （5.6）就是本地码字多面体的交集。目标函数中不包含辅助变量，因此用Q=jQj代替本地码字多面体的交集作为可行多面体并不会改变求解结果。那么含有辅助变量的LP松弛译码模型如式（5.7）所示： minimize:（5.7） subject to: (f，w) Q（二）不等式约束LP译码模型如果能略去辅助变量，找到能直接描述多面体的约束条件，可以得到一个更为简洁的LP问题模型。对任意校验节点jJ，记其邻域N(j)中势为奇数的
18、子集为V，所有V的集合为Dj。给定一个二进制码比特序列，将式(4.2)中的S换成V,Ej换成Dj，如果码比特值满足更换后的等式，就称该序列具有校验节点j的V结构。显然，具有V结构的码比特序列都不能满足相应的校验节点。因此，称V结构为坏结构。图5.1 给定校验节点j，当|N(j)|=3时，邻域变量节点对应的二进制序列分布图 首先使码比特变量fi满足式(5.8)所示箱限制条件 (5.8) 其次，对一个码字而言，必以某个特定的S结构满足给定校验节点j，但就N(j)中的变量节点对应的二进制序列部分而言，码字与校验节点j的任意一个具有坏结构的二进制序列的L1距离至少为1。那么对任意校验节点j J，应该满
19、足式(5.9 )所示不等式，即保证f远离于坏结构。 （5.9）称不等式(5.9 )为奇偶校验不等式。在|N(j)|= 3即三维情况下，从图5.1可以看出，对给定校验节点j，同时满足约束(5.8 )和(5.9 )的点的集合恰好对应于校验节点j的码字多面体j。令所有校验节点j J都满足约束(5.9 )，便可得到所有码字多面体的交集=jj。保持目标函数不变，以码字多面体的交集Q作为可行多面体，得到简洁形式的不等式约束的LP译码模型如下 minimize:（5.10） subject to: 从上节中可知，多面体与多面体Q在变量f空间上的投影是等价的，且目标函数只跟变量f有关，因此，求解(5.10)式
20、得到的最优解f与求解(5.7)式得到的最优解(f*，w*)在变量f空间上的投影是等价的。定义5.1 :给定一个n维多面体P且P 0,1n，如果多面体P的整数顶点恰与码C中的码字一一对应，即P0,1n =C，就称多面体P为一个合适多面体。 引理5.1 多面体是一个合适多面体，即0,1n =C。LP译码的最优解总是在可行多面体的顶点处取得，因此采用合适多面体进行线性规划译码问题求解时，一旦最优解在整数顶点处取得，该整数顶点就是最大似然码字。LP译码步骤如下:求解LP问题，得最优解(f*,w*)或f*;如果f* 0,1n ,输出f*为最大似然码字，否则，如果f*是分数解，输出译码错误。因此，采用LP
21、译码时，如果译码器输出为一个码字，那么保证为最大似然码字。LP译码算法的这个特性称为最大似然保证特性。所以采用LP译码比迭代译码更容易分析译码性能。尽管迭代译码性能优良，但没有任何一种迭代译码算法能从理论上证明其收敛值为ML码字。不过，随着码长n的增长，LP问题的规模将会随n呈指数增长。六 LP译码性能分析（一）抽象可行多面体及误码率分析如图6.1所示为一个抽象的合适松弛多面体P，虽然该多面体显示为二维，但其顶点均可见。其中相连的虚线及其内部表示该合适多面体P，圆点表示多面体顶点，其中实心点表示整数顶点(与码字一一对应)，空心点表示分数顶点，相连的实线及其内部表示码字多面体。内部的箭头表示信道
22、接收端接收到的符号序列方向，均与信道噪声有关，其中灰色箭头表示无信道噪声时接收到的符号序列方向，也是发送码字(y1)的方向，黑色箭头a, b, c, d分别表示四种不同噪声情况下的接收到的符号序列的方向。内部垂直于实心点之间的实连线的直线表示按经典码距译码的判决闭值，垂直于实心点与空心点之间的虚连线的直线表示按分数距离译码的判决闭值。图6.1 给定码C的一个合适多面体P的抽象表示 根据图6.1所示抽象多面体，对LP译码进行分析。 (a)噪声很小时，信道输出端接收符号序列指向为a，无论按分数距离判决还是经典码距判决，此时都应将译为发送码字y1，LP译码输出为ML码字，且采用ML译码和LP译码都成
23、功。(b)噪声变大一些时，信道输出端接收符号序列指向为b，如果采用ML译码，按最小距离判决，译为发送码字y1，而采用LP译码，按最小分数距离判决，译为f，则LP译码输出为分数解f，此时ML译码成功，LP译码失败。(c)噪声继续增大，信道输出端接收符号序列指向为。，如果采用ML译码，按最小距离判决，译为码字y2，如果采用LP译码，按最小分数距离判决，依然译为f , LP译码输出为分数解f，此时ML译码和LP译码均失败。不过由于LP译码结果为分数，译码错误是可检测，而采用ML译码输出依然是最大似然译码，虽然译码错误，但不可检测。(d)噪声很大，信道输出端接收符号序列指向为d，如果采用ML译码，按最
24、小距离判决，译为码字y2，如果采用LP译码，按最小分数距离判决，也译为y2，LP译码输出为整数解，为最大似然码字，此时ML译码和LP译码都出现译码错误，并且错误均不可检测。假设信道输入端的发送码字为y*C，那么LP译码输出可总结为以下四种情况:1)LP问题有一个最优解f* ,，此时LP译码输出译码错误，译码失败。 2) LP问题有一个最优解f*,但f*y*，此时LP译码输出为ML码字，但不是发送码字，译码失败。3 ) LP问题有一个最优解f*,但f*=y*，此时LP译码输出为ML码字，也是发送码字，译码成功。4 ) LP问题有多个最优解，此时，LP译码输出可能正确也可能不正确，我们保守地将这种
25、情况视为译码失败。用Prerr|y*表示LP译码出错的概率，那么有（二）仿真分析在Bi-AWGN信道下，采用LDPC码为信道编码，对编码后的码字进行BPSK调制，研究LDPC码采用三种不同译码算法时的性能，其中BP译码的最大迭代次数为100。码长为96的LDPC码在MS、BP、LP三种译码算法下的误码率曲线如图6.2。 图6.2 码长为96的LDPC码在MS、BP、LP三种译码算法下的误码率曲线从图6.2中可以看出，对具有中长码长的LDPC码，无论高信噪比还是低信噪比时，LP译码的性能都明显好过MS译码。当BER=10-2时，这两种方法的信道增益相差大约0.5dB。同BP译码相比，在低信噪比下，LP译码同BP译码具有相似的性能，随着信噪比增大，BP译码的性能只略好于LP译码。当BER=10-2时，这两种方法的信道增益只相差大约0.05dB，且随着信噪比的继续增大，LP译码和BP译码有相交的趋势。产生这种现象的原因之一是，中短码长的LDPC码的因子图中常有环的存在，因而对其采用BP译码时可能不收敛，从而导致译码性能的下降，而采用LP译码却可以避免这种情况的发生。因此对码长较长的LDPC码，适合采用BP译码算法进行译码，而对中短码长的LDPC码，采用线性规划译码算法可以避免短环对译码性能的影响。
