LDPC码置信传播译码时序研究

南京信息工程大学电子与信息工程学院 周 华 李诚谦 余嘉昊

LDPC码置信传播译码时序研究

南京信息工程大学电子与信息工程学院 周 华 李诚谦 余嘉昊

本文对低密度奇偶校验（LDPC）码置信传播译码的三种基本时序安排进行详细介绍，包括洪泛译码、串行译码、动态译码。对各译码时序的原理、收敛速度、误码率等进行阐述和比较，并提出一些可行性改进措施来提高LDPC码的译码性能。

LDPC码；置信传播；译码时序

1. 低密度奇偶校验码介绍

低密度奇偶校验码（LDPC码） 由二进制稀疏矩阵定义，矩阵中大部分元素是 0，剩余部分元素为 1。LDPC码的一个重要研究成果是1981年著名学者Tanner提出了用图模型来表述LDPC码的理念。该模型根据LDPC码的校验矩阵中1的位置提出双向二分图。通过二分图可构造性能良好的 LDPC 码，支持并行译码，大大降低译码复杂度。Mackay 和 Neal 利用二分图对 LDPC 码性能进行了深入研究，发现采用置信传播（belief propagation）译码算法的 LDPC码译码性能逼近香浓极限。

2. LDPC码置信传播译码算法

假设一个（N,K）的LDPC码，校验位数量为M=N-K，则校验矩阵H是一个M*N的矩阵。矩阵H的二分图如图1所示。图1下方的N个圆圈节点表示N个码字符号，称作变量节点；上边的M个方形节点表示M个校验方程，称作校验节点。当变量节点和校验节点存在于同一个校验方程时，就用边将两者连接。和每个节点相连的边的个数称作该节点的度。从某个节点出发再次回到该节点所经历边的个数即为环的长度，其中最短环所经过的边的数量构成二分图的围长。如图1，黑色加粗的边构成了一个围长等于4的短环。我们构造矩阵的时候尤其关注最小围长，因为它直接关系到LDPC码的译码性能。

图1 LDPC码的校验矩阵和二分图

3. 置信传播的调度安排

LDPC码最常用的译码算法是置信传播。理论分析表明，如果与其校验矩阵对应的二分图无环路存在，则BP算法会收敛于全部比特的后验概率，也是LDPC码具有良好性能的原因之一。

通常评估一种译码算法有三个指标：译码速率、译码复杂度和译码性能。译码器通过迭代算法更新消息，直到满足停止条件。迭代算法的本质是对二分图中的信息进行调度。调度是指置信传播过程中变量节点和校验节点之间的消息更新次序。下面介绍几种常见的时序调度译码算法：

第一，洪泛机制是标准置信传播算法釆取的调度策略，属于并行消息传递机制，也是最普遍最基本的调度策略。它的做法是：在每一轮迭代过程中，所有校验节点同时收集从相邻变量节点传来的消息，更新完毕后，再利用已更新过的所有校验节点的消息同时去更新所有变量节点的消息，最后每个变量节点根据判决条件进行判决，如此反复，直到满足停止条件。这种消息传递机制最为简单，译码速率也很高，但性能并不是最优的。研究标明，洪泛往往需要较大的迭代次数才能收敛，从而引起高运算量以及很长的译码时延。泛洪的置信传播调度方式如图2所示。

图2 泛洪算法节点间消息传播的过程

第二，串行调度按照一定的次序，依次对各节点进行更新。直到所有的校验节点（或变量节点）更新完毕，一次迭代过程才算结束。串行的消息传递机制，与洪泛机制相比，具有收敛速度快，复杂度低，且实际占用硬件资源少的特点。分层置信传播是一种典型的串行调度策略。研究表明，LBP译码的收敛速度大概是洪泛的两倍，且复杂度与洪泛保持一致。这是一种相对理想的，几乎不增加复杂度代价的更新策略。但是无论是洪泛还是LBP，其更新节点的顺序是不变的，称其为非动态消息更新策略。LBP的置信传播调度方式如图3所示。

图3. 泛洪算法节点间消息传播的过程

第三，动态调度动态选择节点进行更新，使得译码达到最优的性能和最大的收敛速率。其中残差置信传播策略能较大提高译码收敛速率。RBP为一种动态消息调度策略，每次需要对所有的消息计算更新前后的差值，然后进行排序。筛选出最大残差值所在的边，对其优先更新。其原理是，当译码收敛的时候，节点前后两次消息的残差值会趋向于0，也就是说，如果节点间消息残差值越大，则可以认为该消息在迭代译码中还未收敛，更新该消息对整个算法收敛具有较大贡献。因此优先对该节点进行处理，能有效的加快译码的整体收敛速率。RBP在高性噪比区可能存在误码平层现象，因而大大限制了译码性能。继而一种面向节点的RBP的动态策略(NWRBP)被提出，在一定程度上有效克服误码平层现象。NW-RBP在原有的算法上做了改进，与RBP不同，NW-RBP在选中最大残差值之后，让更多的变量节点参与更新。仿真结果表明, NW-RBP不仅提高了译码收敛速率，而且改善了RBP的译码性能，但是相对复杂度比较高。RBP和NW-RBP的置信传播调度方式如图4所示。

