图像欧拉数计算复杂度分析

文中用基于图段的方法计算欧拉数,并对该算法的时空复杂度进行分析比较.由于图段方法只要求较少的像素访问次数,从而节省运算时间,因此图段方法比现有的基于四方格或基于四叉树的方法更有效.这种分析还对图像欧拉数计算的VLSI硬件实现具有指导意义.

翻转距离星树问题的计算复杂度和近似算法

讨论基于基因组翻转距离的星型进化树问题的算法和复杂性.首先证明星树问题是NP-难解的,再证明该问题不存在绝对近似求解算法,最后给出一个求解星树问题的常数近似算法,近似性能比为2.

双层结构预测控制计算复杂度分析

在大规模系统在线实施中,双层结构预测控制计算存在复杂度较高、在线求解时间较长的缺陷,从而限制了它的求解效率。通过对稳态目标层和动态控制层的计算复杂度理论分析以及仿真验证,得出影响算法求解效率的主要因素为系统控制输入数和控制时域,且算法的时间复杂度正比于控制输入数和控制时域乘积的三次方。为双层结构预测控制在工程设计中的应用提供了有益的参考。

低计算复杂度的永磁同步电机多步预测电流控制

传统的永磁同步电机模型预测电流控制策略仅在一个采样周期内寻优,难以避免陷入局部最优问题,而多步预测会增加预测次数,计算复杂度成倍增长.为此,提出一种低复杂度的永磁同步电机三步电流预测控制策略.首先,在延时补偿的基础上,两步预测结合三矢量电压控制和最优占空比电压控制,三步预测保持与两步预测相同的电压矢量,然后由代价函数选出控制电压矢量;最后,设计电感dq轴分量双闭环的鲁棒控制.仿真结果表明,相比其他控制策略,所提策略具有良好的动静态性能,寻优代码执行时间降低了约51%;在不影响输出电能质量的前提下,开关频率降低了约17%;并对电感失配造成的性能恶化具有抑制性.

计算机病毒的计算复杂度问题

计算机病毒对计算机系统及软件造成各种各样的损害,除了一些常见的损害,例如删除数据或程序、修改系统信息以外,它们还造成一些非破坏性的影响,例如消耗大量的存贮及时间。这个问题涉及到计算机病毒的计算复杂度。文章初步探讨计算机病毒的计算复杂度问题,从数学上证明两个基本结论:存在计算机病毒,它的传染过程具有任意大计算复杂度;存在计算机病毒,被感染程序的执行过程具有任意大的计算复杂度。除此而外,文章简要讨论计算机病毒检测过程的计算复杂度问题。

一种计算复杂度低收敛速度快的递推Capon谱估计算法

基于递推最小二乘方法实现对观测信号自相关矩阵的逆R-1L的估计,研究了一种计算复杂度低和收敛速度快的Capon谱估计算法。该算法避免了用Cholesky分解、奇异值分解、QR分解或目前文献中见到的其他方法所带来的Capon谱估计算法计算复杂的缺点。同时,在信号自相关矩阵条件数不好时,该算法仍然可以进行信号的谱估计。仿真结果表明,尽管该方法的谱估计分辨率不如修正协方差谱估计法,但是两者相差不多,该方法非常有利于谱估计算法的实时实现和实际应用,并且还可以实现Capon幅值估计。

HEVC帧间快速运动估计及计算复杂度分析

为了降低高性能视频编码标准中帧间运动估计的高计算复杂度,提出了一种基于运动矢量相似性的运动估计快速终止算法.该算法利用视频序列中同一个对象的运动矢量相似性,对当前编码单元的分割方式进行了选取,提前终止了部分可能性较低的复杂分割模式的运动估计.结合运动相似区域的编码单元,在分解后的下一递归深度中对小块预测单元划分的运动估计进行了裁减.实验结果表明:所提方法与高性能视频编码标准参考代码中的标准算法相比,在低延时编码配置下,编码时间和峰值信噪比分别降低了41.79%和0.052dB.随机访问编码配置下,编码时间和峰值信噪比分别降低了41.98%和0.041dB.运动估计的计算量减小,计算复杂度降低.

BP网络隐节点数与计算复杂度的关系

利用多层网络BP算法对复杂的函数进行逼近来讨论BP网络训练过程的训练误差和检验误差的关系,详细对隐节点的个数及取最优隐节点分布、复相关系数、检验误差以及网络输入为维数与计算复杂度的关系进行讨论,最后分析并检验所得关系的正确性。

