《无线通信报告LDPC码的线性规划译码算法》由会员分享，可在线阅读，更多相关《无线通信报告LDPC码的线性规划译码算法（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),称为本地码字多面体。取所有码字多面体的交集，记为，即= 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可以看成码字以
