王 彪，慕建君，焦晓鹏，王钟斐

(1. 西安电子科技大学 计算机学院，陕西 西安 710071；2. 宝鸡文理学院 数学与信息科学学院，陕西 宝鸡 721013)

近年来，具有逼近香农限良好性能的低密度校验(Low-Density Parity-Check，LDPC)码受到了研究学者的普遍关注[1-2]． 线性规划(Linear Programming，LP)译码是LDPC码的一种重要译码方法，但其译码复杂度较高[3]． 文献[4]提出了一种基于交替方向乘子法(Alternating Direction Method of Multipliers，ADMM)的LP译码方法，该方法能够降低LDPC码LP译码方法的译码复杂度[4]． 为了进一步降低LDPC码ADMM译码的复杂度，许多学者进行了以下几个方面的研究:简化译码过程，主要包括利用割查找算法(Cut Search Algorithm，CSA)来设计低复杂度的欧几里德投影算法[5]，提出用单纯形(Simplex)替代校验多胞体(Check Polytope)的欧几里德投影算法[6]，直接降低欧几里德投影的次数[7]，基于查表法提出简化的欧几里德投影算法[8]，以及设计不需排序的迭代欧几里德投影算法[9];通过改变消息在变量节点和校验节点间的传递方式，设计高效的消息调度策略[10];利用多核处理器的结构特征优化ADMM译码算法的软件实现[11];通过在LP模型目标函数中加入罚函数[12]、加权罚函数[13]和改进罚函数[14]来设计ADMM惩罚译码方法，此类方法不仅可以降低ADMM译码复杂度，同时能够改善LDPC码的译码性能．

早停止(Early Termination，ET)方法也是一种能够降低LDPC码译码复杂度的有效方法． 当译出正确码字或达到最大迭代次数时，LDPC码译码器会停止译码[15]． 如果译码器能够在早期阶段(即不达到最大译码迭代次数时)停止译码，即判断出正确码字或错误码字，那么就可以节省不必要的译码迭代，从而降低译码的平均迭代次数． 目前，针对LDPC码置信传播(Belief Propagation，BP)译码方法，基于奇偶校验计算的早停止方法[16]和基于后验对数似然比的早停止方法[17]均能够有效降低LDPC码的译码复杂度．

关于LDPC码ADMM惩罚译码算法的研究，学者们目前主要集中在简化欧几里德投影、设计合适的调度策略及优化实现方法等方面来降低其译码复杂度，还未深入开展针对该算法的早停止方法研究． 现有ADMM惩罚译码的停止方法只有两种: 标准的ε规则[4]和HxT=0 的早停止方法[5]． 标准的ε规则将ADMM译码中每次迭代的主残差(Primal Residual)和对偶残差(Dual Residual)分别与ε(ε>0) 比较，若这两个残差值都小于ε，则译码迭代停止; 而HxT=0 的早停止方法主要依据所有校验方程HxT=0 是否满足来确定译码停止． 通过计算LDPC码译码迭代过程中码字所满足的校验约束个数，设计了LDPC码ADMM惩罚译码的一种早停止方法，该方法能够在早期阶段判断出错误码字而停止译码． 仿真结果表明，所设计的早停止方法能够在低信噪比区域降低LDPC码ADMM惩罚译码的平均迭代次数，且其译码性能几乎没有损失．

1 基于ADMM的LPDC码惩罚译码

设LDPC码C的校验矩阵为m×n的矩阵H，其对应的Tanner图中所有变量节点集合I= {1，2，…，n}，所有校验节点集合J= {1，2，…，m}． 设集合Nv(i)表示与变量节点vi相关联的所有校验节点集合，而集合Nc(j)表示与校验节点cj相关联的所有变量节点集合． 令dvi= |Nv(i)|，表示变量节点vi的度数；dcj= |Nc(j)|，表示校验节点cj的度数．

假设发送端将码字x={xi∈{0，1}|i∈I}经过加性高斯白噪声(Additive White Gaussian Noise，AWGN)信道发送后，接收端接收到的序列r= {ri|i∈I}，r对应的对数似然比向量记为γ= {γi|i∈I}，其中γi= log(Pr(ri|0)/Pr(ri|1))，Pr(·)表示括号内代表的事件发生的概率． 通过引入辅助变量zj∈Rdcj(j∈J) 可以得到LP译码数学模型为[4]

(1)

其中，校验多胞体Pdcj表示所有长度为dcj且含有偶数个1的二进制向量构成的凸包，dcj×n二进制转换矩阵Tj选出x中与第j校验节点所关联的dcj个分量．

2 ADMM惩罚译码的早停止方法

2.1 码字所满足校验约束个数分析

(2)

其中，1T表示长度为m的全1行向量．

图1 (576， 288)LDPC码ADMM惩罚译码迭代时10个码字所满足的校验约束个数变化规律

(3)

2.2 早停止方法设计

所设计的LDPC码ADMM惩罚译码的早停止方法可以概括为:

2.3 计算复杂度分析

表1 每次迭代中3种停止方法的计算复杂度比较

表1中，“*”表示在迭代过程中文中的早停止方法在最坏情况下进行的计算复杂度分析．

