采用动态邻域扩展算法的非一致CA低功耗确定TPG

针对确定内建自测试向量发生器设计中常存在着对冗余向量依赖,导致测试应用时间增长,并产生额外的测试功耗等问题,提出一种新的低功耗确定测试向量发生器的综合算法.该向量发生器采用非一致细胞自动机的结构实现,利用基于模拟退火的动态邻域扩展算法寻找优化的细胞自动机的拓扑连接关系.对标准组合电路仿真实验的结果表明,所综合出的向量发生器可有效地产生给定的低功耗确定向量集,并且不影响原有的故障覆盖率和测试时间.     

Incremental integration testing of concurrent programs

We present a method for selecting test sequences for concurrent programs from labeled transitions systems (LTS). A common approach to selecting test sequences from a set of LTSs is to derive a global LTS, called the reachability graph, and then force deterministic program executions according to paths selected from the graph. However, using a reachability graph for test path selection introduces a state explosion problem. To overcome this problem, a reduced graph can be generated using incremental reachability analysis, which consists of repeatedly generating a reachability graph for a subset of LTSs, reducing this graph, and using the reduced graph in place of the original LTSs. Unfortunately, existing incremental reachability analysis techniques generate reduced graphs with insufficient information for deterministic testing. We present an incremental approach to testing concurrent programs. Incremental testing consists of incremental reachability analysis for test path selection and deterministic testing for test execution. We define a new type of reachability graph for incremental analysis, called an annotated labeled transition system (ALTS). An ALTS is an LTS annotated with information necessary for deterministic testing. We propose practical coverage criteria for selecting tests paths from an ALTS and present an ALTS reduction algorithm. The results of several case studies are reported     

Generating tests for delay faults in nonscan circuits

A delay test method that allows any sequential-circuit test generation program to produce path delay tests for nonscan circuits is presented. Using this method, a given path is tested by augmenting the netlist model of the circuit with a logic block, in which testing for a certain single stuck-at fault is equivalent to testing for a path delay fault. The test sequence for the stuck-at fault performs all the necessary delay fault test functions: initialization, path activation, and fault propagation. Results on benchmarks are presented for nonscan and scan/hold modes of testing     

A loop-based apparatus for at-speed self-testing

At-speed testing using external tester requires an expensive equipment,thus built-in self-test(BIST) is an alternative technique due to its ability to perform on-chip at-speed self-testing.The main issue in BIST for at-speed testing is to obtain high delay fault coverage with a low hardware overhead.This paper presents an improved loop-based BIST scheme,in which a configurable MISR (multiple-input signature register)is used to generate test-pair sequences.The structure and operation modes of the BIST scheme are described.The topological properties of the state-transition-graph of the proposed BIST scheme are analyzed.Based on it ,an approach to design and efficiently implement the proposed BIST scheme is developed.Experimental results on academic benchmark circuits are presented to demonstrate the effectiveness of the proposed BIST scheme as well as the design approach.     

基于优化编码的LFSR重播种测试压缩方案

大规模高密度集成电路测试中存在测试数据量大、测试功耗高等问题.提出了一种先通过编码优化测试集,再使用线性反馈移位寄存器(linear feedback shift register,LFSR)重播种的内建自测试方案.该方案通过自动测试模式生成工具得到被测电路的确定测试集,再压缩为种子集存储在片上ROM中.压缩测试集的过程中,首先以降低测试功耗为目标,用少量确定位编码测试集中的部分测试立方,来增强解码后测试模式相邻位之间的一致性;然后以提高压缩率同时降低LFSR级数为目标,将测试立方编码为确定位含量更少的分段相容码(CBC),最后将以CBC编码的测试立方集压缩为LFSR种子集.实验证明所提出的方案在不影响故障覆盖率的前提下大量降低了测试功耗,并且具有更高的测试数据压缩率.     

Estimating the feasibility of transition paths in extended finite state machines

There has been significant interest in automating testing on the basis of an extended finite state machine (EFSM) model of the required behaviour of the implementation under test (IUT). Many test criteria require that certain parts of the EFSM are executed. For example, we may want to execute every transition of the EFSM. In order to find a test suite (set of input sequences) that achieves this we might first derive a set of paths through the EFSM that satisfy the criterion using, for example, algorithms from graph theory. We then attempt to produce input sequences that trigger these paths. Unfortunately, however, the EFSM might have infeasible paths and the problem of determining whether a path is feasible is generally undecidable. This paper describes an approach in which a fitness function is used to estimate how easy it is to find an input sequence to trigger a given path through an EFSM. Such a fitness function could be used in a search-based approach in which we search for a path with good fitness that achieves a test objective, such as executing a particular transition, and then search for an input sequence that triggers the path. If this second search fails then we search for another path with good fitness and repeat the process. We give a computationally inexpensive approach (fitness function) that estimates the feasibility of a path. In order to evaluate this fitness function we compared the fitness of a path with the ease with which an input sequence can be produced using search to trigger the path and we used random sampling in order to estimate this. The empirical evidence suggests that a reasonably good correlation (0.72 and 0.62) exists between the fitness of a path, produced using the proposed fitness function, and an estimate of the ease with which we can randomly generate an input sequence to trigger the path.     

