数字电路故障模拟方法复杂性分析

通过分析故障模拟算法的发展及其现状,在理论和对ISCAS实验的基础上,给出各种算法的复杂性分析结果,并比较了各种故障模拟方法的优劣。     

基于测试码并行的同步时序电路故障模拟方法

将组合电路故障模拟的一些加速技术推广到时序电路故障模拟中,提出并实现了一个功能块级的基于测试码并行的同步时序电路故障模拟方法,对部分ISCAS89 Benchmark电路的模拟结果表明,该故障模拟方法有较好的性能.     

快速的平行码临界路径跟踪故障模拟

针对平行码临界路径跟踪故障模拟中最费时间的扇出源故障模拟,提出了若干加速技术。通过对电路结构进行的独立扇出分支、扇出源分类及扇出源的最终汇聚门等静态分析,结合对停止线及停止扇出源、测试码标记向量以及扇出源临界性确定前的预处理等动态计算,使得扇出源故障模拟区域及需要故障模拟的扇出源数目大大减少,极大地缩短了整个故障模拟时间。实验结果表明,平行码临界路径跟踪故障模拟算法,对少量和大批的随机码都非常有效,并且随着电路规模增加,其有效性更加明显。     

一个快速的临界跟踪策略 VLSI故障模拟新方法

运用九故障信息标记（X,D,M,R,E,Q,T,P,U）,提出了加速扇出重汇聚引线临界性计算的一种故障模拟新方法,理论分析表明该方法是有效的。     

基于Matlab的线性拟合计算

对于弹道导弹,由于其运动受多种因素的影响,因此描述其运动的微分方程是极其复杂的,而且,方程中的部分参数是通过对试验数据的科学处理获得的.为了建立数学模型,有时用数据拟合的方法对试验数据进行处理.运用单变量、多变量的线性拟和方法,给出了"单输入/单输出"、"多输入/单输出"的线性拟合模型,并针对拟合模型中未知参数的确定问题,给出了基于最小二乘的线性矛盾方程组的求解方法.通过仿真计算,能够得到较高精度的计算结果.最后,给出了Matlab的实现方法,并给出了一段具体的实现程序.     

多传感器系统纯方位定位与可观测性分析

对多静止测向站系统的可观测性、定位方法进行了分析和研究。通过运动等效,将多静止站系统转化成一个特殊的单运动测向站问题。采用拟线性方法,建立了纯方位多传感器系统目标定位问题的数学描述,并分析了系统的可观测性条件。提出了两种目标被动定位的融合递推算法,它们可以以标量的形态递推计算,具有实时性高、可计算性好的优点。     

C3I网络复杂性的度量

从信息过载的角度提出了一种C3I网络复杂性的度量方法,并给出了具体的计算步骤.该度量具有清晰的物理意义,能够直观地反映C3I网络中的信息流的阻塞程度.研究发现,C3I网络的复杂性不仅与网络拓扑结构有关,而且与信息源的信息流产生速度、有向边容量以及传输规则相关,并且C3I网络复杂性度量中存在着突变拐点.最后通过一个案例对提出的C3I网络复杂性的度量方法及步骤进行说明.     

AWGN信道下线性分组码的差错概率下界分析

提出了一种线性分组码的最大似然译码(ML-decoding)差错概率下界的计算方法。差错概率的下界优化实质上是对联合事件概率下界的优化,算法结合改进的Dawson-Sankoff界的优化准则,提出了AWGN信道下线性分组码差错冗余事件的判决准则,得到了误码率下界的计算表达式。该表达式只依赖码字的Hamming重量分布与信噪比,较之类deCaens界与类KAT界,本算法得到的下界更紧,计算量更低。针对LDPC等线性分组码的数值结果证明了算法的优越性能。     

状态电子密度的数值反演

提出了一种计算状态电子密度的超分辨处理方法。这种方法是在Fourier变换的基础上,引入高频滤波器函数H（ω,α）,经滤波处理后,再取Fourier逆变换,得到近似解。此方法能够较好地抑制噪声干扰,且计算复杂性较低,文中给出了算法,证明了收敛性,最后给出了计算机实验结果。     

机载RWR/ESM中改进最近邻算法的分频段辐射源识别

当前战场环境复杂,机载RWR/ESM要求对辐射源快速识别。由于机载RWR/ESM设备计算能力有限,传统识别中采用的线性匹配算法耗时长,已经不适应当前战场环境。结合RWR设备的分频段体制提出分频段划分雷达样本库,库内采用频率优先最近邻算法以降低计算时间。仿真对比了改进最近邻分频段方法与线性匹配方法的计算时间,结果表明了该方法的有效性。     

A finite algorithm for concave minimization over a polyhedron

We present a new algorithm for solving the problem of minimizing a nonseparable concave function over a polyhedron. The algorithm is of the branch-and-bound type. It finds a globally optimal extreme point solution for this problem in a finite number of steps. One of the major advantages of the algorithm is that the linear programming subproblems solved during the branch-and-bound search each have the same feasible region. We discuss this and other advantages and disadvantages of the algorithm. We also discuss some preliminary computational experience we have had with our computer code for implementing the algorithm. This computational experience involved solving several bilinear programming problems with the code.     

Nonextreme point solution strategies for linear programs

