基于竞争机制的LDPC码串行最小和算法*

梁 溪，龙翔林，章恩友，杨 帆

（1.电子科技大学 通信与信息工程学院，四川 成都 611731；2.宁波迦南电子有限公司，浙江 宁波 315000）

基于竞争机制的LDPC码串行最小和算法*

梁 溪1，龙翔林2，章恩友2，杨 帆1

（1.电子科技大学 通信与信息工程学院，四川 成都 611731；2.宁波迦南电子有限公司，浙江 宁波 315000）

针对译码模块设计成本和功耗的问题，提出了一种LDPC码串行最小和算法。该算法是一种采用权重因子的基于变量节点更新的串行算法，它基于竞争机制来更新变量节点对校验节点消息集合中的最小值。与传统串行算法相比，在不损失性能的前提下，它大幅降低了译码所需的复杂度。另一方面，与并行最小和算法相比，新算法不仅大幅降低了所需存储量，而且性能也有一定的提升，复杂度只有略微增加。

电力线载波通信；串行最小和算法；低密度奇偶校验码；迭代译码；归一化权重因子

0 引言

随着信息化的发展，人们对低密度奇偶校验(Low Density Parity Check，LDPC)码有了重新的认识。LDPC码作为高效的信道纠错编码，具有较低的译码复杂度，系统吞吐量较大，已在电力线载波（Power Line Carrier，PLC）通信、第三代和第四代无线移动通信等方面得到了广泛应用[1]。相对于 turbo译码算法[2]，采用 LDPC编码和置信传播(Belief Propagation，BP)译码算法更受人们的青睐[3]。但是BP算法存在对硬件存储量的需求较大以及对信道情况较为敏感等问题。人们更趋向于鲁棒性更好和复杂度更低的译码算法，最典型的就是并行最小和(Parallel Min-Sum，PMS)算法[4]。这类算法在实现中只需要加法和比较运算，且不需要知道信道情况，可以获得性能和复杂度的良好折衷。考虑到PMS算法前后两次迭代译码过程中，参与信息交换的置信度被过高估计，文献[5]通过引入归一化权重因子来减少这种负面影响，使其性能逼近最优BP算法的性能，可称之为归一化并行最小和(Normalized Parallel Min-Sum，N-PMS)算法。随着研究的深入，人们提出了不同的译码机制来提高置信传播的效率，其中较为重要的一类是采用权重因子的串行最小和(Normalized Serial Min-Sum，N-SMS)算法[6]。在电力线载波通信中，收发模块通常采用具有低存储量和低复杂度的编、译码算法。N-SMS算法虽然在存储上较N-PMS算法有一定减少，但N-SMS算法由于每次迭代都采用min操作来更新最小值，复杂度相对较高。

为实现可靠通信，并综合考虑实现成本、器件功耗以及处理复杂度的问题，针对N-SMS算法提出了一种基于竞争机制的归一化的串行最小和(Normalized Competitive Min-Sum，N-CMS)算法。该算法在按照自然顺序更新变量节点对校验节点消息的同时，还利用竞争关系更新变量节点对校验节点消息集合中的最小值。与文献[6]类似的是，N-CMS在更新某一变量节点时，同时利用了与该节点之前已更新的软信息和该节点之后还未更新的软信息，所以N-SMS算法与N-CMS算法的性能相同。不同的是，N-CMS通过采用竞争机制来更新属于同一校验式的变量节点集合中的最小值，避免了文献[6]中采用min操作的复杂运算，并进一步减少了存储量。

1 N-PMS算法简介

为了简化叙述，该文沿用文献[7]中的部分符号定义。设m和n分别表示校验节点和变量节点，H为LDPC码对应的校验矩阵，当变量节点和校验节点有边相连接时，则hmn=1，它是H中的第m行和n列的元素。N(m)={n|hmn=1}表示参与校验方程m的变量节点的集合，N(m) 为 N(m)中除去元素 n后构成的集合；相应地，M(n)={m|hmn=1}表示与变量节点 n相连的校验节点的集合，M(n)m为集合M(n)中除去元素 m后构成的集合。设是从变量节点n传递给校验节点m的软信息，表示在给定接收序列y，并且除了第m个校验方程外，其他与 n相关的校验方程都满足的条件下，xn=x的概率；是由校验节点m传递给变量节点n的软信息，表示在xn=x，且参加第m个校验方程的除n外的其他变量节点的概率 Qn~m已知的条件下，该校验方程成立的概率，其中∈N(m) 。