一个有效的通路时滞故障测试生成系统DTPG

本文提出了一种两向量测试模式下的通路时滞故障分类，并在此基础上设计并实现了一个有效的通路时滞故障测试生成系统ＤＰＴＧ，该系统可识别强健可测通路、非强度可测通路和功能可敏化 通路。     

基于测量的时延故障诊断

与时延测试相比,时延故障诊断需要更精确的故障模型。该文提出了采用精确测量的时延模型和时延故障模型。在这种模型下,利用电路通路图的原理,得到与被测电路的拓扑结构有关的一个精简测试集。测试集的大小与电路的大小保持线性增长关系;其中的每一个测试对应于一条通路的单跳变敏化向量,将测试集中的单跳变敏化向量送入被测电路,可以用测试仪测量相应通路的延时,得到电路关于此测试集的时延故障症候。该文对时延故障症候提供     

An optimal representative set selection method

The optimal representative set selection problem is defined thus: given a set of test requirements and a test suite that satisfies all test requirements, find a subset of the test suite containing a minimum number of test cases that still satisfies all test requirements. Existing methods for solving the representative set selection problem do not guarantee that obtained representative sets are optimal (i.e. minimal). The enhanced zero–one optimal path set selection method [C.G. Chung, J.G. Lee, An enhanced zero–one optimal path set selection method, Journal of Systems and Software, 39(2) (1997) 145–164] solves the so-called optimal path set selection problem, and can be adapted to solve the optimal representative set selection problem by considering paths as test cases and components to be covered (e.g. branches) as test requirements.     

Real-time path planning with limited information for autonomous unmanned air vehicles

We propose real-time path planning schemes employing limited information for fully autonomous unmanned air vehicles (UAVs) in a hostile environment. Two main algorithms are proposed under different assumptions on the information used and the threats involved. They consist of several simple (computationally tractable) deterministic rules for real-time applications. The first algorithm uses extremely limited information (only the probabilistic risk in the surrounding area with respect to the UAV's current position) and memory, and the second utilizes more knowledge (the location and strength of threats within the UAV's sensory range) and memory. Both algorithms provably converge to a given target point and produce a series of safe waypoints whose risk is almost less than a given threshold value. In particular, we characterize a class of dynamic threats (so-called, static-dependent threats) so that the second algorithm can efficiently handle such dynamic threats while guaranteeing its convergence to a given target. Challenging scenarios are used to test the proposed algorithms.     

Testing methodology: implications for the circuit designer

The complexity achievable within a custom chip or on a PCB loaded with standard combinational or sequential elements, even without the use of VLSI components such as microprocessors, requires the use of automatic methods for the generation of test patterns if the task is to be completed within an acceptable time and at an acceptable cost. This paper reviews the current status of some aspects of the test process as applied to such circuits, and of the principles of structured design methodologies intended to reduce the difficulties of test pattern generation (TPG). The paper starts by reviewing the fault models on which most automatic TPG (ATPG) methods are based, and goes on to discuss some of the available ATPG methods themselves. The problems involved in TPG for sequential circuits are briefly discussed to show the motivation behind structured design for testability using the scan-in scan-out (SISO) principle. The main implications of SISO are described, as are some of the applications of these principles to the construction of testable PCBs.     

无人机空中基站对地信道建模及功率覆盖预测

传统统计建模方法难以对特定场景下的无人机信道做出精确预测。针对城市场景下的无人机信道,结合确定性信道建模法,基于射线跟踪原理构建了一种无人机基站-地信道模型,该模型考虑了散射次数对接收功率的影响,将到达地面接收机的射线分为视距路径、一次散射路径和二次散射路径;给出了基于射线跟踪原理的传播损耗和3种路径相应的功率计算方法,该方法沿路径计算场强。在利用数字地图预处理技术对城市建筑物进行简化后,对该场景下无人机信道的传播路径、损耗、功率延迟分布以及功率覆盖情况进行了仿真验证。数值仿真结果表明,本模型能够准确复现城市传播环境及传播状况,覆盖预测结果可用于优化无人机部署。     

Test Time Minimization for Hybrid BIST of Core-Based Systems

This paper presents a solution to the test time minimization problem for core-based systems. We assume a hybrid BIST approach, where a test set is assembled, for each core, from pseudorandom test patterns that are generated online, and deterministic test patterns that are generated off-line and stored in the system. In this paper we propose an iterative algorithm to find the optimal combination of pseudorandom and deterministic test sets of the whole system, consisting of multiple cores, under given memory constraints, so that the total test time is minimized. Our approach employs a fast estimation methodology in order to avoid exhaustive search and to speed-up the calculation process. Experimental results have shown the efficiency of the algorithm to find near optimal solutions.     

Lag synchronization of complex dynamical networks with randomly occurring parameter uncertainties and control packet loss via stochastic sampled-data control

ABSTRACT