移动音频带宽扩展算法计算复杂度优化

移动通信设备由于计算资源有限,对计算复杂度较为敏感。我国自主研发提出的移动音频编解码算法标准AVS P10中的带宽扩展算法有利于提高移动音频编解码质量,但其计算复杂度较高,不利于该编解码算法在移动环境中应用。通过分析该带宽扩展算法的流程,发现其计算复杂度较高的主要原因是时频变换次数过多,为此从算法和代码两个方面对该算法进行优化:算法方面通过减少快速傅里叶变换(FFT)次数来降低算法计算复杂度;而代码方面则通过空间换时间等方法来减少算法消耗时间。测试结果表明,在不降低整体音频编解码主观质量的情况下,带宽扩展模块在编码端和解码端运行时间比例分别降低了4.5和14.3个百分点,算法计算复杂度显著降低,这有利于进一步在移动音频领域推广应用该编解码算法。

一种计算复杂度可调整的块匹配运动估计算法

提出一种计算复杂度可调整块匹配运动估计算法,该方法综合传统三步法中收缩搜索策略和四步法及钻石法中步进搜索策略的优点,对于分散分布的运动矢量及聚中分布的运动矢量搜索都表现出良好的鲁棒性.搜索模式的规整性也使得该算法的VLSI结构设计比以往的算法实现更加简洁,通过对搜索步数和块匹配中降采样率的控制,实现了对运动估计计算复杂度的调整,从而可在计算复杂度与图像处理质量之间折中.该特征为视频编码系统整体的低功耗设计提供前提条件,适用于低复杂度低功耗视频编码器.

一种自适应降低计算复杂度的视频解码方法

在研究了离散余弦变换的频域分辨率与时域分辨率的转换关系的基础上,提出了一种基于自适应降阶IDCT的低复杂度视频解码方法.根据DCT系数块中非零系数的个数,对DCT系数进行自适应降采样.对降采样后的DCT系数块进行降阶的IDCT变换,再对变换后的块在时域中进行线性插值,最终实现解码.降阶IDCT处理降低的解码时间弥补了插值耗费的时间,还使解码的整体复杂度降低.测试结果表明,该方法解码时间可以节省60%-80%,而PSNR损失仅为0.3～0.7dB.

计算复杂度降低的基于CDKF的SLAM算法

为了降低移动机器人基于中心差分卡尔曼滤波(CDKF)的同时定位与地图构建(SLAM)算法的计算复杂度,使其适于较大规模环境中的应用,提出了一种改进的CDKF SLAM算法。该算法以CDKF的线性回归卡尔曼滤波(LRKF)形式为基础,利用SLAM自身特点,重构其预测和观测更新过程中的状态变量及相应的方差矩阵,改进CDKF的采样方法,从而将CDKF SLAM算法的计算复杂度降为O(n2)。不同规模环境中的仿真实验及停车场数据集的实验验证了在不改变CDKF SLAM算法估计准确度的条件下,本文算法的运行时间明显缩短,更适于大规模环境中的应用。

PSL可满足问题的计算复杂度

PSL是一种用于描述并行系统的属性规约语言,包括线性时序逻辑FL和分支时序逻辑OBE两部分。由于OBE就是CTL,因此论文重点研究FL逻辑。理论上已证明许多难解的问题都可多项式变换为"可满足性"问题,"可满足性"问题是研究时序逻辑的核心问题之一,并已成为程序验证的一种有力工具;而计算复杂度是"可满足性"问题需要解决的最深刻的方向之一,其研究意义在于它可作为解决一类问题的难度的标准。文中在利用"铺砖模型"基础上,推导并得出FL的"可满足性"问题的计算复杂度为EXPSPACE-hard,这对正确评价解决该问题的各种算法的效率,进而确定对已有算法的改进余地具有重要的指导意义。

一种新颖的低计算复杂度OFDMA资源分配算法

在融合遗传算法和解析方法的基础上,提出了一种新颖的正交频分多址接入系统资源分配算法.通过最小化评估函数和取整操作,得到满足用户要求的数据速率和误码率,同时使系统总传输功率最小化.与传统遗传算法相比,该算法避免了注水过程,其计算复杂度大幅降低,且不受数据速率增长的影响.仿真实验表明该算法的收敛性和稳定性好;在相同的用户数据速率和误码率要求下,该算法得到的最小化传输功率随用户数增加较为缓慢,接近于解析法得到的理想性能;在平均比特信噪比相同的情况下,该算法能使实际系统误码率接近理论低值.

