摘  要： 综述了多进制LDPC码的几种常用译码算法，重点讲解分析了其中的扩展最小和算法，并采用对比的方法证明其优越性。
关键词： 多进制；低密度奇偶校验码（LDPC）；扩展最小和算法（EMS）；译码算法

　低密度奇偶校验码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算法的硬件复杂性较高。

　最小和译码算法是由WYMEERSCH H[4]等人根据BP译码算法提出的一种对数域BP算法，简称MS算法。其基本思想与BP算法无异，只是在概率信息的表示形式上采用对数似然比，将BP算法中的诸多乘法运算转换为对数域上的加法运算，大大降低了运算复杂度、减少了运行时间且不需要对信道噪声进行估计，但其性能也有一定程度的降低。
　上述各译码虽然在不同的时期不同的应用点各自具有很大优势，但复杂度和实现难度依然很高，研究人员仍然在不断改进和创新译码工作，推动着LDPC学科整体进展。
2 EMS算法
　2007年，DECLERCQ D和FOSSORIER M[5]提出一种扩展最小和EMS（Extended Min-Sum）算法，简称EMS算法。该算法在最小和译码算法基础上，提出一种缩短传递对数似然比概率信息数量的译码方法，大大降低了计算复杂度，在现有多进制LDPC码译码算法中受到推崇。
　假设经过信道传输后在信宿端收到的对数似然比LLR消息向量是：

　随后，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-density parity-check codes[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 J C， NEAL R M． Near Shannon limit performance of low density parity check codes[J]． Electronic Letters，1996，32（18）.
[4] WYMEERSCH H， STEENDAM H， MOENECLAEY M. 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. Low-complexity decoding for non-binary LDPC codes in high order fields[J]. IEEE Transactions on Communication， 2010，58（5）：365-1375.
[7] 林伟.多元LDPC码：设计、构造与译码[D].西安：西安电子科技大学，2012.
[8] 袁东风，张海刚.LDPC码理论与应用[M].北京：人民邮电出版社，2008.