一种求解高密度最大权重团的信息传播算法

在高密度复杂结构带权无向图中,由于信息传递复杂,传统信息传播算法求解最大权重团问题效率较低。利用最大权重独立集与最大权重团的映射关系提出一种针对高密度带权无向图求解最大权重团问题算法,该算法以最大积信息传播算法为框架,将最大权重团的约束条件与置信传播算法迭代方程相结合,设计信息传播算法势函数。同时,将高密度复杂结构带权无向图映射为因子图,并进行去环操作,利用信息传播迭代式进行特征收敛计算,通过迭代收敛后的最大后验概率计算最大权重团最优解。基于不同密度随机图进行实验对比分析,实验结果表明,该算法求解高密度复杂结构带权无向图最大权重问题时非常有效,求解总权值的准确度与求解速率均高于标准置信传播算法。

天基信息传输高效低复杂度LDPC译码算法研究

军事卫星通信由于需满足信息实时性、传输速率高、通信容量大以及符合星间链路信道的时变特性等要求,通常采用高编码增益、高吞吐量的信道编码方案。低密度奇偶校验(Low-Density Parity-Check,LDPC)码由于具备接近Shannon极限的优异纠错性能和可并行计算的特性成为卫星通信主导信道编码标准之一。目前卫星通信接收机的译码器模块设计仍存在诸如无法实时在线判断迭代停止、系统吞吐量受限、大量判决电路影响核心译码电路的低功耗和实时性等问题。考虑上述问题,以因子图模型为基础,针对空间数据系统咨询委员会(Consultative Committee for Space Data Systems,CCSDS)标准深空通信码型,将校验节点归一化满足概率进化图案与LDPC译码器状态紧密耦合,给出可实时在线判断迭代停止的最优停止准则,实现高性能、低复杂度的停止准则译码算法设计。当优先考虑高吞吐量时,误码率(Bit Error Rate,BER)性能退化0.13 dB,中低信噪比平均迭代次数(Average Number of Iteration,ANI)降低50%以上;当优先考虑纠错性能时,BER性能仅退化0.02 dB,同时大幅降低ANI。该译码算法为高效低复杂度LDPC译码器设计提供有效解决方案。

激光雷达和IMU紧耦合SLAM算法

近年来,无人驾驶领域成为广泛关注的热点方向,同时定位与地图构建(SLAM)技术是高精地图创建和无人车辆导航的基础,当下主流的激光SLAM算法基本能够满足应用的需求,但是在大范围场景建图的过程中仍然存在漂移的问题,且算法轻量化以及实时性方面依旧有着改进的空间。文章主要进行了激光雷达和惯性测量单元(IMU)紧耦合的同时定位与建图算法研究,前端部分主要对激光点云数据进行了去除畸变、特征提取,后端使用因子图融合IMU预积分因子、激光里程计因子和回环检测因子进行融合位姿输出。为了提高算法的实时性,文章使用iKD-Tree数据结构维护了一个局部地图,并使用Fast-GICP算法求解回环检测位姿变换。在Kitti公开数据集的测试表明,改算法在保证精度的同时提高了算法的实时性和鲁棒性。

激光雷达IMU紧耦合的室内大范围SLAM方法

针对激光雷达SLAM算法在室内大范围场景中建图与定位精确度低、鲁棒性差的问题,提出一种激光雷达IMU紧耦合的SLAM方法。该方法基于LeGO-LOAM算法,在点云去畸变环节引入惯性测量单元(IMU)数据,将IMU预积分的结果作为初始位姿,消除点云畸变;在点云配准环节,将IMU预积分的结果作为迭代优化时的初始位姿,提升点云配准精度,从而提高机器人位姿估计的准确性;在后端优化环节,通过构建因子图的方式引入激光里程计因子、IMU预积分因子及回环因子,得到全局最优解,进一步提升建图与定位的精度。为验证所提方法的可行性,设计不同场景下LeGO-LOAM算法与改进SLAM算法的对比实验。实验结果表明,在室内大范围场景下,改进的SLAM算法能够减少轨迹波动,提升建图效果及轨迹精度,增强算法的鲁棒性。

基于因子图—和积算法的故障链路诊断

为求得网络内部链路的先验故障概率,提出一种估计链路状态分布的新方法。采用因子图模型描述链路状态和路径状态间的联合概率分布,并使用和积算法求得各链路状态的最大后验估计,然后利用估计出的链路故障概率和当前测量数据推断链路的当前状态。仿真结果表明,当网络规模达到400个节点时,所提方法的计算时间比联立方程组求解法低两个数量级以上,具有更好的可扩展性。

一种基于因素图的联合信道估计和信号检测迭代算法