设 s为长为 N的编码序列 x=[x1，x2，…，xN]T经过BPSK调制后的信号，g是均值为 0、方差为 σ2的高斯噪声。设s经过AWGN信道后的接收序列为y=[y1，y2，…，yN]T，BP译码后的序列为。其中：

定义变量信息、校验信息和后验信息分别为：

传统的N-PMS算法可归纳如下：

初始化：令先验信息L(Pn)=yn，L(Qnm)=L(Pn)

步骤1：判断是否达到设定的最大迭代次数 MT，若是则程序结束；否则执行步骤(2)。

步骤2：对m=1，2，…，M和所有的n∈N(m)计算：

在上式中，αnm=sign(L(Qnm))和 βnm=abs(L(Qnm))，分别表示 L(Qnm)的符号和绝对值，λ为归一化权重因子，满足0≤λ≤1。

步骤3：对n=1，2，…，N和所有的m∈M(n)计算：

步骤 4：对译码软信息进行硬判决，若 L(Qn)＜0，则n=1，否则n=0，n=1，2，…，N。若 HT=0，则译码成功，程序结束，否则转到步骤(1)。

2 N-CMS算法的原理与实现步骤

基于文献[4]的思想，设变量节点n更新前与更新后L(Qnm)的绝对值分别为 βnm和，γ1和 γ2是集合 n∈N(m)所有βnm中最小的两个值，不失一般性令 γ1≤γ2。当 βnm完成到的更新后，使得 n∈N(m)集合在 βnm更新前求得的γ1和γ2可能并不是当前最小的两个值，例如存在的情况，此时的两个最小值应为和 γ1。倘若不对γ1和γ2进行更新，则会导致的值不准确，使得性能和收敛速率都会受到影响。但若要采用min操作来更新γ1和γ2，则计算复杂度会较高。如在文献[6]中，对于码率1/2的规则 (N，J，2J)LDPC码，N-SMS在每次迭代中操作需要次加法运算，当J较大时，简化N-SMS算法的复杂度是很有必要的。

本文在更新 βnm的过程中，同时利用和 γ2三者间的关系来更新属于校验式m的两个最小值γ1和 γ2。若小于 γ1，则在集合 n∈N(m)中最小值为，次最小值才为 γ1；若大于 γ1但小于 γ2，则在集合 n∈ N(m)中最小值仍为γ1，次小值 γ2需更新为；若大于γ2，则集合中最小的两个值仍为γ1和γ2，不发生变化。以上的竞争机制可简单概括为：若 β′nm＜γ1，则令 γ1=，γ2=γ1；若，则 γ1不变，；若γ2，则γ1和γ2都保持不变。N-CMS算法可描述为：

步骤1：判断是否达到设定的最大迭代次数MT，若是则程序结束；否则按照 n=1，2，…，N的顺序更新变量节点对校验节点的消息，执行步骤(2)。

步骤2：对特定的n和每一个m∈M(n)按照式(5)计算L(Rmn)，此处的 min操作由γ1和 γ2取代。

步骤 3：对特定的 n和每一个 m∈M(n)依据式(6)、式(7)算出 L(Qn)和 L(Qnm)，由更新后的 L(Qnm)得出后，再根据竞争模式更新γ1和γ2。

步骤4：若n≤N，对译码软信息进行硬判决，若L(Qn)＜0，则n=1，反之n=0，n=n+1转到步骤(2)。否则执行步骤(5)。

3 复杂度及存储量分析

表1 三种算法

4 算法仿真与测试

仿真中选取码率1/2的(512，3，6)规则LDPC码通过AWGN信道，译码分别采用N-PMS算法和N-CMS算法。为了使得信息得到充分的传播，在仿真中令最大迭代译码次数MT=30。下面从归一化权重因子的选取、误比特率(Bit Error Rate，BER)、误帧率(Frame Error Rate，FER)、收敛速率和译码平均译码复杂度几个方面来进行对比分析。

为简化讨论，此处利用蒙特卡罗方法来获得N-PMS和N-CMS的归一化权重因子。如图1和图2所示，两者都在λ=0.8时表现出最佳的性能，因此将λ=0.8作为最佳归一化权重因子用于之后的仿真。

图1 采用N-PMS算法在1 dB、2 dB和3 dB时，误比特率与归一化权重因子的关系

图2 采用N-CMS算法在1 dB、2 dB和3 dB时，误比特率与归一化权重因子的关系