图4 RBP（左）和NW-RBP（右）算法节点间消息传播的过程

为比较以上三种调度方式的效果，采用（1944,972）码在AWGN信道下进行以上几种置信调度机制仿真，仿真结果如图5所示。当迭代次数较小的时候，RBP性能要显著优于其他三种算法。但随着迭代次数继续增大，RBP的FER曲线开始变得平缓，不再随着迭代次数的增加而降低，曲线出现了误码平层现象。尤其，在RBP迭代4次时候的FER与LBP在迭代次13的时候的FER相同，而且两种算法的FER曲线在迭代次数19次的时候相交，这说明了在RBP译码过程中，虽然迭代次数增大，仍然有些错误无法正确译出。当迭代次数较小，NW-RBP的性能并不如RBP，然后在迭代次数为10次的时候，RBP的性能曲线出现了瓶颈，而NW-RBP的FER继续得到改善而降低，这说明NW-RBP能较好得克服错误平台现象而使得译码的性能更好。此外，NW-RBP在迭代15次的时候的FER与LBP在迭代50次的时候的FER相同，且在迭代10次之后，NW-RBP相比RBP和LBP分别有1dB和0.8dB的FER增益，这说明NW-RBP能有效克服误码平层现象。

图5 信噪比Eb/N0=1.75dB时，（1944,972）码的FER随迭代次数变化的情况

4. 改进措施展望

以上介绍的串行、动态调度置信传播，虽然取得了快速收敛的效果。然而，在迭代次数较多的情况下，现有的一些改进方案并不能较大提高NW-RBP的误码率。由香浓极限所得，当LDPC码码长足够长时，迭代置信译码算法可以无限接近香浓极限。由此可见，LDPC码中的短环结构的存在，是导致译码算法无法收敛的重要原因。基于这一点，本文提出两点可行性改进措施：第一，统计LDPC码Tanner图中的短环分布情况。短环分布不仅要计算出短环的数量，还要统计出具体哪些变量节点参与组成短环，即短环结构。第二，在完成短环分布统计的基础上，分析短环对置信迭代算法的影响，研究残差值随迭代次数增加的变化趋势，从以下几个方面尝试设计新的快速收敛调度方法：（1）赋予参与组成较多短环的变量节点优先调度权；（2）与比特反转算法相结合，当置信算法无法收敛时，反转短环中的某些变量节点的符号，从而达到提高收敛速度和译码正确率的目的；（3）参考RBP算法，首先依据参与短环数对变量节点进行归类，对参与短环较多者并且残差最大者优先调度。以上几种方法的有效性，将在今后的研究中予以验证。

5. 总结

本文对低密度奇偶校验码的三种置信传播译码时序进行详细介绍。这三种译码时序分别是洪泛译码、串行译码、动态译码。通过展示LDPC码二分图中信息的传递顺序和各译码时序的仿真案例，对各译码时序的译码原理、收敛速度、译码误码率等进行阐述和比较，并提出一些可行性改进措施，以期望提高LDPC码的译码性能。

[1]R.Gallager.Low density parity check codes.IET Transactions on Informaiton Theory.1962.

[2]F.Kschischang,B.J.R.Frey,and H.A.Loeliger.Factor graphs and the sum-product algorithm. IET Transactions on Informaiton Theory. 2001.

[3]A.I.V.Casado,M.Griot,and R.D.Wesel.LDPC decoders with informed dynamic scheduling.IEEE Transactions on Communications. 2010.

结束语

通过对微控制器的嵌入式低功耗应用方面相关内容的探讨，可知嵌入式系统低功耗设计目标的实现，需要加强微控制器的合理运用。在具体的设计过程中，应提高对微控制器结构特点的全面认识，确保其在嵌入式低功耗应用中能够达到预期的效果，并在可靠的低功耗模式支持下，提高相关资源利用效率的同时完善系统的服务功能，实现对系统功耗的有效控制。

参考文献

[1]邵贝贝.单片机嵌入式应用的在线开发方法 .清华大学出版社,2004.

[2]林东宁,张强.墨盒芯片,实用新型专利,专利号ZL 200620060165.9.

[3]刘长龙,严新文.嵌入式低功耗8位微控制器的设计[J].天津大学学报,2010,(12).

[4]李多,叶桦.一种基于STM32的嵌入式低功耗无线手持控制器设计[J].电子设计工程,2014,(18).

[5]刘伟伟.嵌入式系统低功耗技术的研究和应用[D].郑州大学,2012,(05).

项目资助：江苏省级大学生实践创新训练计划项目（201610300049），江苏高校品牌专业建设工程资助项目，江苏高校优势学科Ⅱ期建设工程资助项目。