无线通信报告LDPC码的线性规划译码算法 本文关键词：线性规划，译码，无线通信，算法，报告
无线通信报告LDPC码的线性规划译码算法 本文简介：组合最优化课程论文论文题目：LDPC码的线性规划译码算法班级：13级电子A班姓名：周珍珠学号：13212895任课老师：娄定俊一背景低密度奇偶校验（LowDensityParityCheck,LDPC）码一类具有稀疏校验矩阵的线性分组码，也是一种性能非常接近Shannon极限的信道编码方案，具有很强
无线通信报告LDPC码的线性规划译码算法 本文内容：
组合最优化课程论文
论文题目：LDPC码的线性规划
译码算法
班
级：
13级电子A班
姓
名：
周珍珠
学
号：
13212895
任课老师：
娄定俊
一
背景
低密度奇偶校验（Low
Density
Parity
Check,LDPC）码一类具有稀疏校验矩阵的线性分组码，也是一种性能非常接近Shannon极限的信道编码方案，具有很强的纠错抗干扰能力。LDPC码的线性规划（Linear
Programming，LP）译码算法是将最大似然译码松驰成线性规划问题，译码码字具有最大似然特性。对于LDPC码，线性规划问题中的约束式的数量是随着校验节点度数的增加而呈指数增加，因此研究大规模的线性规划问题的求解问题具有重要的意义。本文对LDPC码的最大似然(Maximum
Likehood,ML)译码进行近似求解，建立了二进制分组码的松弛规划译码模型，从而提出了LP译码算法。作为ML译码的估计，理论证明该算法具有最大似然保持特性，也就是，一旦最优解为整数解，那么该解一定为最大似然码字。同时，当Tanner图中存在环时，可以通过添加限制条件，改进LP译码的性能。所以，LP译码可以避免短环对译码性能的影响，提高性能，在误码性能与复杂上的保持平衡。特别是对中短码长的LDPC码，利用线性规划译码算法性能更突出。
二
LDPC码简介
（一）LDPC码的H矩阵表示法
LDPC码是一种线性分组码，它是把长度为k的信息序列作为一个分组，然后按照一定规则将该信息序列映射为码长为n的码字，可表示为(n,k)线性分组码。对于LDPC码，可以由它的校验矩阵H确定。LDPC码的校验矩阵是m行n列的，一般
LDPC码的码字c就是与其对应的校验矩阵H的零空间，满足如下方程：
cHT=0
(2.1)
图2-1
n=10的二进制LDPC码校验矩阵
图２-1显示的是一个码长为10的LDPC码校验矩阵。对于LDPC码的码率的计算则为:
R≥k/n=(n-m)/n
(2.2)
当且仅当校验矩阵H满秩的时候，等号成立。
对于线性分组通常给出的是k行n列的生成矩阵G，生成矩阵G和校验矩阵H存在着正交的关系，即GHT=0或HGT=0。对于长度为k的信息序列u就可以使用生成矩阵G生成长度为n的码字c，用公式表示如下：
c=uG
(2.3)
而对于LDPC码，我们首先得到是它的校验矩阵H，要想完成编码过程必须得进行一些矩阵变换从校验矩阵H得到生成矩阵G，通常所用的方法为高斯消元法，现将校验矩阵H进行格式变化：
H
=Hp-1H=[Im×m
PTm×k]
(2.4)
Hp-1是一个m×m维的变换矩阵，假设不存在矩阵Hp，则表明H矩阵非满秩，这时我们只需保留矩阵中最大数目的线性相关行即可得到H
矩阵，继而得到生成矩阵G：
G=[Pk×m
Ik×k]
(2.5)
（二）LDPC码的Tanner图表示
LDPC码除了可以使用校验矩阵H进行表示之外，还可以用双向图模型进行表示,而且Tanner图与校验矩阵是一一对应的。Tanner图包含三类元素：变量节点(variable
node)、校验节点(check
node)和连接变量节点与校验节点的边(edge).
在Tanner图中，还有一个环(cycle)的概念：从某个节点出发经过一定的路径又回到了该节点，除了此节点外，其余节点均只出现一次。在这个过程中经过的边数被称为环长，最短的环的环长又被称为围长(girth)。
图2-2
校验矩阵H和对应的Tanner图
图2-2展现了一个校验矩阵和所对应的Tanner图。从图2-2可以看到，校验节点的度数为3，变量节点的度数为2，虚线所示的就是Tanner图中的一个环，由六条边组成，故环长为6。注意到，因子图和校验矩阵的形式是一一对应的，对于一个给定的码，其可能的校验矩阵有很多个，相应地，可能的因子图也有很多个。很多译码算法都依赖于因子图的结构特性，采用这些译码算法时，因子图的多样性就显得尤为重要。
三
LDPC码的译码
LDPC码的译码算法可分为硬判决译码算法和软判决译码算法。硬判决算法操作简单，易于硬件实现，但是性能较差;软判决算法性能较好，但实现复杂度太高。在软判决算法方面，以Gallager提出的消息传递算法(Message
Passing
Algorithm,MPA)为主，在因子图上进行消息迭代地传播算法，也称置信传播(Belief
Propagation,BP)算法。推广和积(Sum-Product,SP)算法和变异算法，如最小和(Minimum
Sum,MS)译码算法。软判决迭代译码算法均具有译码速度快，译码性能优良，复杂度较低的优点。然而，迭代算法在许多情况下，比如当Tanner图中存在环时，并不能保证算法收敛;并且，如果算法收敛，收敛点也不一定全是有意义的。也就是说对于迭代译码算法来讲，尽管在大多数情况下都能收敛到最大似然码字，依然缺乏理论根据，因此采用迭代译码时，译码性能难以分析。
2005年，J.Feldman等人,利用线性规划(Linear
Programming,LP)松弛，对LDPC码的最大似然(Maximum
Likehood,ML)译码进行近似求解，建立了二进制分组码的松弛规划译码模型，从而提出了LP译码算法。作为ML译码的估计，理论证明该算法具有最大似然保持特性，也就是，一旦最优解为整数解，那么该解一定为最大似然码字。同时，当Tanner图中存在环时，可以通过添加限制条件，改进LP译码的性能。
四
线性规划译码算法
（一）
线性规划以及线性规划松弛
线性规划是指在一个线性目标函数下，求解一系列线性约束式集合的问题，即在由一系列线性约束式形成的可行域中寻找线性目标函数的最优值，是较简单的一种凸优化问题。许多简单的优化问题都可以利用线性规划求解。
如果一个优化问题的目标函数是线性的，但当且仅当变量取整数时才有意义(比如变量代表候车厅的座椅数目)，那么采用线性规划对此问题无法直接求解。这是因为线性规划的可行域是连续的，求解LP问题所得最优解可能不是整数，从而可能导致解无意义。这样的优化问题为整数线性规划(Integer
Linear
Programming,ILP)问题，其可行域由离散的整数点组成。
LP问题可以通过优化算法高效地求解，ILP却通常是一个NP-hard问题。如果我们对ILP问题中限制变量为整数的条件进行修改，使可行域变为包含所有可行整数点在内的连续域，那么这个ILP问题便被松弛成一个LP问题，可以通过高效的优化算法来求解。此时LP问题的解可能是ILP问题的最优解，也可能不是，如果不是，可以采用现有方法修正结果使其有意义。在很多问题中，只需简单的对每个值进行舍入处理，使其变成整数，就可以得到ILP的最优解。
这种通过转化成LP问题来求解ILP问题的方法被称为线性规划松弛。线性规划松弛广泛应用在计算科学和组合优化上的近似求解算法中，用以解决各种难以求解的凸优化问题。
（二）等价ILP问题
ILP问题是指在有限个整数离散点组成的可行域中，找到使线性代价函数最小的可行点的问题，常见形式如下：
（4.1）
minimize:
aTx
subject
to:
x?Zn
其中x表示一个n维的变量,a表示系数向量,aTx称为代价函数，minimize:aTx
称为目标函数，Zn表示n维整数域。
（4.2）
对ML译码的目标函数进行如下变换
使得代价函数符合ILP中最小值优化的特点。假设信道具有离散无记忆的特性，
那么，式（4.2）可等价为
（4.3）
此时ML译码已变为最小化问题，但仍然是非线性的。对代价函数整体进行整数的加减乘除运算并不会改变最优解的值，在信道特性已知的情况下，为常数，将其加入到式（4.3）的代价函数中，有
（4.4）
称为发送符号yi的最大似然比。取值的正负决定了信道输入端符号取值的可能性。如果
0，则说明信道输入端发送0的可能性大于发送1的可能性。用表示发送端码字为y
=
(y1,y2,,yk)的代价，而最大似然码字就是码C中具有最小代价的码字。发送符号的最大似然比依赖于信道特性，在不同信道传输下，最大似然比是不一样的。
令可得ML译码的等价ILP问题如下式（4.5）所示。这样，就可通过求解ILP问题来获取ML码字。
（4.5）
minimize:
γTy
subject
to:
y?C
（三）等价LP松弛问题
ML译码虽然可等价为式(4.5)所示ILP译码形式，但求解算法依然具有较高的计算复杂度。通过LP松弛技术对式(4.5)进行初级松弛处理，可以得到一个等价的LP松弛问题，从而可以利用有效的优化算法进行求解。
对于一个给定的码C，定义其码字多面体为码C中所有有效码字的凸包，记为Poly(C)，即
（4.6）
从式(4.6)知码字多面体中每一点都是码字的凸组合，且码字多面体的顶点与码字一一对应。事实上，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译码模型
基于线性码的因子图结构，首先给出一个含辅助变量的LP松弛译码模型，对LP问题(4.7)做进一步松弛。建模时，每个变量节点I
?
I对应一个一维变量fi，每个校验节点j?J对应一簇线性约束，且这些线性约束只对该校验节点邻域中的变量节点的码比特值产生影响。为了使约束条件更容易被表达，引入辅助LP变量，这些辅助变量对代价函数均不产生影响。
定义校验节点j的本地码字为满足该校验节点的任意二进制向量，并称校验节点j本地码字的集合为校验节点j的本地码，记为Cj。在因子图中，每个校验节点对应一个本地码，码C是所有本地码的交集即C=∩jCj.每个本地码对应一个本地码字的凸包Poly(Cj),称为本地码字多面体。取所有码字多面体的交集，记为Ω，即Ω=
∩jPoly(Cj)。用变量f=(f1,f2,.,fn)表示码比特序列，通过松弛使码比特变量fi满足以下约束
（5.1）
通过该约束，将变量f限制在一个n维的单位立方体中，因此式(5.1)称为箱限制。
其次，考虑任意校验节点j?J，将校验节点j邻域N(j)中势为偶数的子集(包括空集?)记为S，所有S的集合记为Ej。给定一个二进制码比特序列，
那么该二进制序列f’就是校验节点j的本地码字。Ej中的每个S对应校验节点j的一个本地码字。对Ej中的每个S定义一个辅助LP变量wjs，变量wjs可以看成码字以此S结构满足校验节点j的标识:当wjs为1时，表示码字以此S结构满足校验节点j:当wjs为0时，表示码字不以此S结构满足校验节点j。由于wjs为辅助LP变量，将其松弛后应同码比特变量一样，满足约束
（5.2）此外，对给定的校验节点j，Ej中的元素S与j的本地码字按一一对应的关系满足式(5.2)，因此对校验节点j的辅助变量应满足以下约束条件：
（5.3）
使得校验节点j的本地码字以某个特定的S结构满足该校验节点。相应的，变量节点i的码比特变量fi的值必须同由辅助变量决定的本地码字的S结构相一致,因此，对校验节点j的邻域变量节点的码比特变量，以下约束条件成立
（5.4）
对任意一个校验节点j?J，定义多面体Qj如下式（5.5）：
其中w为由校验节点j所有辅助变量wjs组成的向量。
记多面体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问题模型。对任意校验节点j?J，记其邻域N(j)中势为奇数的子集为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，应该满足式(5.9
)所示不等式，即保证f远离于坏结构。
（5.9）称不等式(5.9
)为奇偶校验不等式。在|N(j)|=
3即三维情况下，从图5.1可以看出，对给定校验节点j，同时满足约束(5.8
)和(5.9
)的点的集合恰好对应于校验节点j的码字多面体Ωj。令所有校验节点j
?
J都满足约束(5.9
)，便可得到所有码字多面体的交集Ω=∩jΩj。保持目标函数不变，以码字多面体的交集Q作为可行多面体，得到简洁形式的不等式约束的LP译码模型如下
minimize:（5.10）
subject
to:
从上节中可知，多面体Ω与多面体Q在变量f空间上的投影是等价的，且目标函数只跟变量f有关，因此，求解(5.10)式得到的最优解f
与求解(5.7)式得到的最优解(f*，w*)在变量f空间上的投影是等价的。
定义5.1
:给定一个n维多面体P且P
?
[0,1]n，如果多面体P的整数顶点恰与码C中的码字一一对应，即P∩[0,1]n
=C，就称多面体P为一个合适多面体。
引理5.1
多面体Ω是一个合适多面体，即Ω∩[0,1]n
=C。
LP译码的最优解总是在可行多面体的顶点处取得，因此采用合适多面体进行线性规划译码问题求解时，一旦最优解在整数顶点处取得，该整数顶点就是最大似然码字。LP译码步骤如下:求解LP问题，得最优解(f*,w*)或f*;如果f*
?[0,1]n,输出f*为最大似然码字，否则，如果f*是分数解，输出译码错误。因此，采用LP译码时，如果译码器输出为一个码字，那么保证为最大似然码字。LP译码算法的这个特性称为最大似然保证特性。所以采用LP译码比迭代译码更容易分析译码性能。尽管迭代译码性能优良，但没有任何一种迭代译码算法能从理论上证明其收敛值为ML码字。不过，随着码长n的增长，LP问题的规模将会随n呈指数增长。
六
LP译码性能分析
（一）抽象可行多面体及误码率分析
如图6.1所示为一个抽象的合适松弛多面体P，虽然该多面体显示为二维，但其顶点均可见。其中相连的虚线及其内部表示该合适多面体P，圆点表示多面体顶点，其中实心点表示整数顶点(与码字一一对应)，空心点表示分数顶点，相连的实线及其内部表示码字多面体。内部的箭头表示信道接收端接收到的符号序列方向，均与信道噪声有关，其中灰色箭头表示无信道噪声时接收到的符号序列方向，也是发送码字(y1)的方向，黑色箭头a,b,c,d分别表示四种不同噪声情况下的接收到的符号序列的方向。内部垂直于实心点之间的实连线的直线表示按经典码距译码的判决闭值，垂直于实心点与空心点之间的虚连线的直线表示按分数距离译码的判决闭值。
图6.1
给定码C的一个合适多面体P的抽象表示
根据图6.1所示抽象多面体，对LP译码进行分析。
(a)噪声很小时，信道输出端接收符号序列指向为a，无论按分数距离判决还是经典码距判决，此时都应将译为发送码字y1，LP译码输出为ML码字，且采用ML译码和LP译码都成功。
(b)噪声变大一些时，信道输出端接收符号序列指向为b，如果采用ML译码，按最小距离判决，译为发送码字y1，而采用LP译码，按最小分数距离判决，译为f，则LP译码输出为分数解f，此时ML译码成功，LP译码失败。
(c)噪声继续增大，信道输出端接收符号序列指向为。，如果采用ML译码，按最小距离判决，译为码字y2，如果采用LP译码，按最小分数距离判决，依然译为f,LP译码输出为分数解f，此时ML译码和LP译码均失败。不过由于LP译码结果为分数，译码错误是可检测，而采用ML译码输出依然是最大似然译码，虽然译码错误，但不可检测。
(d)噪声很大，信道输出端接收符号序列指向为d，如果采用ML译码，按最小距离判决，译为码字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译码输出可能正确也可能不正确，我们保守地将这种情况视为译码失败。
用Pr[err|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码，采用线性规划译码算法可以避免短环对译码性能的影响。
10
周珍珠
13212895
信息与通信工程专业（电A）
篇2：《数学建模与数学实验》实验报告实验五线性规划模型实验
《数学建模与数学实验》实验报告实验五线性规划模型实验 本文关键词：实验，线性规划，数学，建模，模型
《数学建模与数学实验》实验报告实验五线性规划模型实验 本文简介：《数学建模与数学实验》实验报告实验五：线性规划模型实验专业、班级数学09B学号094080144姓名徐波课程编号实验类型验证性学时2实验（上机）地点同析楼4栋404完成时间2012-6-10任课教师李锋评分一、实验目的及要求掌握数学软件lingo的基本用法和一些常用的规则，能用该软件进行基本线性规划
《数学建模与数学实验》实验报告实验五线性规划模型实验 本文内容：
《数学建模与数学实验》实验报告
实验五：线性规划模型实验
专业、班级
数学09B
学号
094080144
姓名
徐波
课程编号
实验类型
验证性
学时
2
实验（上机）地点
同析楼4栋404
完成时间
2012-6-10
任课教师
李锋
评分
一、实验目的及要求
掌握数学软件lingo的基本用法和一些常用的规则，能用该软件进行基本线性规划运算，并能进行的编程，掌握线性规划模型的。
2、
借助数学软件，研究、解答以下问题
某电力公司经营两座发电站，发电站分别位于两个水库上，已知发电站A可以将A的一万m^3
的水转换成400千度电能，发电站B能将水库B的一万立方米转化成200千度电能。发电站A，B每个月最大发电能力分别是60000千度，35000千度，每个月最多有50000千度能够以200元/千度的价格出售，多余的电能只能够以140元/千度的价格出售，水库A,B的其他有关数据如下：
水库A
书库B
水库最大蓄水量
2000
1500
水源本月流入水量
200
40
水源下月流入水量
130
15
水库最小蓄水量
1200
800
水库目前蓄水量
1900
850
设计该电力公司本月和下月的生产计划。
本月的情况：
解:
设本月高价卖出的水量是u，低价卖出的数量是v，A,B书库用来发电的水量好似xa，xb，从水库里放走的水量是ya，yb，水库月末剩余的水量分别是za，zb；
建立模型如下：
目标函数：、
Max=200u+140v
约束条件：
每个月发电量与卖电量相等：
400*x1+200*x2=u+v;
水库发电后剩余水量及消耗水量与发电前的水量守恒：
X1+y1+z1=2100;
X2+y2+z2=890+x1+y1;
其他约束条件：
400*x1a=1200;
Z1=800;
Z2=1200;
Z1b=1200;
Z2a=800;
Z2b>=800;
Z2b<=1500;
u1<=50000;
u2<=50000;
end
解得：
Global
optimal
solution
found.
Objective
value:
0.3330000E+08
Total
solver
iterations:
0
Variable
Value
Reduced
Cost
U1
50000.00
0.000000
U2
50000.00
0.000000
V1
50000.00
0.000000
V2
45000.00
0.000000
X1A
0.000000
56000.00
X2A
0.000000
28000.00
X1B
150.0000
0.000000
X2B
175.0000
0.000000
Y1A
900.0000
0.000000
Z1A
1200.000
0.000000
Y2B
0.000000
0.000000
Z2B
800.0000
0.000000
ZB2
810.0000
0.000000
Y1B
0.000000
0.000000
Y2A
990.0000
0.000000
Z2A
800.0000
0.000000
Z1B
1330.000
0.000000
Row
Slack
or
Surplus
Dual
Price
1
0.3330000E+08
1.000000
2
0.000000
140.0000
3
0.000000
-140.0000
4
0.000000
0.000000
5
0.000000
0.000000
6
0.000000
0.000000
7
0.000000
0.000000
8
60000.00
0.000000
9
0.000000
140.0000
10
35000.00
0.000000
11
0.000000
140.0000
12
800.0000
0.000000
13
0.000000
0.000000
14
670.0000
0.000000
15
0.000000
0.000000
16
700.0000
0.000000
17
0.000000
0.000000
18
0.000000
0.000000
19
700.0000
0.000000
20
0.000000
340.0000
21
0.000000
60.00000
由上可知，最大值是0.3260000E+08，每月A,B厂发电用水量是150,175,150,175
三、本次实验的难点分析
实验过程中遇到了一些问题：
对掌握lingo的基本用法有所欠缺，本实验中存在偏差。
4、
参考文献
姜启源，谢金星，叶俊．数学模型（第三版），高等教育出版社，2003
6