图3 和图4分别对比了PMS、N-PMS、CMS和N-CMS系统的BER和FER性能，按照是否引入归一化权重因子分为两组，即PMS和N-PMS，CMS和N-CMS。可以看出，不论哪一组归一化算法均比非归一化的算法性能要好得多，约有0.5～0.7 dB的性能差距。此外，即使都是归一化算法，N-CMS较N-PMS也有0.1～0.2 dB的性能提升。

图3 误比特率比较

图4 误帧率比较

由图5可知，CMS所需的平均迭代译码次数要少于PMS，类似的，N-CMS所需的平均迭代译码次数也少于N-PMS。从图6可以得出，N-CMS在中低信噪比时译码复杂度较N-SMS有明显的优势，但比N-PMS略高；在高信噪比时N-CMS与N-PMS复杂度接近，而且两者都比N-SMS的复杂度低。

图5 所需平均迭代译码次数

5 结论

本文提出了一种按照变量节点更新的归一化串行最小和算法——N-CMS。N-CMS算法采用竞争机制实时更新变量节点对校验节点消息集合中最小的两个值，它在保持与N-SMS算法相同性能的前提下大幅降低了运算量。相对N-PMS算法而言，N-CMS算法不论是在收敛速度，还是在译码性能上都更有优势，其复杂度只有略微增加。最为重要的是N-CMS算法具有极低的存储需求，尤其是在电力线载波通信所需的译码模块的设计中，表现出巨大的实用价值。

图6 N-PMS、N-SMS和N-CMS所需平均复杂度比较

[1]DEVELI I，KABALCI Y.Analysis of the use of different decoding schemes in LDPC coded OFDM systems over indoor PLC channel[J].Electronics&Electrical Engineering，2014，20(1)：76-80.

[2]BERROU C，GLAVIEUX A，THITIMAJSHIMA P.Near Shannon limit error-correcting coding：turbo codes[C].In ICC93，1993(5)：1064-1070.

[3]MACKAY D J C.Good error-correcting codes based on very sparse matrices[J].IEEE Trans.Inform.Theory，1999 (45)：399-431.

[4]FOSSORIER M P C，MIHALJEVIC M，IMAI H.Reduced complexity iterative decoding of low density parity check codes based on belief propagation[J].IEEE Trans.Commun，1999(47)：673-680.

[5]CHEN J，FOSSORIER M P C.Decoding low-density parity check codes with normalized APP-based algorithm[C].Proc. IEEE Global Communications Conference，2001，9(1)：1026-1030.

[6]刘原华，王新梅，胡树楷，等.一种改进的卷积LDPC码置信传播译码算法[J].西安电子科技大学学报，2009，36 (3)：424-428.

[7]杨帆，罗振东，田宝玉.改进的LDPC串行译码[J].北京邮电大学学报，2008，31(4)：130-134.

A serial min-sum algorithm for LDPC codes based on competitive scheme

Liang Xi1，Long Xianglin2，Zhang Enyou2，Yang Fan1
（1.University of Electronic Science and Technology of China,Chengdu 611731，China；2.Ningbo Jianan Electronics Co.，Ltd，Ningbo 315000，China）

Considering the designing costs and the power consumption issues in the decoding module,a serial min-sum algorithm for LDPC codes is proposed.The new algorithm is a type of variable-to-check message updating algorithm using normalized factor, it updates the minimum value among the variable-to-check messages based on a competitive scheme.Compared to the conventional normalized serial min-sum algorithm,it reduces the decoding complexity significantly without any performance loss.On the other hand,compared with the normalized parallel min-sum algorithm,the new approach not only reduces amount of memory,but also has some performance improvement with a little complexity increased.

power line carrier communication；serial min-sum algorithm；low density parity check codes；iterative decoding；normalized factor

TN911.22

A

10.16157/j.issn.0258-7998.2015.11.025

梁溪，龙翔林，章恩友，等.基于竞争机制的LDPC码串行最小和算法[J].电子技术应用，2015，41(11)：89-92，100.

英文引用格式：Liang Xi，Long Xianglin，Zhang Enyou，et al.A serial min-sum algorithm for LDPC codes based on competitive scheme[J].Application of Electronic Technique，2015，41(11)：89-92，100.

2015-07-10)

梁溪（1992-），男，硕士研究生，主要研究方向：通信与信息系统。

国家自然科学基金（61301272）；四川省应用基础研究计划（2014JY0037）；中央高校基金（ZYGX2013J008）

龙翔林（1971-），男，硕士，总工程师，主要研究方向：用电信息采集系统及电力线载波通信。