由此可见，文中所设计的早停止方法的计算复杂度低于标准ε规则的计算复杂度，而该早停止方法在最坏情况下的计算复杂度略高于HxT=0 的早停止方法的计算复杂度(假设比较运算和加减法运算的计算复杂度相近)．

3 仿真实验

以IEEE 802.16e标准中码率为0.5的(576， 288)LDPC码C1和码率为0.75的 (1 152， 288)LDPC码C2为例，从译码平均迭代次数和译码性能(误帧率)两个方面，对所设计的LDPC码ADMM惩罚译码的早停止方法与现有ADMM惩罚译码的标准的ε规则及HxT=0 的早停止方法进行了比较．仿真实验中，ADMM惩罚译码器采用l1罚函数进行译码，所涉及的罚参数按照文献[12]中的方法进行优化选择，且最大迭代次数、译码容差值(Error Tolerance Value)和超松弛参数(Over Relaxation Parameter)分别取40、10-5和1.9．

3.1 参数选择

下面给出所设计的LDPC码ADMM惩罚译码的早停止方法所涉及的检测错误码字的比较阈值T、统计计数器Ncounter的起始迭代次数Imin及检测错误码字的起始迭代次数Idec这3个关键参数的选择方法．

图2 T变化时码C1的译码平均迭代次数和误帧率比较

首先，取Imin=15和Idec=20来研究比较阈值T的变化对译码效果的影响． 图2给出了T依次取260、270和280时，码C1采用所设计早停止方法的译码平均迭代次数和译码性能比较． 从图2可以看出，采用3种不同T值时，在高信噪比区域的译码平均迭代次数大致相同，而在低信噪比区域T=280 时，译码的平均迭代次数最低，然而其译码误帧率反而最差． 当T=260 和T=270 时的译码平均迭代次数基本相同，而在低信噪比区域T=270 时的误帧率较好． 因此，选取T=270 作为所设计早停止方法的参数值．

图3 Imin和Idec变化时码C1的译码平均迭代次数和误帧率比较

其次，取T=270来研究Imin和Idec的变化对译码效果的影响．针对3组不同参数值 (Imin=10，Idec=15)，(Imin=15，Idec=20) 和 (Imin=20，Idec=25)，图3给出了码C1采用所设计的早停止方法的ADMM惩罚译码时，译码平均迭代次数和译码性能比较． 由图3可以看到，Imin和Idec的3组不同取值的译码平均迭代次数在高信噪比区域大致相同，而在低信噪比区域有所不同，其中取参数值 (Imin=20，Idec=25) 时译码的平均迭代次数最高，取参数值 (Imin=10，Idec=15) 时译码的平均迭代次数最低; 3组不同取值的误帧率在高信噪比区域几乎相同，而在低信噪比区域选取 (Imin=15，Idec=20) 的误帧率较好． 因此，选取 (Imin=15，Idec=20) 作为所设计早停止方法的参数值．

3.2 平均迭代次数和译码性能比较

适当选择所设计早停止方法的参数后，以码C1和码C2为例，比较了所设计的LDPC码ADMM惩罚译码的早停止方法、标准的ε规则以及HxT=0 的早停止方法3种停止方法的平均迭代次数和误帧率．

针对码C1所设计的早停止方法取定参数T=270、Imin=15和Idec=20，图4给出了所设计的早停止方法与标准的ε规则以及HxT=0 的早停止方法的译码平均迭代次数和误帧率的比较． 从图4看出，译码时利用3种停止方法的误帧率大致相同，而其平均迭代次数则明显不同． 在较低信噪比区域HxT=0 的早停止方法的平均迭代次数高于标准的ε规则，这是因为较低信噪比区域错误码字通常较多，而HxT=0 的早停止方法需要更多的迭代次数才能判定错误码字． 而所设计的早停止方法克服了HxT=0 的早停止方法的这一缺点，在较低信噪比区域可明显降低LDPC码译码的平均迭代次数，且译码性能几乎没有损失．

图4 码C1采用3种停止方法的译码平均迭代次数和误帧率比较

图5 码C2采用3种停止方法的译码平均迭代次数和误帧率比较

类似地，对于码C2所设计早停止方法的参数依次取T=270，Imin=15和Idec=20．图5给出了采用3种停止方法的译码平均迭代次数和误帧率的比较．从图5可以看出，与现有两种停止方法相比较，所设计早停止方法在较低信噪比区域降低了译码的平均迭代次数，且译码性能几乎没有损失．

4 结 束 语

通过计算迭代译码中码字所满足的校验约束个数，设计了一种能够在LDPC码ADMM惩罚译码早期阶段检测出错误码字的早停止方法． 针对IEEE 802.16e标准中两个典型LDPC码的仿真实验结果表明，与现有ADMM惩罚译码的标准的ε规则和HxT=0 的早停止方法相比较，所设计的早停止方法能够在几乎没有损失译码性能的同时可降低LDPC码低信噪比区域译码的平均迭代次数． 因此，该方法适合在噪声较大环境下作为LDPC码ADMM惩罚译码的停止方法来提高译码收敛速度．