This exposition presents two algorithms for linear programs which allow a value change in more than one nonbasic variable at each iteration. The computational formulae are developed and errors which have appeared in the literature are noted. One algorithm is a multiple basis exchange procedure while the second is a feasible direction method. There remain many computational challenges in the area of linear programming and we hope that this investigation will encourage additional work in the directions indicated in this exposition.     

基于正交最小二乘估计的非线性时间序列的预测

在对非线性时间序列的短期预测中经常采用局部线性化的预测算法 ,原有的算法使用普通最小二乘法 (LS)估计近似线性模型的参数。对于存在噪声的数据 ,该算法的数值稳定性较差。本文在对非线性空间进行局部线性化的基础上 ,采用正交最小二乘方法 (OLS)对线性模型同时进行结构选择与参数辨识 ,改善了数值的病态特性 ,增强了算法的稳定性     

Nonlinear integer programming for various forms of constraints

A theoretical and computational investigation is made of the performance of a dynamic-programming-based algorithm for nonlinear integer problems with various types of constraints. We include linear constraints, aggregated linear constraints, separable nonlinear constraints and constraints involving maxima and minima. Separability of the objective function is assumed. The new feature of the algorithm is that two types of fathoming or pruning are used to reduce the size of tables and number of computations: fathoming by bounds and fathoming by infeasibility.     

A generalized euclidean procedure for integer linear programs

This paper investigates a new procedure for solving the general-variable pure integer linear programming problem. A simple transformation converts the problem to one of constructing nonnegative integer solutions to a system of linear diophantine equations. Rubin's sequential algorithm, an extension of the classic Euclidean algorithm, is used to find an integer solution to this system of equations. Two new theorems are proved on the properties of integer solutions to linear systems. This permits a modified Fourier-Motzkin elimination method to be used to construct a nonnegative integer solution. An experimental computer code was developed for the algorithm to solve some test problems selected from the literature. The computational results, though limited, are encouraging when compared with the Gomory all-integer algorithm.     

军队人力资源培训问题的整数线性规划模型

文章研究了军队人力资源培训问题,并基于时间和费用两个指标,建立了一个满足培训时间约束且费用最省的0-1整数线性规划模型,给出了基于Lagrange松驰分解的模型求解算法。在算法中,采用一种简单可行的Lagrange乘子更新方法代替传统的次梯度法。另外,文章证明了算法获得最优解的两个充分条件,计算实例初步表明给出的算法是行之有效的。     

基于直接数据域自适应算法的相干信号DOA估计

利用直接数据域自适应算法的稳态权值代替噪声子空间构建空间谱,构造了一种超分辨波达方向(DOA)估计方法.为了解决谱峰搜索时的伪峰问题,采用参考阵元轮换得到多组线性无关稳态权值,逼近噪声子空间,能有效去除伪峰.针对相干信号的DOA估计,进一步提出了直接数据域取对称共轭向量的解相干方法.相比子空间分解类算法,本文算法不需估计信号源数目和协方差矩阵、不需特征分解,复杂度仅为O(MP),同时能有效完成解相干处理.     

一种针对基因识别的GHMM简化算法

广义隐Markov模型是计算机基因识别的一种重要模型,它克服了传统隐Markov模型的状态段长成几何分布的缺陷,更加适合于计算机基因识别。其缺点在于计算量大,需要采用有效的简化算法。利用基因的结构特点,在不附加额外限制条件的情况下,提出了一种新的简化算法,其计算复杂度是序列长度的线性函数。对实际生物序列数据的测试结果表明了此简化算法的有效性。     

An exact network flow formulation for cell‐based evacuation in urban areas

In the literature two common macroscopic evacuation planning approaches exist: The dynamic network flow approach and the Cell–Transmission–Based approach. Both approaches have advantages and disadvantages. Many efficient solution approaches for the dynamic network flow approach exist so that realistic problem instances can be considered. However, the consideration of (more) realistic aspects (eg, density dependent travel times) results in non‐linear model formulations. The Cell‐Transmission‐Based approach on the other hand considers realistic traffic phenomena like shock waves and traffic congestion, but this approach leads to long computational times for realistic problem instances. In this article, we combine the advantages of both approaches: We consider a Cell‐Transmission‐Based Evacuation Planning Model (CTEPM) and present a network flow formulation that is equivalent to the cell‐based model. Thus, the computational costs of the CTEPM are enormously reduced due to the reformulation and the detailed representation of the traffic flow dynamics is maintained. We investigate the impacts of various evacuation scenario parameters on the evacuation performance and on the computational times in a computational study including 90 realistic instances.     

Rank‐Cluster‐and‐Prune: An algorithm for generating clusters in complex set partitioning problems

Clustering problems are often difficult to solve due to nonlinear cost functions and complicating constraints. Set partitioning formulations can help overcome these challenges, but at the cost of a very large number of variables. Therefore, techniques such as delayed column generation must be used to solve these large integer programs. The underlying pricing problem can suffer from the same challenges (non‐linear cost, complicating constraints) as the original problem, however, making a mathematical programming approach intractable. Motivated by a real‐world problem in printed circuit board (PCB) manufacturing, we develop a search‐based algorithm (Rank‐Cluster‐and‐Prune) as an alternative, present computational results for the PCB problem to demonstrate the tractability of our approach, and identify a broader class of clustering problems for which this approach can be used. © 2009 Wiley Periodicals, Inc. Naval Research Logistics 2009