基于FSM的测试用例生成算法

研究了基于FSM模型的测试用例自动生成算法来验证实现的FSM与规格FSM的一致性。基于状态机分解的思想提出了新的用例生成方法,DC-方法。相对其他通用方法而言,它不必依据测试树中所有的子路径集合,从而使得用例集减少,同时减少每次重置到初始态的次数,测试序列的长度也有所减少,节省了测试时间,提高了效率,并且具有良好的扩展性,可以方便应用于包含数据流的测试,只需在搜索到所有的DU-Path后直接经过运算就能得出测试用例。并给出了生成用例方法的正确性证明。     

面向USB PD3.0协议的新型BMC解码电路设计

针对USB PD3.0(Universal Serial Bus Power Delivery)协议中的传统BMC(Biphase Mark Coding)解码所存在的功耗高、面积大、抗干扰性差等缺点,提出了具有自动校正功能的低功耗、面积小、鲁棒性强的新型解码系统。该系统充分利用了FIR(Finite Impulse Response)滤波算法和滑动平均滤波算法的优点,使之更好地服务于该解码系统,此外,该系统还增加了信号监控功能。为验证该系统的可靠性,在Synopsys公司的DC开发平台下,采用Verilog语言描述该系统电路并进行仿真验证。实验结果表明,在同等情况下,该系统与传统解码电路相比,鲁棒性明显增强,同时面积降低了2.19%,功耗降低了2.06%,充分体现低功耗、面积小、抗干扰能力强等优点。该系统为提高USB PD快速充电芯片设计的可靠性、实用性奠定了理论基础,并且提高了USB PD3.0的充电效率。     

Efficient distributed SAT and SAT-based distributed Bounded Model Checking

SAT-based Bounded Model Checking (BMC), though a robust and scalable verification approach, still is computationally intensive, requiring large memory and time. Even with the recent development of improved SAT solvers, the memory limitation of a single server rather than time can become a bottleneck for doing deeper BMC search for large designs. Distributing computing requirements of BMC over a network of workstations can overcome the memory limitation of a single server, albeit at increased communication cost. In this paper, we present (a) a method for distributed SAT over a network of workstations using a Master/Client model where each Client workstation has an exclusive partition of the SAT problem and uses knowledge of partition topology to communicate with other Clients, (b) a method for distributing SAT-based BMC using the distributed SAT. For the sake of scalability, at no point in the BMC computation does a single workstation have all the information. We experimented on a network of heterogeneous workstations interconnected with a standard Ethernet LAN. To illustrate, on an industrial design with ∼13 K FFs and ∼0.5 million gates, the non-distributed BMC on a single workstation (with 4 GB memory) ran out of memory after reaching a depth of 120; on the other hand, our SAT-based distributed BMC over 5 similar workstations was able to go up to 323 steps with a communication overhead of only 30%.     

基于LMfr-IPDA的有限传感器分辨率多目标跟踪

以往的目标跟踪算法大多假定传感器分辨率是无限的,即量测与目标一一对应,而这并不符合实际.对此,提出一种利用线性多目标(LM)跟踪算法简化结构获得LM有限分辨率(LMfr)跟踪算法,并将其与集成概率数据关联(IPDA)相结合,推导出LMfr-IPDA多目标跟踪算法.仿真实验中,注重于虚假航迹的辨别性能与航迹保持能力,将LMfr-IPDA与LM-IPDA和IPDA在杂波环境中使用有限分辨率传感器对6个交叉目标的目标跟踪性能进行了比较,从而验证了算法的有效性.     

最短路径树的马尔可夫有限阶段决策算法

本文从决策的角度出发,结合马尔可夫决策过程理论,建立了计算最短路径树（SPT）的有限阶段决策模型.引入一个辅助图：反转图,结合它修改了模型的理论求解算法,提出了SPT反转递归迭代算法,并证明了算法的正确性.在此基础上,又提出了不使用反转图的改进模型和算法.算法的时间和空间复杂度分析表明：本文提出的算法具有分布式并行计算的特点,可以均衡各节点的工作负载,降低时间和空间复杂度,并可以有效防止环路的产生,因此可以有效应用于资源匮乏的嵌入式互连环境和对等网络环境中.     

