多进制低密度奇偶校验码的扩展最小和译码算法研究

庞 臣，徐家品

（四川大学 电子信息学院，四川 成都 610065）

低密度奇偶校验码LDPC（Low Density Parity Check）是目前信道编码领域公认的性能优异，形式简单，应用前景广阔的一种好的线性分组码。LDPC码的性能最逼近香农限，因此被认为是未来通信领域中最具竞争力的信道编码。自从1962年GALLAGER R G[1]博士在其学位论文中首次提出LDPC码的相关概念，并用当时条件局限的方法证明了其优异的纠错性能之后，学术界就展开了针对LDPC的卓识有效的研究，并取得了极大的成果。至20世纪末，二进制LDPC码已经成为了非常成熟的信道编码。除了理论方面取得了巨大成就，二进制LDPC在应用领域更是大放异彩。欧洲通信标准委员会（ETSI）推出的DVB-S2标准中，信道编码已经采用LDPC码。2010年10月10日，清华大学研制的低密度奇偶校验码遥测信道编码试验按计划实施，“嫦娥二号”卫星上LDPC编码器以及喀什测控站、青岛测控站LDPC遥测译码终端状态良好、运行正常，遥测数据接收解调正常，试验取得成功。此次试验成功是LDPC信道编码技术首次应用于我国航天领域。LDPC码优异性能成为未来第四代（4G）移动通信系统最强有竞争力的候选标准之一。

1998年，DAVEY M C 和 MACKAY D J C[2]提出了基于 GF（q）域的 LDPC码，由此开启了 LDPC码研究的一个新领域。定义在GF（q）上的多进制LDPC码的双向图与二进制的相似，但变量节点有q（q=2b）个可能取值，校验节点的约束限制也比二进制检验节点更复杂。在原信道不变的情况下，多进制的一个符号需要b个二进制比特。相比之下，无论是在计算复杂度，还是存储容量及传输占用时间等方面，多进制LDPC码都比二进制LDPC码有更大的难度。尽管如此，由于其具有无可比拟的特性，多进制的研究都是极有理论和工程意义的。

本文简要介绍多进制LDPC码的几种常见译码方法，分析各种方法的利弊，并利用多种形式重点介绍扩展最小和算法。

1 常见译码算法

LDPC码有很多种译码方法。根据消息迭代过程中传送消息的形式不同，可以将LDPC码的译码方法分为硬判决译码和软判决译码两种。硬判决译码设定阈值来判断输出，软判决译码通过最大后验概率信息决定可能的信源值。硬判决译码计算简单，但是误码率高；软判决译码计算复杂，但是性能优异。实践中，倾向于选择软判决译码。目前，多进制LDPC码的软判决译码方法主要有信度传播BP（Belief Propagation）算法、最小和MS（Min-Sum）算法、Normalized BP-based算法以及 LP算法。在此介绍前两种算法。

信度传播算法是由MACKAY P J C和NEAL R M[3]共同提出的一种迭代译码算法，简称BP算法。BP算法迭代过程如图1所示。BP算法的核心思想在于利用接收到的软信息在变量节点和校验节点之间进行迭代运算，从而获得最大编码增益。该算法在迭代过程中会对结果作出判决。如果译码达到预定标准，译码计算立即结束而不再继续进行固定次数的迭代，大大节省了译码时间，降低了运算复杂度。而若算法在到达预先限定的最大迭代次数后仍未找到有效的译码结果，译码器将宣告译码失败。BP算法是一种并行译码算法，在硬件中的并行实现能够极大地提高译码速度。LDPC码利用BP译码算法能够得到很好的译码性能，但是由于大量的乘法运算，采用BP算法的硬件复杂性较高。

图1 BP算法迭代译码过程

最小和译码算法是由WYMEERSCH H[4]等人根据BP译码算法提出的一种对数域BP算法，简称MS算法。其基本思想与BP算法无异，只是在概率信息的表示形式上采用对数似然比，将BP算法中的诸多乘法运算转换为对数域上的加法运算，大大降低了运算复杂度、减少了运行时间且不需要对信道噪声进行估计，但其性能也有一定程度的降低。

上述各译码虽然在不同的时期不同的应用点各自具有很大优势，但复杂度和实现难度依然很高，研究人员仍然在不断改进和创新译码工作，推动着LDPC学科整体进展。

2 EMS算法

2007年，DECLERCQ D和FOSSORIER M[5]提出一种扩展最小和 EMS（Extended Min-Sum）算法，简称 EMS算法。该算法在最小和译码算法基础上，提出一种缩短传递对数似然比概率信息数量的译码方法，大大降低了计算复杂度，在现有多进制LDPC码译码算法中受到推崇。

假设经过信道传输后在信宿端收到的对数似然比LLR消息向量是：

其中，

LV表示变量V中符号 αk的对数似然值，而P（αk）表示其概率测度值。

EMS算法首先将LV按照降序排列，然后顺次截取LV中LLR值最大的项，得到处理后的消息向量U，LLR最大值即是U[1]，最小值是U[nm]。用Uq表示向量U对应的GF（q）元素值，用γU=U[nm]-δ表示其余域元素对应的似然值，其中δ是一个经过优化的固定偏移值。

例如：GF（8），nm=4

某变量节点接收到的LLR值为：

降序排列后：

对应的 GF（8）元素值为：

