本发明提供了一种基于预测-修正原对偶内点法的LDPC码的LP译码器，包括线性规划松弛模块、判断模块、迭代方向计算模块、变量更新模块和输出模块，线性规划松弛模块将LDPC码的ML译码问题松弛成LP问题；在判断模块内先计算迭代误差，接着判断迭代误差是否小于误差容忍度并且判断当前迭代次数是否大于最大迭代次数，用以确定下一步进入的模块；迭代方向计算模块用于计算迭代方向；变量更新模块依次完成确定迭代步长和利用迭代步长、迭代方向更新当前变量值的功能，最后将结果反馈给判断模块；输出模块将所求的解进行规整，输出需要的码字。本发明具有译码收敛速度快、误码率性能好的特点。
1.一种基于预测-修正原对偶内点法的LDPC码的LP译码器，其特征是：该LP译码器，包括线性规划松弛模块、判断模块、迭代方向计算模块、变量更新模块和输出模块，各模块间是串行结构；线性规划松弛模块将LDPC的ML译码问题松弛成LP问题，随后导出LP问题的库恩-图克方程，并且对各个变量进行初始化或者宏定义；在判断模块内先计算迭代误差，接着判断迭代误差是否小于误差容忍度并且判断当前迭代次数是否大于最大迭代次数，用以确定下一步进入哪个模块；迭代方向计算模块用于计算迭代方向；变量更新模块依次完成确定迭代步长和利用迭代步长、迭代方向更新当前变量值的功能，最后将结果反馈给判断模块用以重新判断；输出模块将所求的解进行规整，输出需要的码字；其中“线性规划松弛模块将LDPC的ML译码问题松弛成LP问题，随后导出LP问题的库恩-图克方程，并且对各个变量进行初始化或者宏定义”的具体过程是： n T
考虑一个长度为n的规则LDPC码C∈{0,1}，假设发送一个码字y=(y1,y2,...yn) ∈C经过无记忆的有噪信道， 为接收到的符号序列，那么经最大似然译码后的ML码字为： 其中， 为
随 后 定 义 码 字 多 面 体 poly(C)为 码 C 中 所 有 码 字 的 凸 包，即 ，其 中，poly(C)中 的 每一 点 都 对应 一 个 向 量 ，由于多面体的凸点不能由多面体的其他点的组合表示，且任意线性规划问题的最优解总是在多面体的一个凸点处获得，所以ML译码又可表示成下列LP形式： 上述LP问题中，尽管poly(C)由一些有限个数的线性方程表示，但是这种约束条件的数量是LDPC码的码长n的指数，因此(2)式实际上是个穷举NP-Hard问题，具体很高的运算复杂度，为简化其约束条件，将所有码字以及部分非码字作为凸点进行线性松弛，引进一个松弛多面体； m×n
假设LDPC码的校验矩阵为H∈{0,1} ，I={i|1≤i≤n}和J={j|1≤j≤m}分别为变量节点集合和校验节点集合，N(j)为与校验节点j∈J相连的变量节点的集合， 为包含偶数个元素的子集 的集合； 对于每个在Ej中的V，引入一个辅助变量tj,V，如果tj,V=1，表示V中变量节点被赋值为
1； 表示N(j)中所有变量节点被赋值为0，作为一个标识变量，tj,V首先需满足：由于当V中变量节点被赋值为1时，校验方程被满足，所以tj,V能够看作码字满足第j个校验方程的标识，即规定： 接着，为了标识每个fi(1≤i≤n)必须属于这个松弛多面体，规定： 最终，松弛多面体Q就是:对于所有的校验节点j∈J，满足(3)-(6)式的所有点(f,t)的集合，其中，t={tj,V|j∈J,V∈Ej}，并且可以计算出t的维数是表示向下取整；
将poly(C)松弛成松弛多面体Q后，(2)式也能够写成等价的松弛LP形式，如下式所示： 尽管松弛多面体Q能用约束条件式(3)-(6)来表示，但需要一个更直观的等价表T示，把上式中的等式约束和不等式约束展开，并且令c=[r,0,..,0],b=[1,..,1,0,..,0]T T,r=(r1,...,rn),x=[f,t]，就可得下式： T
上式中向量x,c,0,e的维数为ρ1=n+φ，b的维数为ρ2=m+m|N(j)|,A∈R ，并且e和0分别表示全1向量和全0向量； ρ1
引入松弛变量s∈R 将不等式约束化为等式约束及变量不等式约束，得到(8)式的标准线性规划形式： T
根据（9）式，加入对数障碍函数，定义拉格朗日函数Lagrangian： 式中，x、s为原始变量向量，y、w为Lagrangian乘子向量，即对偶变量向量，下标i表示向量的第i个元素，μ为惩罚因子且满足μ>0； 上式的KKT条件就是Lagrangian函数L(x,s,y,w)分别对所有变量x、s、y和w的一阶偏导数Lx、Ls、Ly和Lw为零，即： 令z=μX-1e，则可以把KKT条件写成如下面所示的带有变量不等式的求根方程： 式中，X、Z、S和W分别是以向量x、z、s、和w各元素为对角元构成的对角矩阵；称T TXZe-μe=0和SWe-μe=0为互补松弛条件；由非负向量x、z、s、和w构成的表达式 g=xz+sw是对偶间隙，对偶间隙测量的是向量F的互补松弛条件的l1范数。
基于预测-修正原对偶内点法的LDPC码的LP译码器
技术领域
[0001] 本发明涉及一种LDPC码线性规划译码的译码器，属于移动通信信道编码技术领域。
背景技术
[0002] 高可靠性传输一直是移动通信的目标，而移动衰落信道环境恶劣，长突发错误的产生降低了通信质量，因此有必要采用信道编码方案对传输数据进行冗余保护。低密度奇偶校验(LDPC，Low-Density Parity-Check)码是一种性能非常接近香农(shannon)极限的信道编码方案，具有很强的纠错抗干扰能力。除了置信传播(BP，Blief Popagation)译码算法外，LDPC码还可以使用线性规划(LP，Linear Programming)算法进行译码。尽管LP译码的性能并不优于BP译码，但LP译码码字具有最大似然(ML，Maximun Likelihood)验证性，即不管LP译码输出什么码字，可保证其一定是ML码字；并且LP译码器比BP译码器更易于分析性能。
[0003] LP译码算法是通过把ML译码问题松弛成LP问题，通过解这个LP问题而获得最大似然码字。对于LDPC码字，LP问题中的约束式的数量随着码长的增加而呈指数级增加，因此研究解大型LP问题的算法变得不可或缺。
[0004] 解大型LP问题的一系列算法起源于Dantzig于1949年提出的单纯形(simplex)法，但该系列算法的时间复杂性是非多项式的，在最坏的情况下，算法的迭代次数将随问题维数的增加而呈指数级增加。Karmarkar提出的现代内点算法是一类多项式时间复杂性算法，对于解大型LP问题，不仅比单纯形法更有效，并且计算更简单。其中，预测-修正原对偶内点(PCPDIP，Predictor-Corrector Primal-dual Interior-point)算法是目前求解大型LP问题的最具潜力的一种内点法，该算法收敛迅速，鲁棒性强，对初值的选择不敏感。
[0005] 目前，LDPC码的BP译码器不易于分析性能，特别是在Tanner图出现循环的时候，而采用单纯形算法等其他算法的LP译码器收敛速度慢，需要较多次迭代。
发明内容
[0006] 本发明针对现有LDPC码译码器存在的不足，提供一种具有良好收敛特性和ML验证特性的基于预测-修正原对偶内点法的LDPC码的LP译码器。
[0007] 本发明的基于预测-修正原对偶内点法的LDPC码的LP译码器采用以下技术解决方案：
[0008] 该线性规划译码器，包括线性规划松弛模块、判断模块、迭代方向计算模块、变量更新模块和输出模块，各模块间是串行结构；线性规划松弛模块将低密度奇偶校验(LDPC)码的最大似然(ML)译码问题松弛成线性规划(LP)问题，随后导出LP问题的库恩一图克(KKT：Karush-Kuhn-Tucker)方程，并且对各个变量进行初始化或者宏定义；在判断模块内先计算迭代误差，接着判断迭代误差是否小于误差容忍度并且判断当前迭代次数是否大于最大迭代次数，用以确定下一步进入哪个模块；迭代方向计算模块用于计算迭代方向；变量更新模块依次完成确定迭代步长和利用迭代步长、迭代方向更新当前变量值的功能，最后将结果反馈给判断模块用以重新判断；输出模块将所求的解进行规整，输出需要的码字。
[0009] 本发明利用PCPDIP算法来解LDPC码的松弛LP译码问题，不仅收敛更快，达到同样的误码性能需要的迭代次数少，而且较BP译码器更易于分析性能，特别是在Tanner图出现循环的时候。
附图说明
[0010] 图1是本发明线性规划译码器的模块结构示意图。
[0011] 图2是本发明线性规划译码器的译码器的工作流程图。
[0012] 图3是本发明线性规划译码器的LDPC码译码问题的松弛过程示意图。
[0013] 图4是本发明线性规划译码器的计算迭代方向模块的工作流程图。
具体实施方式
[0014] 本发明的基于PCPDIP算法的LDPC码的线性规划译码器如图1所示，包括线性规划松弛模块、判断模块、迭代方向计算模块、变量更新模块和输出模块，各模块间是串行结构。该译码器的工作流程如图2所示，译码器通过LP松弛模块将LDPC码的ML译码问题松弛成LP问题，导出LP问题的库恩一图克(KKT：Karush-Kuhn-Tucker)方程，接着输入变量0
的初始值ψ、最大迭代次数kmax和误差容忍度ε，设置当前迭代次数k为零，最后将LP问题的KKT方程、变量初始值、最大迭代次数、误差容忍度和当前迭代次数输出到判断模块；
在判断模块中计算迭代误差，如果迭代误差小于误差容忍度或者当前迭代次数大于最大迭代次数时，将当前的变量值直接输出到输出模块，在输出模块中输出结果并终止迭代，否则将KKT方程和当前变量值输出到计算迭代方向模块；计算迭代方向模块利用KKT方程计算出迭代方向Δψ；在变量更新模块中先确定迭代步长α，然后利用迭代步长更新当前变量值，接着内部的迭代次数计数器自动加一记录当前迭代次数，最后输出当前次数和当前变量值到判断模块重新判断是否满足退出迭代条件。
[0015] 下面从各模块出发，详细介绍基于PCPDIP算法的LDPC码的线性规划译码器的译码过程。
[0016] (1)线性规划松弛模块
[0017] 线性规划松弛模块的主要功能是将LDPC码的ML译码问题松弛成LP问题，随后导出LP问题的库恩一图克(KKT：Karush-Kuhn-Tucker)方程，并且对各个变量进行初始化或者宏定义。
[0018] 考虑一个长度为n的规则LDPC码C∈{0，1}n。假设发送一个码字y＝(y1，Ty2，...yn) ∈C经过无记忆的有噪信道， 为接收到的符号序列，那么经最大似然(maximum likelihood，ML)译码后的ML码字为：
[0019]
[0020] 其中， 为接收到的符号序列的对数似然比(LLR)。
[0021] 随 后 定 义 码 字 多 面 体poly(C) 为 码 C中 所 有 码 字 的 凸 包，即其 中，poly(C)中 的 每 一点 都 对 应一 个 向 量由于多面体的凸点不能由多面体的其他点的组合表示，且任意线
性规划问题的最优解总是在多面体的一个凸点处获得，所以ML译码又可表示成下列LP形式：
[0022]
[0023] s.t. f∈poly(C)
[0024] 上述LP问题中，尽管poly(C)可以由一些有限个数的线性方程表示，但是这种约束条件的数量是LDPC码的码长n的指数，因此(2)式实际上是个穷举(NP-Hard)问题，具体很高的运算复杂度。为简化其约束条件，将所有码字以及部分非码字作为凸点进行线性松弛，引进一个松弛多面体。m×n
[0025] 假设LDPC码的校验矩阵为H∈{0，1} ，I＝{i|1 #i n}和J＝{j|1≤j≤m}分别为变量节点集合和校验节点集合，N(j)为与校验节点j∈J相连的变量节点的集合，为包含偶数个元素的子集 的集合。
[0026] 对于每个在Ej中的V，引入一个辅助变量tj，V。如果tj，V＝1，表示V中变量节点被赋值为1； 表示N(j)中所有变量节点被赋值为0。作为一个标识变量，tj，V首先需满足：
[0027]
[0028] 由于当V中变量节点被赋值为1时，校验方程被满足，所以tj，V也可以看作码字满足第j个校验方程的标识，即规定
[0029]
[0030] 接着，为了标识每个fi(1 #i n)必须属于这个松弛多面体，规定：
[0031]
[0032]
[0033] 最终，松弛多面体Q就是：对于所有的校验节点j∈J，满足(3)-(6)式的所有点(f，t)的集合。其中，t＝{tj，V|j∈J，V ∈Ej}，并且可以计算出t的维数是表示向下取整。
[0034] 将poly(C)松弛成松弛多面体Q后，(2)也可以写成等价的松弛LP形式，如下式所示：
[0035]
[0036] s.t.(f，t)∈Q
[0037] 尽管松弛多面体Q可用约束条件(3)-(6)来表示，但我们需要一个更直观的等价T表示。把上式中的等式约束和不等式约束展开，并且令c＝[r，0，..，0]，b＝[1，..，1，T T
0，..，0]，r＝(r1，...，rn)，x＝[f，t]，就可得下式：
[0038] min cTx
[0039] s.t. Ax＝b (8)
[0040] 0≤x≤e
[0041] 上式中向量x，c，0，e的维数为ρ1＝n+φ，b的维数为ρ2＝m+m|N(j)|，并且e和0分别表示全1向量和全0向量。
[0042] 引入松弛变量 将不等式约束化为等式约束及变量不等式约束，得到(8)式的标准线性规划形式：
[0043] min cTx
[0044] s.t. Ax＝b； (9)
[0045] x+s＝e；
[0046] x，s≥0。
[0047] 根据(9)式，加入对数障碍函数，可定义拉格朗日(Lagrangian)函数：
[0048]
[0049] 式中，x、s为原始变量向量，y、w为Lagrangian乘子向量，即对偶变量向量，下标i表示向量的第i个元素，μ为惩罚因子且满足μ＞0。
[0050] 上式的KKT条件就是Lagrangian函数L(x，s，y，w)分别对所有变量x、s、y和w的一阶偏导数Lx、Ls、Ly和Lw为零。即：
[0051]
[0052]
[0053]
[0054]
[0055] x，s，w≥0.
[0056] 令z＝μX-1e，则可以把KKT条件写成如下面所示的带有变量不等式的求根方程：
[0057]
[0058] 式中，X、Z、S和W分别是以向量x、z、s、和w各元素为对角元构成的对角矩阵；称XZe-μe＝0和SWe-μe＝0为互补松弛条件；由非负向量x、z、s、和w构成的表达式g＝T Txz+sw是对偶间隙，对偶间隙测量的是向量F的互补松弛条件的l1范数。
[0059] 基于上述分析，LDPC码的译码问题的松弛过程，可用图3表示。
[0060] 在线性规划松弛模块中将LDPC码的ML译码问题松弛成LP问题，随后导出LP问0 0 0 0
题的库恩一图克(KKT：Karush-Kuhn-Tucker)方程后，输入变量的初始值ψ ＝(x ；z ；s ；
0 0
w ；y)、最大迭代次数kmax和误差容忍度ε，设置当前迭代次数k为零，并将LP问题的KKT方程、变量初始值、最大迭代次数、误差容忍度和当前迭代次数输出到判断模块。
[0061] (2)判断模块
[0062] 判断模块在接收到数据后，先计算迭代误差，即
[0063]
[0064] 随后判断迭代误差是否小于误差容忍度并且判断当前迭代次数是否大于最大迭代次数。如果满足退出迭代条件，即迭代误差小于误差容忍度或者当前迭代次数大于最大迭代次数的话，就将当前的变量值ψk直接输出到输出模块，在输出模块中输出最终结果并终止迭代，否则将KKT方程和当前变量值输出到计算迭代方向模块。
[0065] (3)计算迭代方向模块
[0066] 此模块的作用是计算迭代方向Δψ并把迭代方向Δψ和当前变量值ψ输出到变量更新模块，此模块是整个译码器的核心模块。计算迭代方向Δψ的具体过程如图4所示。
[0067] 本译码器把变量的迭代方向Δψ分为预测方向Δψp＝(Δxp；Δzp；Δsp；Δwp；Δyp)和修正方向Δψc＝(Δxc；Δzc；Δsc；Δwc；Δyc)两部分。两个方向都是通过求解方程F′(ψ)·Δψ＝-F(ψ)而得到，不同的是方程的右边向量，即求解预测方向Δψp时方程右边向量是μ＝0时的KKT方程，即F(ψ)＝[Ax-b；x+s-e；ATy+z-w-c；XZe；SWe]；而求解修正方向Δψc时方程的右边向量是F＝[0；0；0；((ΔXp)(ΔZp)e-μe)；((ΔSp)(ΔWp)e-μe)]。其中F′(ψ)是列向量F(ψ)的雅克比矩阵：
[0068]
[0069] 在计算修正方向Δψc之前，还需确定惩罚因子μ的取值。本发明在迭代初期取一充分大的初始惩罚因子，而后在迭代的过程中以某种方式逐渐减少，并且在迭代的末期μ趋于0，这样PCPDIP算法将在最后收敛于某一最优解。具体方法是根据对偶间隙来确定惩罚因子μ，即
[0070]
[0071] 式中，σ∈(0，1]为向心参数，它取值对PCPDIP算法的性能起着决定性的作用。当σ取较大数值时，算法的数值稳定性较好，但收敛速度较慢，算法侧重考虑可行性；当σ取较小的数值时，算法则主要考虑解的最优性，收敛速度较快，但数值稳定性较差，容易引起振荡，使算法的收敛速度减慢，甚至导致振荡发散。在本发明中，取σ为在0.001至0.2之间的某个数值。
[0072] 对于方程F′(ψ)·Δψ＝-F(ψ)的求解，本发明采用一种比较简单的算法来实现。因为F′(ψ)是高度稀疏的矩阵，所以可以应用高斯块消元法把方程F′(ψ)·Δψ＝-F(ψ)简化成一元线性方程，即从方程F′(ψ)·Δψ＝-F(ψ)中逐步消除Δx，Δz，-1 -1 -1Δs和Δw，并且令D＝(X Z+S W) ，就可得到所谓的正规方程：
[0073]
[0074] 其中，变量Δx，Δz，Δs和Δw可由下面的式子来表示：
[0075]
[0076]
[0077] Δz＝-X-1(ZΔx+rxz)；
[0078] Δs＝-(Δx+rub)；
[0079] Δw＝-S-1(WΔs+rsw)。
[0080] 至于正规方程组(14)的求解，可以先对矩阵ADAT进行乔里斯基(Cholesky)分解，T T将矩阵分解成一个上三角矩阵和其转置矩阵的乘积，即ADA ＝LL，其中L是下三角矩阵。
T
然后再通过求解下面两个式子就能把Δy解出来，而不用求矩阵ADA 的逆：
[0081]
[0082] LΔy＝ω。
[0083] (4)变量更新模块
[0084] 变量更新模块需要依次完成以下四个功能，一是确定迭代步长α，二是利用迭代步长和迭代方向更新当前变量值，三是模块内部的迭代次数计数器自动加一记录当前迭代次数，最后把当前迭代次数和更新后的变量值输出到判断模块重新判断是否满足退出迭代条件。
[0085] 在每次迭代中为了避免求得的解超过边界而采用制约步长法来保证解的内点性质。原始变量的步长αp和对偶变量的步长αd分别为：
[0086]
[0087]
[0088] 使 得 更 新 后 的 原 始 变 量 和 对 偶 变 量都处在非负象限内或者非负象限的边界上。但是仅仅保证(x，z，
s，w)≥0是不够的，还需保证变量(x，z，s，w)在迭代的早期阶段不会太接近于0。否则如果某个变量(如w)为0，那么它的互补松弛条件SWe-μe＝0的牛顿方程SΔWe+WΔSe＝-SWe变成SΔWe＝0，这将导致Δw＝0并且变量w以后永远为0。所以保证变量(x，z，s，w)的正性是非常必要的。
[0089] 为保证变量(x，z，s，w)的正性所采取的措施是将原始和对偶步长一直都乘参数β∈[0.5，1]，直到更新后的变量满足min(xTz，sTw)≥10-5(xTz+sTw)为止。
[0090] 在确定迭代步长以后，用联合迭代方向Δψ＝Δψp+Δψc更新原始变量和对偶变量的当前值，即：
[0091]
[0092] 最后把加一以后的当前迭代次数k和更新后的变量值ψk+1输出到判断模块重新判断是否满足退出迭代条件。
[0093] (5)输出模块
[0094] 因为从判断模块中输出的解不仅包括我们所需要的变量x，还包括其他变量(如z、s、w、y)，所以输出模块的作用是将之前模块所求的解进行分离，输出我们需要的码字。
[0095] 最后的输出结果只取所得解的前ρ1个元素，即输出结果为x＝ψ(1:ρ1)。然后判断所要输出的向量元素是否都为整数，如果某个元素不是整数，把其规整为整数再输出，即如果元素值大于或等于0.5，输出1；否则输出0。最后终止迭代。