This paper focuses on the lag synchronization of two general complex dynamical networks with randomly occurring parameter uncertainties and control packet loss. The randomly occurring uncertainties are adopted to reflect more realistic dynamical behaviours of complex networks that are caused by noisy environment. By introducing a Bernoulli distributed stochastic variable, the information of probabilistic time-varying delay is transformed into the deterministic time-varying delay with stochastic parameters. Sampled-data controllers with stochastically varying sampling intervals are considered and a switched system is used to describe packet dropouts in a deterministic way. Some sufficient conditions for the lag synchronization in the mean square are derived in terms of constructing an appropriate Lyapunov function and using linear matrix inequalities. Finally, a numerical example is given to show the effectiveness of the theoretical results.     

一种基于分支覆盖的测试数据自动生成算法

通过构造新的程序流图，利用Fibonacci法优化选取路径．为指定的分支生成测试数据。提出了路径测试数据生成代价的概念，并给出了代价的计算方法。当所选路径的分支谓词均为线性表达式时，直接求解线性约束集即可生成测试数据，或判定路径不可行；当分支谓词含有非线性表达式时，利用均差近似导数将非线性函数线性化，通过简单的迭代，亦能容易生成测试数据或判定路径在很大程度上不可行。若所选路径不可行或在很大程度上不可行，则选取新的路径，重复以上过程，直至求出所期望的数据，或无新的路径被选取，给定分支不可达。实例和实验表明，算法可行、有效。     

A test-pattern-generation algorithm for sequential circuits

A deterministic test-pattern-generation algorithm for synchronous sequential circuits is presented. The algorithm, called Essential, takes advantage of a procedure for learning global implications. It uses static and dynamic dominance relationships among signals, the concept of the potential propagation path, and intelligent heuristics to guide and accelerate the decision-making process for deterministic automatic test pattern generation (ATPG). Essential is based on the well-known method of reverse time processing, but it applies forward processing within time frames to avoid disadvantageous a priori determination of a path to be sensitized or of a primary output to which the fault effects must be propagated. It is designed to exploit fully the sophisticated techniques used for combinational circuits in the Socrates ATPG system. Experimental results for sequential ATPG obtained with Essential (implemented in C on a Sequent Symmetry computer) are reported     

A robust critical path in an environment with hybrid uncertainty

In this article, we consider the project critical path problem in an environment with hybrid uncertainty. In this environment, the duration of activities are considered as random fuzzy variables that have probability and fuzzy natures, simultaneously. To obtain a robust critical path with this kind of uncertainty a chance constraints programming model is used. This model is converted to a deterministic model in two stages. In the first stage, the uncertain model is converted to a model with interval parameters by alpha-cut method and distribution function concepts. In the second stage, the interval model is converted to a deterministic model by robust optimization and min-max regret criterion and ultimately a genetic algorithm with a proposed exact algorithm are applied to solve the final model. Finally, some numerical examples are given to show the efficiency of the solution procedure.     

Testing for Perturbations of Program Statements

Many testing methods require the selection of a set of paths on which tests are to be conducted. Errors in arithmetic expressions within program statements can be represented as perturbing functions added to the correct expression. It is then possible to derive the set of errors in a chosen functional class which cannot possibly be detected using a given test path. For example, test paths which pass through an assignment statement "X := f(Y)" are incapable of revealing if the expression "X -f( Y)" has been added to later statements. In general, there are an infinite number of such undetectable error perturbations for any test path. However, when the chosen functional class of error expressions is a vector space, a finite characterization of all undetectable expressions can be found for one test path, or for combined testing along several paths. An analysis of the undetected perturbations for sequential programs operating on integers and real numbers is presented which permits the detection of multinomial error terms. The reduction of the space of (potential undetected errors is proposed as a criterion for test path selection.     

A Test Approach for Look-Up Table Based FPGAs

This paper describes a test architecture for minimum number of test configurations in test of FPGA （Field Programmable Gate Array） LUTs （Look Up Tables）. The test architecture includes a TPG （Test Pattern Generator） that is tested while it is generating test data for LEs （Logic Elements） that form the CUT （Circuit Under Test）. This scheme eliminates the need for switching LEs between CUT, TPG and ORA （Output Response Analyzer） and having to perform many more reconfiguratioas of the FPGA. An external ORA locates faults of the FPGA under test. In addition to the LUTs, a scheme is presented for testing other parts of LEs. Compared with other methods, the presented scheme uses the least number of reconfigurations of an FPGA for its LUT testing.     

A System to Generate Test Data and Symbolically Execute Programs

This paper describes a system that attempts to generate test data for programs written in ANSI Fortran. Given a path, the system symbolically executes the path and creates a set of constraints on the program's input variables. If the set of constraints is linear, linear programming techniques are employed to obtain a solution. A solution to the set of constraints is test data that will drive execution down the given path. If it can be determined that the set of constraints is inconsistent, then the given path is shown to be nonexecutable. To increase the chance of detecting some of the more common programming errors, artificial constraints are temporarily created that simulate error conditions and then an attempt is made to solve each augmented set of constraints. A symbolic representation of the program's output variables in terms of the program's input variables is also created. The symbolic representation is in a human readable form that facilitates error detection as well as being a possible aid in assertion generation and automatic program documentation.