截取到的前nm个LLR组成的向量U为：

截取信息后对应的 GF（8）元素向量Uq为：

剩余域元素对应的似然值γU为：

记UVC变量为节点V向校验节点C传递的消息向量，UCV为校验节点C向变量节点V传递的消息向量。EMS具体步骤如下：

（1）初始化（Initialization）

将UVC初始化为信道初始消息向量LV中最大的nm项。

（2）置换步骤（Permutation Step）：有限域元素顺序通过置换重新排列

将各项与该置换节点的 GF（q）域元素相乘，从而完成对消息向量的置换，如图2所示。

图2 置换步骤示意图

其中，实心矩形为置换节点，置换节点左边箭头上实心圆形代表阶段后的LLR值对应的GF（q）值，同理，右边为置换后GF（q）值，手绘曲线箭头所指为实际置换过程。

（3）横向步骤（Horizontal Step）：检验节点更新

采用前向后向算法，将度为dc的校验节点更新分解为2（dc-2）个校验节点基本步骤。记校验节点基本步骤的输入消息向量为V和I，输出消息向量为U，则对应的符号索引向量分别为Vq、Iq和Uq。

（4）逆置换步骤（Reverse Permutation Step）：逆置换元素顺序

（5）纵向步骤（Vertical step）：变量节点更新

采用前向后向算法，将度为dv的变量节点更新分解为2（dv-2）个变量节点基本步骤。记变量节点基本步骤的输入消息向量为和，输出消息向量为，其对应的有限域值为定义长度为 2nm的向量 Y=[Y[0]，Y[1]，…Y[2nm-1]]，

其中，

输出消息向量则由Y中最大的nm项按降序排列得到。

其过程如图3所示。其中，黑色实心圆代表LLR值，空心圆代表对应的GF（q）值。该变量节点度为dv，故有dv-1个输入信息，经过如上计算规则计算以后又恢复出q个值，再重新降序排列，截断后在下一次循环迭代中初始化（若有可能）。

图3 变量节点更新过程

（6）将变量V判决为消息符号索引向量Uq首项，校验方程满足或到达最大迭代次数则结束译码，否则返回步骤（2）。

随后，VOICILA A等人[6]从实现角度对EMS算法进行了改进，将译码的实数加法运算复杂度进一步下降。如今，译码算法界众多研究人员依然致力于对此算法的研究，希望有所突破。

当前，EMS在多进制LDPC码译码算法中具有举足轻重的地位，所有最新的研究成果均是围绕此算法进行的改进和实现。无论谁想要在多进制LDPC译码算法上有所作为，都必须深刻研究EMS算法。由此可见，EMS算法的影响力有多么泛和深刻。

3 LDPC研究方向

当前，对LDPC码的研究主要集中在检验矩阵的构造、译码算法的优化、性能分析和改进以及在实际系统中的应用4个方面。即便如此，LDPC仍然有许多研究方向。

（1）多进制LDPC码的校验矩阵的构造方法依然存在很大的难度。现有众多方法应用范围过于狭窄，往往是满足了一方面的要求，而在其他地方则差强人意。无论是结构化构造还是随机构造，对于硬件实现总有不理想之处。追求完善、系统的检验矩阵的构造方法是学术界的动力。

（2）多进制 LDPC码的译码方法对于 EMS算法依赖过于严重，人们的认知眼界和研究思路很难从中跳出，长期以往，很难有大的突破和创新。如何能够将译码复杂度降下来，让性能提升，依然是永恒的愿景。

（3）多进制 LDPC编码系统的联合优化设计，将编码技术与调制技术、空时编码技术、OFDM技术结合进行性能优化是当前及将来的发展方向之一。

（4）尽快将更多的研究成果转化为实际应用，诸如深空卫星通信、第四代（4G）移动通信系统及深海通信等。

本文介绍了多进制LDPC常见的两种译码算法，然后依据原算法以及个人的理解，利用图解的方式重点分析了EMS算法的具体步骤以及需要注意的问题。通过分析，就能够理解EMS在存储和计算复杂度中较其他算法具有明显优势。最后对多进制LDPC码的研究方向进行了简要分析和预测。

[1]GALLAGER R G.Low-densityparity-checkcodes[D].Cambridge， Massachusetts： M.I.T.Press， 1963.

[2]DAVEY M C，MACKAY D J C.Low density parity check codes over GF（q）[C].Information Theory Workshop， 1998：70-71.

[3]MACKAY D JC， NEALR M．NearShannonlimit performance of low density parity check codes[J]．Electronic Letters，1996，32（18）.

[4]WYMEERSCHH， STEENDAMH， MOENECLAEYM.Log-domain decoding of LDPC codes over GF（q）[C].2004 IEEE International Conference on Communications，2004（2）：772-776.

[5] DECLERCQ D，FOSSORIER M.Decoding algorithms for nonbinary LDPC codes over GF（q）[J].IEEE Transactions on Communication， 2007，55（4）：633-643.

[6]VOICILA A， DECLERCQ D， VERDIER F， et al.Lowcomplexity decoding for non-binary LDPC codes in high orderfields[J].IEEE Transactions on Communication，2010，58（5）：365-1375.

[7]林伟.多元LDPC码：设计、构造与译码[D].西安：西安电子科技大学，2012.

[8]袁东风，张海刚.LDPC码理论与应用[M].北京：人民邮电出版社，2008.