Applying SAT Solving in Classification of Finite Algebras

The classification of mathematical structures plays an important role for research in pure mathematics. It is, however, a meticulous task that can be aided by using automated techniques. Many automated methods concentrate on the quantitative side of classification, like counting isomorphism classes for certain structures with given cardinality. In contrast, we have devised a bootstrapping algorithm that performs qualitative classification by producing classification theorems that describe unique distinguishing properties for isomorphism classes. In order to fully verify the classification it is essential to prove a range of problems, which can become quite challenging for classical automated theorem provers even in the case of relatively small algebraic structures. But since the problems are in a finite domain, employing Boolean satisfiability solving is possible. In this paper we present the application of satisfiability solvers to generate fully verified classification theorems in finite algebra. We explore diverse methods to efficiently encode the arising problems both for Boolean SAT solvers as well as for solvers with built-in equational theory. We give experimental evidence for their effectiveness, which leads to an improvement of the overall bootstrapping algorithm.     

基于SAT的串扰时延故障测试

随着深亚微米技术的不断发展和芯片运行速率的不断提高,串扰噪声问题越来越严重,对串扰时延测试已成为一个迫切的问题。在组合电路的基础上,将SAT（布尔可满足性）方法引入到串扰引起的时延测试中,通过词法分析和语法分析直接提取Verilog（硬件描述语言）源码的形式模型,组合成CNF（合取范式）形式。并在非鲁棒测试条件下,激活串扰时延故障,约简CNF范式表达式,最终输入SAT求解器得到测试矢量。在标准电路 ISCAS’85上进行实验验证,结果表明：该算法对于串扰时延故障的测试矢量产生是有效的。     

Reducing Symmetries to Generate Easier SAT Instances

Finding countermodels is an effective way of disproving false conjectures. In first-order predicate logic, model finding is an undecidable problem. But if a finite model exists, it can be found by exhaustive search. The finite model generation problem in the first-order logic can also be translated to the satisfiability problem in the propositional logic. But a direct translation may not be very efficient. This paper discusses how to take the symmetries into account so as to make the resulting problem easier. A static method for adding constraints is presented, which can be thought of as an approximation of the least number heuristic (LNH). Also described is a dynamic method, which asks a model searcher like SEM to generate a set of partial models, and then gives each partial model to a propositional prover. The two methods are analyzed, and compared with each other.     

油藏数值模拟有限元并行计算方法研究

针对目前油藏数值模拟普遍采用的有限差分法计算精度低的问题,提出了兼顾计算精度、计算速度问题的有限元油藏数值模拟方法,即在建立了油藏数值模拟数学模型的基础上通过有限元数值分析方法建立有限元数值模型,但有限元在油藏数值模拟时存在单机计算困难、计算时间长的问题,为此提出了利用区域分解技术的油藏数值模拟并行计算方法,最后将该方法通过实例进行检验,取得了良好的加速比和并行效率。     

程序中不可达路径的检测方法

对于大型软件来说,程序中不可达路径的存在增加了软件测试的耗费并严重影响了测试的准确性。通过在已生成的基本路径集中排除不可达路径的影响,有利于结构测试中各阶段的实现。提出了一种利用数据流分析信息检测不可达路径的方法。通过对条件分支相关性的探测进而确定了程序中的不可达路径,并通过适当地选取条件谓词,提高了检测分支的覆盖率。     

Unary Quantifiers on Finite Models

In this paper (except in Section 5) all quantifiers are assumedto be so called simple unaryquantifiers, and all models are assumedto be finite. We give a necessary and sufficientcondition for a quantifier to be definablein terms of monotone quantifiers. For amonotone quantifier we give a necessaryand sufficient condition for beingdefinable in terms of a given set of bounded monotonequantifiers. Finally, we give a necessaryand sufficient condition for a monotonequantifier to be definable in terms of agiven monotone quantifier.Our analysis shows that the quantifierat least one half and its relatives behavedifferently than other monotone quantifiers.     

基于有限元的衰荡光腔内温度分布仿真

