无线通信报告ldpc码的线性规划译码算法(编辑修改稿)

无线通信报告ldpc码的线性规划译码算法(编辑修改稿)内容摘要：

g m in l n ( )ˆPr [ | 1 ]n iiiyC i iiyyy yy   ˆPr [ | 0 ]l n ( ) , { 1 , 2 , .. ., }ˆPr [ | 1 ]iiiiiyy inyy  称为发送符号 yi 的最大似然比。 i 取值的正负决定了信道输入端符号取值的可能性。 如果 i 0，说明信道输入端发送 1 的可能性大于发送 0 的可能性。 反之，如果 i 0，则说明信道输入端发送 0 的可能性大于发送 1 的可能性。 用 1n iii y 表示发送端码字为 y = (y1,y2,......, yk)的代价，而最大似然码字就是码 C 中具有最小代价的码字。 发送符号的最大似然比 依赖于信道特性，在不同信道传输下，最（ ） （ ） （ ） 周珍珠 13212895 信息与通信工程专业（电 A） 5 大似然比是不一样的。 令 1 2 1 2( , , .. ., ) , ( , , .. ., ) ,TTnny y y y   可得 ML 译码的等价 ILP 问题如下式（ ）所示。 这样，就可通过求解 ILP 问题来获取 ML 码字。 minimize: γTy subject to: yєC （三） 等价 LP 松弛问题 ML 译码虽然可等价为式 ()所示 ILP 译码形式，但求解算法依然具有较高的计算复杂度。 通过 LP 松弛技术对式 ()进行初级松弛处理，可以得到一个等价的 LP 松弛问题，从而可以利用有效的优化算法进行求解。 对于一个给定的码 C，定义其码字多面体为码 C 中所有有效码字的凸包，记为 Poly(C)，即 ( ) { : 0 , 1 }y y yy C y CP oly C y       （ ） 从式 ()知 码字多面体中每一点都是码字的凸组合，且码字多面体的顶点与码字一一对应。 事实上， LP 问题的最优解总是在其可行多面体的顶点处取得。 如果将码 C 的码字 多面体 Poly(C)作为线性规划松弛后的可行域，那么在 Poly(C)中求解使得代价函数最小的点等价于求解式 ()所示整数规划问题。 因此 ML 译码可等价为如下式 ()所示的 LP 问题。 minimize:1n iii f subject to: f є Poly(C) 当码长 n 较大时，根据式 （ )对码字多面体进行描述是十分复杂的，对式 ()所示 LP 问题的求解难度也随之增大。 因此，希望找到码字多面体的松弛或近似多面体，使其不仅包含所有的码字，而且具有确切的易于表达的可实现的描述形式。 五 LP 译码 （一） 等式约束 LP 译码模型 基于线性码的因子图结构，首先给出一个含辅助变量的 LP 松弛译码模型，对 LP 问题 ()做进一步松弛。 建模时，每个变量节点 I є I 对应一个一维变量fi，每个校验节点 jєJ 对应一簇线性约束，且这些线性约束只对该校验节点邻域中的变量节点的码比特值产生影响。 为了使约束条件更容易被表达，引入辅助LP 变量，这些辅助变量对代价函数均不 产生影响。 定义校验节点 j 的本地码字为满足该校验节点的任意二进制向量，并称校验节点 j 本地码字的集合为校验节点 j 的本地码，记为 Cj。 在因子图中，每个校验节点对应一个本地码，码 C 是所有本地码的交集即 C=∩ 个本地码字的凸包 Poly(Cj),称为本地码字多面体。 取所有码字多面体的交集，记（ ） （ ） 周珍珠 13212895 信息与通信工程专业（电 A） 6 为Ω，即Ω = ∩ jPoly(Cj)。 用变量 f=(f1,f2,...,fn)表示码比特序列，通过松弛使码比特变量 fi满足以下约束 , 0 1ii I f    （ ） 通过该约束，将变量 f 限制在一个 n 维的单位立方体中，因此式 ()称为箱限制。 其次，考虑任意校验节点 jєJ，将校验节点 j 邻域 N(j)中势为偶数的子集 (包括空集 ∅)记为 S，所有 S 的集合记为 Ej。 给定一个二进制码比特序列39。 39。 39。 39。 12( , ,..., )nf f f f ， 那么该二进制序列 f’就是校验节点 j 的本地码字。 Ej中的每个 S 对应校验节点 j 的一个本地码字。 对 Ej 中的每个 S 定义一个辅助 LP 变量wjs，变量 wjs 可以看成码字 以此 S 结构满足校验节点 j 的标识 :当 wjs 为 1 时，表示码字以此 S 结构满足校验节点 j:当 wjs 为 0 时，表示码字不以此 S 结构满足校验节点 j。 由于 wjs 为辅助 LP 变量，将其松弛后应同码比特变量一样，满足约束 , 0 1j j sS E w    （ ） 此外，对给定的校验节点 j， Ej中的元素 S 与 j 的本地码字按一一对 应的关系满足式 ()，因此对校验节点 j 的辅助变量应满足以下约束条件 ：。