组合最优化课程论文
论文题目：LDPC 码的线性规划
译码算法
班 级： ***** 姓 名： ***
学 号： ****
任课老师： ***
一 背景
低密度奇偶校验（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 的零空间，满足如下方程：
cH T =0 (2.1)
⎡1⎢0⎢H =⎢1⎢⎢0
⎢⎣[***********][***********]001010⎤0⎥⎥0⎥⎥1⎥0⎥⎦
图2-1 n =10的二进制LDPC 码校验矩阵
图２-1显示的是一个码长为10的LDPC 码校验矩阵。对于LDPC 码的码率的计算则为:
R ≥k /n=(n-m) /n (2.2) 当且仅当校验矩阵H 满秩的时候，等号成立。
对于线性分组通常给出的是k 行n 列的生成矩阵G ，生成矩阵G 和校验矩阵H 存在着正交的关系，即GH T =0或HG T =0。对于长度为k 的信息序列u 就可以使用生成矩阵G 生成长度为n 的码字c ，用公式表示如下：
c=uG (2.3) 而对于LDPC 码，我们首先得到是它的校验矩阵H ，要想完成编码过程必须得进行一些矩阵变换从校验矩阵H 得到生成矩阵G ，通常所用的方法为高斯消元法，现将校验矩阵H 进行格式变化：
H '=H p -1H =[I m ×m P T m ×k ] (2.4) H p -1是一个m ×m 维的变换矩阵，假设不存在矩阵H p ，则表明H 矩阵非满秩，这时我们只需保留矩阵中最大数目的线性相关行即可得到H ' 矩阵，继而得到生成矩阵G ：
G =[P k ×m I k ×k ]
（二）LDPC 码的Tanner 图表示 (2.5)
LDPC 码除了可以使用校验矩阵H 进行表示之外，还可以用双向图模型进行表示, 而且Tanner 图与校验矩阵是一一对应的。Tanner 图包含三类元素：变量节点(variable node) 、校验节点(check node) 和连接变量节点与校验节点的边(edge). 在Tanner 图中，还有一个环(cycle)的概念：从某个节点出发经过一定的路径又回到了该节点，除了此节点外，其余节点均只出现一次。在这个过程中经过的边数被称为环长，最短的环的环长又被称为围长(girth)。
0H =⎢⎣0⎥001⎥010⎥⎥10011⎦012345图2-2 校验矩阵H 和对应的Tanner 图 00⎤
图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 问题是指在有限个整数离散点组成的可行域中，找到使线性代价函数最小的可行点的问题，常见形式如下：
minimize: aT x （4.1） subject to: xєZ n
其中x 表示一个n 维的变量,a 表示系数向量, aT x 称为代价函数，minimize:aT x 称为目标函数，Z n 表示n 维整数域。 （4.2）
y ∈C y ∈C
使得代价函数符合ILP 中最小值优化的特点。假设信道具有离散无记忆的特性， 对ML 译码的目标函数进行如下变换 ˆ|y ]=arg min -ln(Pr[y ˆ|y ])y *=arg max Pr[y
ˆ|y ]=∏Pr[y ˆi |y i ]，式（4.2）可等价为 那么Pr[y i =1n
ˆi |y i ])=arg min -∑ln(Pr[y ˆi |y i ]) （4.3） y =arg min -ln(∏Pr[y y ∈C i =1y ∈C i =1*n n
此时ML 译码已变为最小化问题，但仍然是非线性的。对代价函数整体进行整数的加减乘除运算并不会改变最优解的值，在信道特性已知的情况下，i =1ˆ[∑l n (P r y |=i y i
*n
y ∈C i =1n 为常数，将其加入到式（4.3）的代价函数中，有 0]) n i =1ˆi |y i =0])-∑ln(Pr[y ˆi |y i ])} y =arg min{∑ln(Pr[y
=a r g m i n ∑{y ∈C i :y i =0ˆy |=P r y [i i ˆi y |i =P r y [0]+∑) 0]i y i :=1ˆy P r y [=|i i ˆy P [i =|i r y 0]) }1]
=arg min ∑ln(y ∈C i :y i =1
n ˆi |y i =0]Pr[y ) ˆi |y i =1]Pr[y （4.4） =a r g m ∑i n y i y ∈C i =1ˆy |=P r y [i i ˆi y |i =P r y [0] 1])
γi =ln(ˆi |y i =0]Pr[y ), i ∈{1,2,..., n } ˆi |y i =1]Pr[y
称为发送符号yi 的最大似然比。
能性。如果γi 取值的正负决定了信道输入端符号取值的可γi 0，则说明信道输入端发送0的可能性大于发送1的可能性。用=1表示发送端码字为y = (y1,y2,......, yk) 的代价，而最大似然码字就是码C 中具有最小代价的码字。发送符号的最大似然比依赖于信道特性，在不同信道传输下，最
大似然比是不一样的。
令γ=(γ1, γ2,..., γn ) T , y =(y 1, y 2,..., y n ) T , 可得ML 译码的等价ILP 问题如下式（4.5）所示。这样，就可通过求解ILP 问题来获取ML 码字。
minimize: γT y
subject to: yєC
（三）等价LP 松弛问题 （4.5）
ML 译码虽然可等价为式(4.5)所示ILP 译码形式，但求解算法依然具有较高的计算复杂度。通过LP 松弛技术对式(4.5)进行初级松弛处理，可以得到一个等价的LP 松弛问题，从而可以利用有效的优化算法进行求解。
对于一个给定的码C ，定义其码字多面体为码C 中所有有效码字的凸包，记为Poly(C)，即
C ={∑λy P o l (y ) y ∈C y λ:y ≥0∑, λy =∈y C 1 （4.6）
从式(4.6)知码字多面体中每一点都是码字的凸组合，且码字多面体的顶点与码字一一对应。事实上，LP 问题的最优解总是在其可行多面体的顶点处取得。如果将码C 的码字多面体Poly(C)作为线性规划松弛后的可行域，那么在Poly(C)中求解使得代价函数最小的点等价于求解式(4.5)所示整数规划问题。因此ML 译码可等价为如下式(4.7)所示的LP 问题。
minimize:∑γi f i i =1n （4.7） 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)表示码比特序列，通过松弛使码比特变量f i 满足以下约束
∀i ∈I , 0≤i f ≤1 （5.1） 通过该约束，将变量f 限制在一个n 维的单位立方体中，因此式(5.1)称为箱限制。
其次，考虑任意校验节点j єJ ，将校验节点j 邻域N(j)中势为偶数的子集(包括空集∅) 记为S ，所有S 的集合记为E j 。给定一个二进制码比特序列
' f ' =(f 1' , f 2,..., f n ) ' ， 那么该二进制序列f ’就是校验节点j 的本地码字。E j 中的每
个S 对应校验节点j 的一个本地码字。对E j 中的每个S 定义一个辅助LP 变量w js ，变量w js 可以看成码字以此S 结构满足校验节点j 的标识:当w js 为1时，表示码字以此S 结构满足校验节点j:当w js 为0时，表示码字不以此S 结构满足校验节点j 。由于w js 为辅助LP 变量，将其松弛后应同码比特变量一样，满足约束
∀S ∈E j ,0≤w j , s ≤1 （5.2）此外，对给定的校验节点j ，E j 中的元素S 与j 的本地码字按一一对应的关系满足式(5.2)，因此对校验节点j 的辅助变量应满足以下约束条件：
S ∈E j ∑w j , s =1 （5.3） 使得校验节点j 的本地码字以某个特定的S 结构满足该校验节点。相应的，变量节点i 的码比特变量f i 的值必须同由辅助变量决定的本地码字的S 结构相一致, 因此，对校验节点j 的邻域变量节点的码比特变量，以下约束条件成立 ∀i ∈N (j ), f i =∑w j , s （5.4） i ∈S , S ∈E j
对任意一个校验节点j єJ ，定义多面体Q j 如下式（5.5）：
Q j ={(f , w ):∀i ∈I ,0≤f i ≤1, ∀S ∈E j ,0≤w j , s ≤1, ∑w j , s =1, ∀i ∈N (j ), f i =∑w j , s }S ∈E j i ∈S , S ∈E j
j
其中w 为由校验节点j 所有辅助变量wjs 组成的向量。 w =(w j , S 1, w j , S 2,..., w j , S |F |)
记多面体Qj 在变量f 所定义的空间上的投影为Proj(Qj),且Proj(Qj),就是校验节点j 的本地码字多面体Poly(Cj)记为Ωj 。令Q=∩jQj, 那么Q 在变量f 定义的子空间上的投影
P r o j (Q =) P o r ⋂j j (j Q =) ⋂j P o r j Q (=⋂) j Q ) j (=Ω （5.6）就是本地码字多面体的交集Ω。目标函数中不包含辅助变量，因此用Q=∩j Q j 代替本地码字多面体的交集Ω作为可行多面体并不会改变求解结果。
那么含有辅助变量的LP 松弛译码模型如式（5.7）所示：
minimize:∑γi f i i =1n （5.7）
subject to: (f，w) є Q
（二）不等式约束LP 译码模型
如果能略去辅助变量，找到能直接描述多面体Ω的约束条件，可以得到一个更为简洁的LP 问题模型。对任意校验节点j єJ ，记其邻域N(j)中势为奇数的子集为V ，所有V 的集合为D j 。给定一个二进制码比特序列f ' =(f 1' , f 2' ,..., f n ' ) ，将式(4.2)中的S 换成V ,E j 换成D j ，如果码比特值满足更换后的等式，就称该序列具有校验节点j 的V 结构。显然，具有V 结构的码比特序列都不能满足相应的校验节点。因此，称V 结构为坏结构。
图5.1 给定校验节点j ，当|N(j)|=3时，邻域变量节点对应的二进制序列分布图 首先使码比特变量f i 满足式(5.8)所示箱限制条件
∀i ∈I , 0≤i f ≤1 (5.8) 其次，对一个码字而言，必以某个特定的S 结构满足给定校验节点j ，但就N(j)中的变量节点对应的二进制序列部分而言，码字与校验节点j 的任意一个具有坏结构的二进制序列的L1距离至少为1。那么对任意校验节点j є J ，应该满足式(5.9 )所示不等式，即保证f 远离于坏结构。
∀V ∈D j , ∑f -f ) 1i +∑(1i ≥i ∈(N (j ) \V ) ∈i V （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:∑γi f i i =1n （5.10） subject to: 0≤f i ≤1, ∀i ∈I i ∈(N (j )\V ) ∑f i +∑(1-f i ) ≥1, ∀V ∈D j , ∀j ∈J i ∈V
从上节中可知，多面体Ω与多面体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)噪声很小时，信道输出端接收符号序列y
ˆ译为发送码字y1，LP 译码输出为ML 码字，还是经典码距判决，此时都应将y
且采用ML 译码和LP 译码都成功。
ˆ指向为b ，如果采用ML 译(b)噪声变大一些时，信道输出端接收符号序列y
ˆ译为发送码字y1，而采用LP 译码，按最小分数距离判码，按最小距离判决，y
ˆ译为f ，则LP 译码输出为分数解f ，此时ML 译码成功，LP 译码失败。 决，y
ˆ指向为。(c)噪声继续增大，信道输出端接收符号序列y ，如果采用ML 译码，
ˆ译为码字y2，如果采用LP 译码，按最小分数距离判决，y ˆ按最小距离判决，y
依然译为f , LP译码输出为分数解f ，此时ML 译码和LP 译码均失败。不过由于LP 译码结果为分数，译码错误是可检测，而采用ML 译码输出依然是最大似然译码，虽然译码错误，但不可检测。
ˆ指向为d ，如果采用ML 译码，按(d)噪声很大，信道输出端接收符号序列y
ˆ译为码字y2，如果采用LP 译码，按最小分数距离判决，y ˆ也最小距离判决，y
译为y2，LP 译码输出为整数解，为最大似然码字，此时ML 译码和LP 译码都出现译码错误，并且错误均不可检测。
假设信道输入端的发送码字为y*єC ，那么LP 译码输出可总结为以下四种情况:
1)LP 问题有一个最优解f* ,f *∉{0,1}n ，此时LP 译码输出译码错误，译码失败。
*n 2) LP 问题有一个最优解f'*,f ∈{0,1}但f*≠y*，此时LP 译码输出为ML
码字，但不是发送码字，译码失败。
3 ) LP问题有一个最优解f'*,f *∈{0,1}n 但f*=y*，此时LP 译码输出为ML 码字，也是发送码字，译码成功。
4 ) LP问题有多个最优解，此时，LP 译码输出可能正确也可能不正确，我们保守地将这种情况视为译码失败。
用Pr[err|y*]表示LP 译码出错的概率，那么有
Pr[err |y *]=Pr[∃(f , w ) ∈Q , f ≠y *:∑γi f i ≤∑γi y i *]=Pr[∃f ∈Ω, f ≠y *:∑γi f i ≤∑γi y i *]
i i i i
（二）仿真分析
在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
组合最优化课程论文
论文题目：LDPC 码的线性规划
译码算法
班 级： ***** 姓 名： ***
学 号： ****
任课老师： ***
一 背景
低密度奇偶校验（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 的零空间，满足如下方程：
cH T =0 (2.1)
⎡1⎢0⎢H =⎢1⎢⎢0
⎢⎣[***********][***********]001010⎤0⎥⎥0⎥⎥1⎥0⎥⎦
图2-1 n =10的二进制LDPC 码校验矩阵
图２-1显示的是一个码长为10的LDPC 码校验矩阵。对于LDPC 码的码率的计算则为:
R ≥k /n=(n-m) /n (2.2) 当且仅当校验矩阵H 满秩的时候，等号成立。
对于线性分组通常给出的是k 行n 列的生成矩阵G ，生成矩阵G 和校验矩阵H 存在着正交的关系，即GH T =0或HG T =0。对于长度为k 的信息序列u 就可以使用生成矩阵G 生成长度为n 的码字c ，用公式表示如下：
c=uG (2.3) 而对于LDPC 码，我们首先得到是它的校验矩阵H ，要想完成编码过程必须得进行一些矩阵变换从校验矩阵H 得到生成矩阵G ，通常所用的方法为高斯消元法，现将校验矩阵H 进行格式变化：
H '=H p -1H =[I m ×m P T m ×k ] (2.4) H p -1是一个m ×m 维的变换矩阵，假设不存在矩阵H p ，则表明H 矩阵非满秩，这时我们只需保留矩阵中最大数目的线性相关行即可得到H ' 矩阵，继而得到生成矩阵G ：
G =[P k ×m I k ×k ]
（二）LDPC 码的Tanner 图表示 (2.5)
LDPC 码除了可以使用校验矩阵H 进行表示之外，还可以用双向图模型进行表示, 而且Tanner 图与校验矩阵是一一对应的。Tanner 图包含三类元素：变量节点(variable node) 、校验节点(check node) 和连接变量节点与校验节点的边(edge). 在Tanner 图中，还有一个环(cycle)的概念：从某个节点出发经过一定的路径又回到了该节点，除了此节点外，其余节点均只出现一次。在这个过程中经过的边数被称为环长，最短的环的环长又被称为围长(girth)。
0H =⎢⎣0⎥001⎥010⎥⎥10011⎦012345图2-2 校验矩阵H 和对应的Tanner 图 00⎤
图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 问题是指在有限个整数离散点组成的可行域中，找到使线性代价函数最小的可行点的问题，常见形式如下：
minimize: aT x （4.1） subject to: xєZ n
其中x 表示一个n 维的变量,a 表示系数向量, aT x 称为代价函数，minimize:aT x 称为目标函数，Z n 表示n 维整数域。 （4.2）
y ∈C y ∈C
使得代价函数符合ILP 中最小值优化的特点。假设信道具有离散无记忆的特性， 对ML 译码的目标函数进行如下变换 ˆ|y ]=arg min -ln(Pr[y ˆ|y ])y *=arg max Pr[y
ˆ|y ]=∏Pr[y ˆi |y i ]，式（4.2）可等价为 那么Pr[y i =1n
ˆi |y i ])=arg min -∑ln(Pr[y ˆi |y i ]) （4.3） y =arg min -ln(∏Pr[y y ∈C i =1y ∈C i =1*n n
此时ML 译码已变为最小化问题，但仍然是非线性的。对代价函数整体进行整数的加减乘除运算并不会改变最优解的值，在信道特性已知的情况下，i =1ˆ[∑l n (P r y |=i y i
*n
y ∈C i =1n 为常数，将其加入到式（4.3）的代价函数中，有 0]) n i =1ˆi |y i =0])-∑ln(Pr[y ˆi |y i ])} y =arg min{∑ln(Pr[y
=a r g m i n ∑{y ∈C i :y i =0ˆy |=P r y [i i ˆi y |i =P r y [0]+∑) 0]i y i :=1ˆy P r y [=|i i ˆy P [i =|i r y 0]) }1]
=arg min ∑ln(y ∈C i :y i =1
n ˆi |y i =0]Pr[y ) ˆi |y i =1]Pr[y （4.4） =a r g m ∑i n y i y ∈C i =1ˆy |=P r y [i i ˆi y |i =P r y [0] 1])
γi =ln(ˆi |y i =0]Pr[y ), i ∈{1,2,..., n } ˆi |y i =1]Pr[y
称为发送符号yi 的最大似然比。
能性。如果γi 取值的正负决定了信道输入端符号取值的可γi 0，则说明信道输入端发送0的可能性大于发送1的可能性。用=1表示发送端码字为y = (y1,y2,......, yk) 的代价，而最大似然码字就是码C 中具有最小代价的码字。发送符号的最大似然比依赖于信道特性，在不同信道传输下，最
大似然比是不一样的。
令γ=(γ1, γ2,..., γn ) T , y =(y 1, y 2,..., y n ) T , 可得ML 译码的等价ILP 问题如下式（4.5）所示。这样，就可通过求解ILP 问题来获取ML 码字。
minimize: γT y
subject to: yєC
（三）等价LP 松弛问题 （4.5）
ML 译码虽然可等价为式(4.5)所示ILP 译码形式，但求解算法依然具有较高的计算复杂度。通过LP 松弛技术对式(4.5)进行初级松弛处理，可以得到一个等价的LP 松弛问题，从而可以利用有效的优化算法进行求解。
对于一个给定的码C ，定义其码字多面体为码C 中所有有效码字的凸包，记为Poly(C)，即
C ={∑λy P o l (y ) y ∈C y λ:y ≥0∑, λy =∈y C 1 （4.6）
从式(4.6)知码字多面体中每一点都是码字的凸组合，且码字多面体的顶点与码字一一对应。事实上，LP 问题的最优解总是在其可行多面体的顶点处取得。如果将码C 的码字多面体Poly(C)作为线性规划松弛后的可行域，那么在Poly(C)中求解使得代价函数最小的点等价于求解式(4.5)所示整数规划问题。因此ML 译码可等价为如下式(4.7)所示的LP 问题。
minimize:∑γi f i i =1n （4.7） 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)表示码比特序列，通过松弛使码比特变量f i 满足以下约束
∀i ∈I , 0≤i f ≤1 （5.1） 通过该约束，将变量f 限制在一个n 维的单位立方体中，因此式(5.1)称为箱限制。
其次，考虑任意校验节点j єJ ，将校验节点j 邻域N(j)中势为偶数的子集(包括空集∅) 记为S ，所有S 的集合记为E j 。给定一个二进制码比特序列
' f ' =(f 1' , f 2,..., f n ) ' ， 那么该二进制序列f ’就是校验节点j 的本地码字。E j 中的每
个S 对应校验节点j 的一个本地码字。对E j 中的每个S 定义一个辅助LP 变量w js ，变量w js 可以看成码字以此S 结构满足校验节点j 的标识:当w js 为1时，表示码字以此S 结构满足校验节点j:当w js 为0时，表示码字不以此S 结构满足校验节点j 。由于w js 为辅助LP 变量，将其松弛后应同码比特变量一样，满足约束
∀S ∈E j ,0≤w j , s ≤1 （5.2）此外，对给定的校验节点j ，E j 中的元素S 与j 的本地码字按一一对应的关系满足式(5.2)，因此对校验节点j 的辅助变量应满足以下约束条件：
S ∈E j ∑w j , s =1 （5.3） 使得校验节点j 的本地码字以某个特定的S 结构满足该校验节点。相应的，变量节点i 的码比特变量f i 的值必须同由辅助变量决定的本地码字的S 结构相一致, 因此，对校验节点j 的邻域变量节点的码比特变量，以下约束条件成立 ∀i ∈N (j ), f i =∑w j , s （5.4） i ∈S , S ∈E j
对任意一个校验节点j єJ ，定义多面体Q j 如下式（5.5）：
Q j ={(f , w ):∀i ∈I ,0≤f i ≤1, ∀S ∈E j ,0≤w j , s ≤1, ∑w j , s =1, ∀i ∈N (j ), f i =∑w j , s }S ∈E j i ∈S , S ∈E j
j
其中w 为由校验节点j 所有辅助变量wjs 组成的向量。 w =(w j , S 1, w j , S 2,..., w j , S |F |)
记多面体Qj 在变量f 所定义的空间上的投影为Proj(Qj),且Proj(Qj),就是校验节点j 的本地码字多面体Poly(Cj)记为Ωj 。令Q=∩jQj, 那么Q 在变量f 定义的子空间上的投影
P r o j (Q =) P o r ⋂j j (j Q =) ⋂j P o r j Q (=⋂) j Q ) j (=Ω （5.6）就是本地码字多面体的交集Ω。目标函数中不包含辅助变量，因此用Q=∩j Q j 代替本地码字多面体的交集Ω作为可行多面体并不会改变求解结果。
那么含有辅助变量的LP 松弛译码模型如式（5.7）所示：
minimize:∑γi f i i =1n （5.7）
subject to: (f，w) є Q
（二）不等式约束LP 译码模型
如果能略去辅助变量，找到能直接描述多面体Ω的约束条件，可以得到一个更为简洁的LP 问题模型。对任意校验节点j єJ ，记其邻域N(j)中势为奇数的子集为V ，所有V 的集合为D j 。给定一个二进制码比特序列f ' =(f 1' , f 2' ,..., f n ' ) ，将式(4.2)中的S 换成V ,E j 换成D j ，如果码比特值满足更换后的等式，就称该序列具有校验节点j 的V 结构。显然，具有V 结构的码比特序列都不能满足相应的校验节点。因此，称V 结构为坏结构。
图5.1 给定校验节点j ，当|N(j)|=3时，邻域变量节点对应的二进制序列分布图 首先使码比特变量f i 满足式(5.8)所示箱限制条件
∀i ∈I , 0≤i f ≤1 (5.8) 其次，对一个码字而言，必以某个特定的S 结构满足给定校验节点j ，但就N(j)中的变量节点对应的二进制序列部分而言，码字与校验节点j 的任意一个具有坏结构的二进制序列的L1距离至少为1。那么对任意校验节点j є J ，应该满足式(5.9 )所示不等式，即保证f 远离于坏结构。
∀V ∈D j , ∑f -f ) 1i +∑(1i ≥i ∈(N (j ) \V ) ∈i V （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:∑γi f i i =1n （5.10） subject to: 0≤f i ≤1, ∀i ∈I i ∈(N (j )\V ) ∑f i +∑(1-f i ) ≥1, ∀V ∈D j , ∀j ∈J i ∈V
从上节中可知，多面体Ω与多面体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)噪声很小时，信道输出端接收符号序列y
ˆ译为发送码字y1，LP 译码输出为ML 码字，还是经典码距判决，此时都应将y
且采用ML 译码和LP 译码都成功。
ˆ指向为b ，如果采用ML 译(b)噪声变大一些时，信道输出端接收符号序列y
ˆ译为发送码字y1，而采用LP 译码，按最小分数距离判码，按最小距离判决，y
ˆ译为f ，则LP 译码输出为分数解f ，此时ML 译码成功，LP 译码失败。 决，y
ˆ指向为。(c)噪声继续增大，信道输出端接收符号序列y ，如果采用ML 译码，
ˆ译为码字y2，如果采用LP 译码，按最小分数距离判决，y ˆ按最小距离判决，y
依然译为f , LP译码输出为分数解f ，此时ML 译码和LP 译码均失败。不过由于LP 译码结果为分数，译码错误是可检测，而采用ML 译码输出依然是最大似然译码，虽然译码错误，但不可检测。
ˆ指向为d ，如果采用ML 译码，按(d)噪声很大，信道输出端接收符号序列y
ˆ译为码字y2，如果采用LP 译码，按最小分数距离判决，y ˆ也最小距离判决，y
译为y2，LP 译码输出为整数解，为最大似然码字，此时ML 译码和LP 译码都出现译码错误，并且错误均不可检测。
假设信道输入端的发送码字为y*єC ，那么LP 译码输出可总结为以下四种情况:
1)LP 问题有一个最优解f* ,f *∉{0,1}n ，此时LP 译码输出译码错误，译码失败。
*n 2) LP 问题有一个最优解f'*,f ∈{0,1}但f*≠y*，此时LP 译码输出为ML
码字，但不是发送码字，译码失败。
3 ) LP问题有一个最优解f'*,f *∈{0,1}n 但f*=y*，此时LP 译码输出为ML 码字，也是发送码字，译码成功。
4 ) LP问题有多个最优解，此时，LP 译码输出可能正确也可能不正确，我们保守地将这种情况视为译码失败。
用Pr[err|y*]表示LP 译码出错的概率，那么有
Pr[err |y *]=Pr[∃(f , w ) ∈Q , f ≠y *:∑γi f i ≤∑γi y i *]=Pr[∃f ∈Ω, f ≠y *:∑γi f i ≤∑γi y i *]
i i i i
（二）仿真分析
在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