天基信息传输高效低复杂度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译码器设计提供有效解决方案。

面向物理信息系统的分布式攻击图生成算法

物理信息系统包含类型多样的物理设备,现有的攻击图生成技术不适用于物理信息系统.传统的漏洞扫描技术难以检测到物理设备的漏洞,并且随着系统规模的增加,攻击图的计算会出现状态空间爆炸问题.为此,本文提出了一种面向物理信息系统的分布式攻击图生成算法.首先,针对物理设备漏洞识别较难的问题,提出了一种基于属性标记实体的方法扩展实体漏洞信息,并据此对物理信息系统进行攻击建模;其次,针对状态空间爆炸问题,提出了一种分布式攻击图生成算法,并且利用消息传递机制消除图部分的重复遍历,进一步提高了生成效率.实验结果表明,与其他相关技术相比,本文技术具有更高的生成效率.

融合负采样和消息传递的GCN推荐算法

近年来,图卷积神经网络(Graph Convolutional Networks,GCN)在推荐领域有广泛的应用,LightGCN通过对传统GCN的简化,省略特征变换和非线性激活的过程,对GCN的研究提供了新思路。为了解决推荐算法负采样问题和消息传递对GCN收敛的影响,提出了SNGCN模型,改变了直接从数据中采样原始负样本的采样策略,利用正例混合和样本混合两个步骤合成硬负样本;其次,SNGCN利用约束损失逼近多层图卷积的极限。最终该模型在4个公开基准数据集上得出的实验结果表明,其Recall和NDCG两项指标均比对比的推荐算法有所提升。

分布式多维大图迭代计算性能优化方法

大规模图的复杂挖掘算法通常需要高频迭代分析,而在计算与存储方面扩展性良好的分布式计算是提高处理效率的有效方案.然而,图顶点之间存在自由分布的边关系,会在分布式计算任务之间产生大量消息,由此在迭代过程中产生的巨大通信开销严重制约性能收益.已有工作在传统消息推送框架下采用合并和备份等技术降低通信代价,但主要面向结构简单、易优化的单维消息类算法,并不适用于结构复杂的多维消息类算法,也难以与当前最先进的消息按需拉取框架兼容.因此提出一种新型轻量级顶点备份机制,通过备份顶点的按需同步以及本地消息的按需生成,可完美继承拉取框架在容错和内存管控等方面的系统优势,同时显著降低通信代价.此外,通过考虑通信收益与负载偏斜代价,可计算最优阈值以提高整体性能.最后在大量真实数据集上验证了相关技术的有效性.

基于消息传递机制的MapReduce图算法研究

单机运行环境难以满足基于海量数据的大图算法对时空开销的需求,如何设计高效的面向云计算环境的分布式大图算法越来越受到人们的关注,MapReduce作为云计算的核心计算模式受限于易并行(EP)计算模型的制约不易表达图算法.文中突破了MapReduce基于易并行计算的假设,增强了MapReduce既有的编程规范,新的大同步(BSP)计算模型既能保证兼容旧的MapReduce作业可以无改动的运行,同时引入消息传递机制允许变化的状态数据在并行任务的超级步间进行交互.系统提供高度灵活的消息自定义接口,针对不同应用需求设计了轻量级和重量级两种自适应的消息传递机制,更高效地支持有数据交互需求的包含迭代处理的一大类图算法.在真实大规模图数据集上的实验结果表明,相比于原始的MapReduce作业外部链式处理,该文提出的BSP模型下的内部超级步迭代计算模式大幅降低了大图算法的处理时间.

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

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

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

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

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

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

上行SCMA系统的动态子图检测算法

面对未来网络需求量的爆炸性增长,稀疏码多址接入(Sparse Code Multiple Access,SCMA)作为一种基于码本的非正交多址技术,在用户连接数、频谱效率和低时延都有很大的提升。由于码字的稀疏性,SCMA采用消息传递算法(Message Passing Algorithm,MPA)实现多用户检测,但是复杂度还是相对较高,以至于很难应用于实际系统。为了解决上述问题,提出了一种动态子图消息传递算法(Dynamic Sub-graph Message Passing Algorithm,DS-MPA)进行信号检测。DS-MPA利用剩余值来确定下一次迭代的子图,减少了资源节点的更新用户数量,达到了降低复杂度的目的。仿真结果显示算法性能几乎无损并且降低了1/3左右的复杂度。

LDPC码研究进展

介绍了LDPC码的特点和优势;综述了LDPC码在码结构及其优化、译码及其性能分析、码的工程实现和应用等方面的研究进展。

稀疏码分多址收发端改进方案的设计

为降低传统稀疏码分多址接入(sparse code multiple access, SCMA)系统的译码复杂度,同时保证系统误比特率(bit error ratio, BER)性能,考虑信道质量因素提出SCMA系统收发端改进方案。在接收端,提出基于信道质量动态选择节点改进消息传递算法(message passing algorithm, MPA),在串行策略基础上对节点更新顺序进行合理排序,减少算法迭代次数,以降低译码复杂度;同时为补偿付出的BER性能代价,在发送端基于信道质量设计动态自适应更新因子图方案,为用户节点匹配高信道增益的资源节点组合,并且考虑到用户的公平性,令上轮更新因子图时信道增益最低的用户节点优先匹配。仿真实验证明,所提改进方案在保证BER性能和各用户公平性前提下有效降低系统译码复杂度。

协作网络因子图中粒子形式的信息传递算法

