江苏 南京 210000
摘要：该算法大大降低了时间复杂度和空间复杂度，使得中低速或猝发通信系统的译码模块可应用在DSP或ARM等低功耗处理器上。本文通过对该算法原理及复杂度分析，得出结论：算法本身并不影响译码性能，却提高了算法应用范围。
关键词：索引矩阵；LDPC；最小和
1 引言
LDPC码[1]是一种逼近香农限的信道编码，性能优异，缺点是译码运算复杂，工程中一般只把编码模块可以放在DSP或CPU中实现。为了提高业务吞吐率，译码模块通常要进行FPGA开发或购买第三方的IP核，研制成本高昂。
以QC_LDPC(1/2，2016)码型[2]常用的最小和算法为例，在TI DSP6457上解码一帧数据需要约200ms的时间，数据吞吐率约5kbps。本文通过对传统译码算法分析，找出计算瓶颈，传统算法没有发挥稀疏矩阵的特点，造成空间和时间上不必要的开销，导致运算效率低下。
本文对稀疏校验矩阵中的非零节点建立横向索引和纵向索引，时间复杂度从降到。TI DSP6457运行实际结果表明，(1/2，2016)码型解码一帧数据只需约10ms，数据吞吐率约100kbps。最后，本文对该算法复杂度进行了分析。
2 算法原理
工程上常用的LDPC译码普遍都是最小和（MinSum）算法，与传统的置信传播（BP）算法相比，该算法性能略有损失（大约0.2dB），但实现复杂度大大降低（译码过程只有乘加和比较运算），且不需要信噪比估计和自动增益控制等[3]。
LDPC译码器（码率为C）算法流程图如下：
算法主要的运算量在更新校验节点和变量节点上，以QC-LDPC（1/2，2016）为例，M=1008，N=2016，这意味着解码模块有M个校验节点和N个变量节点，传统算法中对每个校验节点需要计算N2次比较操作，以及对每个变量节点进行M2次比较操作，但更新的节点只是非常稀疏的非零节点。
鉴于此，本文根据QC_LDPC码的特点，定义两个索引矩阵H1和H2，H1存储校验节点信息，H2存储变量节点信息。由于H的最大行重是7，最大列重是6，因此申请存储校验节点和信息节点的空间分别是（M*7）和（N*6）即可。这在空间上相当于把原来M*N单位的存储空间压缩到10*N个单位，不仅大大降低了空间复杂度，还使得内循环计算量大大降低。下面给出校验节点和变量节点的更新示意图：
3 算法复杂度分析
以下对算法中单次迭代所需的运算资源作分析如下表：
一般M=(1-C)*N，因此传统算法的时间复杂度是、空间复杂度是，本文提出的算法复杂度均降到了线性复杂度，运算资源只随编码长度线性增加，便于长码的应用。
4 总结
本文详细介绍了一种低复杂度的LDPC译码算法，该算法通过对LDPC的校验矩阵建立两个索引矩阵的方法，使得译码算法在更新校验节点和变量节点时，只需对非零节点进行乘加等运算操作，极大发挥了稀疏矩阵的特点，从而把立方阶复杂度降低到线性复杂度，使得该算法能以软译码的方式运行在100kbps以下系统或猝发通信系统中，易于快速开发。
本文提出的算法只是优化了LDPC译码算法的运算结构，并不影响译码性能，实际应用中还可以通过优化编译选项和增加伴随式判断提前结束迭代循环的方式，进一步提高译码速度。
参考文献：
[1]R.G.Gallager.Low density parity-check codes[D].IRE Trans.Inf.Theory,Jan.,1962,IT-8(1):21–28.
[2]尹晓琦，LDPC码编码及译码算法的研究[D],南京师范大学，2006.
[3]田宇,QC_LDPC码构造及其译码研究[D], 西安电子科技大学，2015.
论文作者:付军峰
论文发表刊物:《城镇建设》2019年14期
论文发表时间:2019/9/29
标签：算法论文; 译码论文; 复杂度论文; 节点论文; 矩阵论文; 本文论文; 变量论文; 《城镇建设》2019年14期论文;