衰荡光腔受温度影响长度变化使腔内光斑模式改变,影响测量精度,为达到衰荡光腔内温度均匀分布,利用仿真平台,对控温箱体内加热片发热功率进行仿真计算.首先设计控温箱体几何模型,确定热传导模型和边界条件,通过有限元分析初步确定控温箱体内温度分布;然后通过参数化扫描和迭代运算,优化控温箱体温度场分布,得到均匀化温度分布所需的各加...     

一种基于搜索路径识别的CDCL命题逻辑求解器延迟重启算法

适当的重启有助于求解器跳出局部最优,但频繁重启会严重降低效率。为解决CDCL求解器重启触发条件随意性大的问题,提出一种基于搜索路径识别的延迟重启算法。该算法使用Luby序列触发延时重启判断,将当前搜索路径和已搜索路径转换为向量空间模型,通过计算向量空间相似度来判断当前搜索过程是否会进入重复搜索空间。若向量空间相似度达到设定阈值,则触发重启,否则延迟重启。采用SAT国际竞赛的实例,与两个主流的求解器进行了对比实验。结果表明,所提算法能够有效规避重复搜索空间问题,并显著提高求解效率。     

Real-time Volumetric Deformable Models for Surgery Simulation using Finite Elements and Condensation

This paper discusses the application of 3D solid volumetric Finite Element models to surgery simulation. In particular it introduces three new ideas for solving the problem of achieving real-time performance for these models. The simulation system we have developed is described and we demonstrate real-time deformation using the methods developed in the paper.     

复杂网络中最短路径问题的求解算法研究

本文以时间代价作为目标函数,针对复杂网络的优化问题进行研究,给出了目标评价函数模型的建立过程,提出了改进的A＊算法求解复杂网络中最短路径问题的算法,并以城市交通为例,对算法进行了验证,实验结果表明所提出的算法可适用于一般多重图中最短路径问题的快速求解,具有广泛的应用价值。     

销钉连接叶片固有特性分析有限元模型研究

计算销钉连接转子叶片动频需采用有限元接触技术,而非线性接触分析难度和计算量都较大,因此提出两种线性简化工程模型,将求解非线性问题转换为求解线性问题,从而大大降低了分析难度和计算量.经检验其计算结果精度可满足工程分析要求.同时对简化柔度矩阵法及面约束简化模型有限元法计算的动频结果进行了分析,对发动机叶片固有振动特性分析有帮助.     

测点数据生成刀具路径研究

为了提高反求加工的效率，提出由大规模测点数据直接生成粗、精加工刀具路径的算法．粗加工采用层切法分层切削材料，首先构造健壮的数据结构——层切网；然后计算无干涉刀位点，并把整个层切网划分为几个优化的子加工区域；最后应用优化的刀路链接法则得到粗加工刀具路径．精加工由大规模数据点构建三角曲面．为了避免干涉，需计算点、面和边的无干涉刀位点．实验结果表明，粗加工刀具路径算法具有较高的效率，只需要占用较小的内存空间；精加工可以成功地避免干涉并且获得可靠的表面精度．     

基于Finite Ridgelet变换的图像线性特征提取

线性特征是图像的一种重要局部特征,它常常决定图像中目标的形状。线性特征的提取在图像匹配、目标描述与识别以及运动估计、目标跟踪等领域具有十分重要的意义。常用的线性特征检测方法有Radon变换和Hough变换,但检测曲线复杂度会很高。本文提出一种多尺度几何分析的线性特征检测方法,该方法以finite ridgelet理论为基础,结合正交小波变换对线性特征进行提取。Finite ridgelet变换对于含有直线奇异的多变量函数具有良好的逼近特性,能够获得连续空间函数的稀疏表达,同时具有区域平滑性、很好的可逆性和去冗余性。实验结果表明,本方法即使在背景复杂的环境下也具有良好的检测效果。     

基于两层编码遗传算法的机器人路径规划

讨论了在障碍物已知的二维环境里,在两上已知点之间寻找最短欧氏路径的问题,用了一种基于遗传算法的新的空间分割的方法,在遗传算法中,提出了一种新的编码方法－两层编码,这种编码来源于分子数量遗传学中的遗传机制,它能够大大夺强编码的表达能力,这种方法的核心就在于通过中间层编码来降低搜索的复杂度。