和积算法结合因子图可以用分布式方式实现协作定位。和积算法是一种信息传递算法,然而在非线性、非高斯环境下用参数法实现信息传递误差较大,不能满足定位需要,提出一种算法用粒子形式来实现信息传递。因子图中的信息计算包括求和与求积两个过程。粒子形式的信息传递算法利用重要性采样得到求和信息,利用吉布斯采样得到求积信息。提出的算法能简化复杂的网络节点的联合后验概率。与基于参数的信息传递算法相比,粒子形式表示方法提高了在非线性、非高斯环境下的定位精度。

基于因子图拉伸的SC-FDE联合信道估计接收机

提出了一种基于因子图-消息传递算法的联合信道估计单载波频域均衡(SC-FDE)接收机。针对现有联合信道估计接收机中存在的复杂度和性能之间的矛盾,利用因子图拉伸方法对现有模型进行拉伸变换。变换之后的因子图模型可以将现有模型中的观测节点分割为几个节点的组合,并依据分割后节点的自身特点采用更合适的消息传递规则,进而避免了各种消息传递规则的固有缺陷。仿真结果表明,相比已有联合接收机算法,所提出的基于因子图拉伸和联合期望传播-平均场(BP-MF)算法在提升性能的情况下能够显著降低复杂度。

一种基于图同构和单向置换的报文摘要构造算法

为了保护信息的机密性和完整性,该文给出了一种新的报文摘要构造算法,这种新算法是基于图同构的。为了把报文与图联系起来,采用了基于单向置换的报文摘要生成算法,并证明了对该算法而言,不存在多项式时间的概率算法来找到一个“冲突”。最后给出了类似于MD5算法的构造实例。

MD-4原象攻击的分析与改进

首先分析了Leurent提出的MD-4原象攻击方法,该方法利用MD-4布尔函数的吸收性质,迭代函数的可逆性以及消息扩展方式的特殊性,首先形成伪原象攻击,之后利用基于树的方法将伪原象转变为原象攻击。采用随机图的方法,对其后一部分进行了改进,提高了攻击效率,将复杂度从2102降低到298。

一种基于图匹配的求解可满足性问题的算法

信息传播算法求解可满足性问题时具有良好的有效性,能使难解区域变窄。在信息传播算法的设计中,是将变量的联合概率分布分解为变量子集上的局部函数的乘积形式。称局部函数为因子(factor),每一个因子依赖于一个变量子集,将变量联合分布的这一因子形式表示为图模型——因子图(factor graph)。信息传播算法是通过因子图上的边传递概率消息,这种消息传递有两种方式:变量结点传递给因子结点的消息和因子结点传递给变量结点的消息。从每个结点传出的消息由传入该结点的消息决定,通过某种迭代策略对消息进行更新。当这种消息迭代过程收敛到某一固定点时,利用某种规则(如,最小熵、最大积、最大匹配)对问题进行求解。本文提出一种利用最大匹配规则求解因子图上的信息传播算法的收敛性及算法迭代步数的上界估计方法,根据对算法的收敛性分析,在对问题解的精确性影响不大的前提下,仅需要给出算法合理的迭代步数或者强迫算法终止,使得算法提前结束,有助于求解可满足性问题算法性能的更进一步优化。

基于因子图的SCMA和LDPC联合检测和译码

稀疏码分多址(SCMA)和低密度奇偶校验码(LDPC)是未来移动通信系统中重要的多用户接入和信道编码备选方案。针对SCMA多用户检测性能不理想的问题,该文提出了基于因子图的SCMA和LDPC联合检测和译码方案(JDD),利用LDPC译码的外信息辅助SCMA的多用户检测,仿真结果表明,JDD方案能够获得显著的SCMA检测和LDPC译码性能增益,并使得译码性能逼近理想的单用户传输系统。为了实现算法性能与复杂度之间的折中,该文还提出了基于Jacobi对数近似和消息阻尼(Damping)技术的低复杂度联合检测和译码方案(RC-JDD),仿真和复杂度分析结果表明RC-JDD方案能够在保证译码性能的同时显著降低算法复杂度。

多计算机互连网通信中关于死锁问题的一种理论

如何获得无死锁而且通信性能良好的选路算法始终是人们十分关心的问题．本文提出纯分流点的概念并证明了选路算法无死锁的充要条件，从理论上解决了环与死锁的关系问题，为死锁的判定、消除和设计无死锁的算法提供了有力的依据．

多路直扩信号并行IMPA捕获算法仿真实现

针对长PN序列作扩频地址码的多路直扩信号的快速捕获问题,提出多路直扩信号并行IMPA(迭代信息传递算法)捕获方案,该方案能够根据接收信号的信道信息直接生成与各路接收信号序列粗同步的本地伪码序列,改变了传统捕获方法中本地伪码序列的生成方式,大大缩短了信号的捕获时间。详细说明了该方案的实现原理和实现方法,并对该方案进行了仿真和实际验证。结果表明该方案能够在低信噪比下实现多路直扩信号的快速捕获,而且实现的复杂度较低。

MIMO-SCMA系统低复杂度多用户检测算法

MIMO-SCMA系统不仅能够实现更高的频谱效率,在高吞吐量和海量连接应用场景中也具有明显的优势.针对下行链路MIMO-SCMA系统中联合消息传递算法(Joint Message Passing Algorithm JMPA)复杂度较高的问题,在JMPA算法的基础上对部分联合外部信息算法进行改进.首先筛选出概率密度函数值大于门限值Td的部分码字,再利用球形译码原理设置合适的球形半径R,对位于球内置信度高的码字信息进行迭代译码,提出的算法进一步减少了虚拟资源节点上信息更新数量.仿真表明,该算法与JMPA算法相比,既能保持检测性能最优和收敛速度较快的优点,又能显著降低算法的检测复杂度.