快速传递对准滤波器设计及其计算复杂度分析

机载武器传递对准时,机翼挠曲变形等因素都会对子惯导的对准精度产生影响。针对空基导弹捷联惯导系统动基座传递对准的工程需要,重点考虑机翼挠曲变形带来的对准误差影响,采用"速度+姿态"的匹配方案设计了降维传递对准滤波器,并对其进行了仿真验证及计算复杂度分析。仿真结果表明,设计的17维设计快速传递对准滤波在4～6s内已收敛到亚毫弧度级,在保证对准性能的同时明显减小系统的计算复杂度。

视频解码计算复杂度的线性建模理论及在线预测方法

视频解码是一类最典型的多媒体应用,其计算量大、耗能高.现代多媒体计算平台可利用视频解码计算复杂度固有的动态变化特征来自适应地调整所需计算资源,从而节省能耗,其前提是对视频解码计算复杂度进行准确估计.作者基于解码计算复杂度与帧长之间的线性关系,提出了一种利用状态变量法对解码计算复杂度进行理论建模和在线估计的方法.与传统的直接对帧长和计算复杂度之间的输入-输出依赖关系进行建模所不同,这里将视频解码系统表征为由视频内容特征的状态变化所驱动的系统.首先从语义层面对解码器各模块的解码复杂度进行分析,并导出各模块计算复杂度与语义参数间的依赖关系模型,总解码复杂度为各子模块的复杂度之和.经过化简得到解码计算复杂度与帧长之间的线性模型,其中模型系数为上述语义参数的函数,表征了视频内容特征的状态变化,被定义为状态变量.再结合压缩视频流中相邻帧语义参数之间的相关性,将系统状态方程定义为反映视频内容变化程度的分段线性函数.根据I帧和P帧状态轨迹特性及其在压缩码流中位置属性的不同,分别进行计算复杂度在线估计:对于I帧,采用统计分析方法获得其状态变量的均值并进行在线估计;而对P帧,则是在运行过程中利用状态方程对状态变量进行实时更新和计算复杂度估计.在基于SimpleScalar的软件仿真平台和基于DSP的嵌入式硬件平台上分别对H.264、MPEG-4压缩码流的解码计算复杂度进行在线估计,实验结果表明:对解码计算复杂度的平均估计误差在7%以内,预测精度非常高,而且状态方程更新过程简单,在线运行复杂度低,特别适用于嵌入式移动设备.

低计算复杂度的半盲签名方案

为了解决盲签名中由于签名者无法控制签名内容以及已有半签名方案由于计算复杂度高而不实用的问题,提出了一种低计算复杂度的半盲签名方案,并给出了随机预言机模型下的安全性证明.新方案简化了交互过程中请求方和签名方之间的交互轮次,降低了在签名过程中的计算复杂度.与Masayuki Abe和Tatsuaki Okamoto的方案相比,新方案具有更高的效率.低计算复杂度的特性使得新方案非常适用于移动终端和智能卡环境.

降低多通道维纳滤波语音增强方法计算复杂度的新策略

提出三种改进的多通道维纳滤波算法。其中,每帧信号相邻多个频点共用一个相同线性滤波向量。跟传统算法比,所提出的三种算法有较低的计算复杂度。实验结果表明,以三种经典的客观评价为标准,所提出的三种算法在一些情形下比传统的多通道维纳滤波算法具有更好的去噪性能。

一个计算复杂度为O(n)的递归分组排序算法的实证

文章对递归分组排序进行了实际验证。对服从一般概率分布（非均匀分布）的随机数据序列实施递归分组排序和快速排序两种算法，递归分组排序比快速排序要快很多，特别是在数据量很大时。实证支持该理论结果。

可计算环上幂零根与Jacobson根的计算复杂度

Downey等人(2007)证明了:存在一个可计算的有单位元素的交换环,其幂零根是Σ_(1)^(0)-完全集;存在另一个可计算的有单位元素的交换环,其Jacobson根是Π_(2)^(0)-完全集。本文进一步证明了:存在一个可计算的有单位元素的交换环,其幂零根是Σ_(1)^(0)-完全集且其Jacobson根是Π_(2)^(0)-完全集。此外,对于任意c.e.集A,都存在一个可计算的有单位元素的交换环使其幂零根与A图灵等价;对于任意Π_(2)^(0)集B,都存在一个可计算的有单位元素的交换环使其Jacobson根与B图灵等价。