本文提出了一种新的联合信道估计和信号检测算法.基于广义分配率准则,将实现发送序列最优估计的似然函数分解为多个局部概率函数的乘积,而局部概率函数之间的关系借助直观的因素图来描述.在此基础上,利用和积算法,实现分布式的联合信道估计和信号检测,以较低的计算复杂度达到最优序列检测性能的逼近.同时,采用粒子滤波处理和积算法中出现的连续变量积分,实现频率选择性衰落信道的实时跟踪,从而可有效降低导频数量,提高频谱效率.仿真结果表明,这种联合算法在获得较好的检测性能同时,计算复杂度显著降低.

基于因子图消元优化的多传感器融合定位算法

无人机定位系统融合处理多个不同频率、非线性传感器传输信号过程中,针对采用常规的基于因子图模型的信息融合方法,存在定位精度不高、抗扰性差及容错能力弱等问题,提出了一种基于因子图消元优化的多传感器融合定位算法。提出的新算法为了提高抗干扰性和容错能力,在链式因子图模型中加入滑动窗口用于保留窗口内历史状态信息;同时为了避免高维矩阵运算,引入消元算法将因子图转化为贝叶斯网络,依次边缘化历史状态,实现矩阵降维。在对比实验中,无人机定位系统分别采用常规因子图算法和因子图消元优化算法进行导航定位,实验结果表明,提出的因子图消元优化算法可以显著地提高定位的精准性、可靠性,同时大大减少信息融合的运算量。

MIMO系统中基于因素图的迭代信号检测算法

基于无线通信中接收信号的似然检测模型,给出发送信号估计和推理的因素图描述。在此基础上,应用标准和积算法提出一种频率选择性衰落信道下的多输入多输出(multiple input multiple output,MIMO)系统的迭代信号检测算法。为了降低计算复杂度,提出一种快速迭代检测算法,通过引入概率数据关联方法,避免了标准和积算法中符号概率估计的积分计算。仿真结果表明,应用标准和积算法得到的迭代信号检测算法可以逼近最优算法的性能,而快速迭代检测算法在大幅降低计算复杂度的同时,误码率性能比传统的最小均方误差算法有较大优势。

路径张量分解的知识图谱推理算法

现有张量分解技术在用于知识图谱学习和推理过程中时,只考虑知识图谱中实体与实体间的直接关系,忽略知识图谱图形结构的特点.因此,文中提出基于路径张量分解的知识图谱推理算法(PRESCAL),利用路径排列算法(PRA)获得知识图谱中各实体对间的关系路径.然后对实体对间的关系路径进行张量分解,并在优化更新过程中采用交替最小二乘法.实验表明,在路径问题回答任务和实体链接预测任务中,PRESCAL可以取得较好的预测准确率.

因子图在卫星姿态估计中的应用

在北斗卫星导航系统定位过程中首先要对卫星自身的姿态角速度进行估计。卫星姿态角速度估计的精度将直接影响北斗卫星定位的精度。为了提高北斗卫星姿态角速度估计的精度,提出了一种新的采用概率图模型的卫星姿态角速度估计方法,即基于因子图消息传递的卫星姿态角速度估计方法。因子图是一种典型的概率图模型方法,它通过对卫星姿态角速度观测方程和状态方程建模,并使用和积迭代算法求解相关参数,获得对卫星姿态角速度的估计。通过MATLAB仿真,对所提算法与传统基于kalman滤波的姿态角速度估计算法进行比较,结果表明改进算法可以准确估计卫星的姿态角速度,并且在低信噪比情况下比kalman滤波算法有更小的估计误差,算法收敛速度更快,可为北斗卫星导航定位系统优化设计提供参考。

基于因子图的Turbo码译码

Turbo码和LDPC码都可以实现接近Shannon理论极限的性能。Turbo码由于成员RSC码所固有的移位寄存器特性使得其编码较为容易实现 ;而对于接近Shannon容量的LDPC码 ,则需要大量的矩阵乘法运算才能完成信息的编码 ,电路实现较为复杂。另一方面 ,采用和积算法的LDPC码的译码过程则比采用BCJR算法 (及其简化形式 )的Turbo译码更加容易实现 ,且计算复杂度更低。将Turbo编码与LDPC码的译码相结合 ,对Turbo采用基于其因子图表示的和积译码算法进行译码 ,可以在很大程度上降低Turbo码的译码复杂度 ,并对交织器的设计及成员码的选择有一定的指导作用。

基于因子图的同频数字混合信号单通道盲分离

本文针对复杂编码下同频数字调制混合信号单通道盲分离问题,构建了利用因子图设计盲分离算法的统一框架。通过将和积消息传递算法与ECM参数估计算法有机地结合,提出一种基于因子图的编码辅助同频混合信号单通道盲分离算法。确定了在最大似然准则下混合信号同步参数的估计式。利用广义分配率准则,为存在码间干扰的混合信号建立了合理的因子图模型,得到了符号序列的后验概率估计式。仿真结果表明,本文提出的算法不仅能够对卷积码混合信号取得较好的分离性能,还能有效实现对LDPC码等复杂编码混合信号的参数和序列的联合估计。

基于iMPA的伪码快速捕获算法的性能分析和改进

针对迭代消息传递算法(iterative Message Passing Algorithm,iMPA),通过证明m序列是一种特殊的线性分组码,给出了该算法应用到伪码捕获的理论依据;分析了采用iMPA进行伪码快速捕获的性能,包括捕获概率和算法复杂度;用马尔科夫链分析了基于iMPA的捕获及判决流程,给出了平均捕获时间的解析表示。针对iMPA进行伪码捕获时收敛速度慢,检测性能较低的缺点,通过增加因子图的约束,提出了冗余iMPA算法,即R-iMPA(redun-dancy iMPA)。仿真结果表明,R-iMPA能有效的提高算法的收敛速度,检测性能平均提高约2 dB。

OFDM系统中基于因子图的信道估计算法

为提高正交频分复用(OFDM)系统的信道估计精度,根据频谱资源的无线信道特性,提出基于因子图的OFDM系统信道估计算法,包括二维联合信道估计算法和2个级联的一维信道估计算法。将时变频率选择性衰落信道建模为一阶自回归模型,使信道参数之间的交互信息近似为高斯分布,利用和积算法实现OFDM系统的联合信道估计和符号检测。仿真结果表明,该信道估计算法能够以较低的计算复杂度逼近最优的估计性能。

基于因子图的MIMO-OFDM时变信道估计

提出了一种基于因子图的多输入多输出正濒分复用(MIMO-OFDM)时变信道估计算法.该算法在占用少量导频的基础上,建立一阶AR信道模型,使用消息传递算法进行MIMO-OFDM信道估计,并将该方法与LS算法、MMSE算法、基于Kalman滤波的信道估计算法进行比较.通过MATLAB仿真表明,该算法可以很好地估计MIMO-OFDM信道,算法复杂度低于MMSE算法,且在低信噪比情况下,估计性能优于其他的算法.

MIMO系统中基于因子图的联合迭代检测和LDPC译码

本文提出了多输入多输出系统中频率选择性衰落信道下的一种联合迭代检测和LDPC译码的算法,采用因子图的模型将检测器和译码器融合到了一个框架中,通过检测器与译码器两个处理器内部及全局的信息混合调度改善系统性能。与MAP检测比,该算法以较低的复杂度获得良好的性能,因子图检测特有的并行调度在硬件快速实现上更具优势。

警示传播算法收敛的充分条件

信息传播算法求解可满足问题时有惊人的效果,难解区域变窄.然而,因子图带有环的实例,信息传播算法不总有效,常表现为不收敛.对于这种现象,至今缺少系统的理论解释.警示传播(warning propagation,简称WP)算法是一种基础的信息传播算法,对WP算法的收敛性研究是其他信息传播算法收敛性研究的重要基础.在WP算法中,将警示信息的取值从{0,1}松弛为[0,1],利用压缩函数的性质,给出了WP算法收敛的一个充分条件.选取了两组不同规模的随机3-SAT实例进行实验模拟,结果表明:当子句与变元的比值?<1.8时,该判定条件有效.

可满足性问题中信念传播算法的收敛性分析

信念传播算法是基于因子图模型的消息传递算法,通过图中的边,将消息从一个结点传递给另一个结点,以高概率地确定部分变量的取值,这种方法被实验证明在求解可满足性问题时非常有效.然而,目前还未对其有效性从理论角度给予解释.通过对信念传播算法的收敛性分析,试图从理论上解释算法的有效性.在信息传播算法的信息迭代方程中,参数的取值范围为(0,1),将该取值范围扩展到整个实数空间,即(−∞,+∞).利用压缩函数的数学原理,得到了信息迭代方程收敛的判定条件.选取随机可满足性问题实例进行实验模拟,验证了结论的正确性.

LDPC码的低复杂度译码算法研究

本文在对LDPC码的译码算法分析的基础上,针对校验矩阵中含有的环对译码算法的影响,提出了一种基于置信传播算法基础上的低复杂度译码算法。该算法通过及时切断消息在环上的重传回路,可消除因校验矩阵中的环回传原始信息对译码造成的影响,保证优质的原始信息能尽可能地传播到其能传播的节点,从而提升了LDPC码的译码性能。仿真实验表明,该算法具有低于传统算法的复杂度,在低信噪比的信道中可以获得相当于传统算法的性能,在良好的信道条件下可以取得比传统算法更优异的性能。

基于置信传播的优化译码算法研究

该文在对LDPC码的译码算法分析的基础上,针对校验矩阵中含有的环对译码算法的影响,提出了一种在置信传播算法基础之上的译码算法。该算法通过及时切断消息在环上的重传回路,可消除因校验矩阵中的环回传原始信息对译码造成的影响,保证优质的原始信息能尽可能地传播到其能传播的节点,从而提升了LDPC码的译码性能。仿真实验表明,在低信噪比的信道中,该算法具有相当于传统算法的性能和更低的计算复杂度;在良好的信道条件下可以取得比传统算法更优异的性能。