采用基本门单元完全测试矢量的测试生成算法

文章介绍了一种采用基本逻辑门单元的安全测试矢量集生成测试矢量的方法，该方法可以将搜索空间限制在2(n 1）种组合内。它采用故障支配和故障等效的故障传播、回退等技术，建立了一套从局部到全局的测试生成新方法。同时，利用基本门单元安全测试矢量的规律性，可以实现最小的内存容量要求。在一些基准电路的应用实例中，得到了满意的结果。     

Extended selection of switching target faults in CONT algorithm for test generation

We describe an extended selection of switching target faults in the CONT algorithm. The main difficulty in test generation is the conflict that arises in the process of determining the signal values due to reconvergent fanouts. Conventional approaches for test generation change a signal value, which causes conflicts to another possible choice for backtracking. In the CONT algorithm, a strategy of switching target fault was proposed as a new backtracking mechanism. In this method, the target fault is switched to a new target fault instead of making an alternative assignment on the primary input value when a conflict occurs. A disadvantage of the CONT algorithm is that unjustified lines exist in the process of test generation. These unjustified lines make the procedure of switching targets complicated and restrict the possible choice in selecting the new target fault. In the new version of CONT, called CONT-2, we have removed the unjustified lines in the process of test generation and have extended to two target-fault types for switching targets. Implementing CONT-2 by a Fortran program, ISCAS85 benchmark circuits are examined. Experiments on a combined system with fault simulation followed by CONT-2 are also presented.     

多攻击线引起的串扰时延故障的TPG

探讨了一种串扰时延最大化算法,并且利用被修改的FAN算法,生成测试矢量.对于一条敏化通路,利用被修改的FAN算法适当地激活相应的攻击线和受害线,使电路在最恶劣情况下引起最大通路时延,从而实现更有效的时延测试.利用了FAN算法的多路回退和回溯等主要特色,提高了测试生成算法的效率.实验结果表明,沿着任何临界通路传播的受害线相耦合的攻击线被适当地激活,并且可以对一定规模的电路的串扰时延故障进行测试矢量生成.     

FIRE: a fault-independent combinational redundancy identificationalgorithm

FIRE is a novel Fault-Independent algorithm for combinational REdundancy identification. The algorithm is based on a simple concept that a fault which requires a conflict as a necessary condition for its detection is undetectable and hence redundant. FIRE does not use the backtracking-based exhaustive search performed by fault-oriented automatic test generation algorithms, and identifies redundant faults without any search. Our results on benchmark and real circuits indicate that we find a large number of redundancies (about 80% of the combinational redundancies in benchmark circuits), much faster than a test-generation-based approach for redundancy identification. However, FIRE is not guaranteed to identify all redundancies in a circuit     

A switch-level test generation system for synchronous and asynchronous circuits

A switch-level test generation system for synchronous and asynchronous circuits has been developed in which a new algorithm for fully automatic switch-level test generation and an existing fault simulator have been integrated. For test generation, a switch-level circuit is modeled as a logic network that correctly models the behavior of the switch-level including bidirectionality, dynamic charge storage, and ratioed logic. The algorithm is able to generate tests for combinational and sequential circuits. BothnMOS and CMOS circuits can be modeled. In addition to the classical line stuck-at faults, the algorithm is able to handle stuck-open and stuck-closed faults on the transistors of the circuit.In synchronous circuits, the time-frame based algorithm uses asynchronous processing within each clock phase to achieve stability in the circuit and synchronous processing between clock phases to model the passage of time. In asynchronous circuits, the algorithm uses asynchronous processing to reach stability within and between modules. Unlike earlier time-frame based test generators for general sequential circuits, the test generator presented uses the monotonicity of the logic network to speed up the search for a solution. Results on benchmark circuits show that the test generator outperforms an existing switch-level test generator both in time and space requirements. The algorithm is adaptable to mixed-level test generation.     

The Range Extender with Gain--A New Telephone System Loop Extender

Approximately 2 percent of Bell System loops are longer than the central office switching equipment design limit of 1300 Ω. These long loops require treatment on a special basis with the use of so-called long line circuits and voice frequency repeaters. The complexity, cost, and lack of a simple way to test the loop through these circuits led to a new design. In this paper, we describe the REG, an integrated signaling Range Extender with a voice frequency Gain unit which overcomes these shortcomings. The key to providing the improved features is a novel electronic dual-mode current detector. The requirements and design of the current detector are covered in detail. Finally, we discuss REG operation illustrating the problems of the switching system interface.     

时序电路测试生成新算法研究

为解决同步时序电路的测试难题,提高时序电路测试生成效率,进行了时序电路测试生成算法的研究,将粒子群优化算法应用在时序电路的测试生成中。为验证PSO算法性能,首先将其用于函数优化,能获得较好的优化结果。之后建立自动测试生成离散粒子群速度—位置模型,针对国际标准时序电路的验证结果表明,与同类算法相比,该算法可以获得较高的故障覆盖率和较小的测试矢量集。     

A hierarchical test generation methodology for digital circuits

A new hierarchical modeling and test generation technique for digital circuits is presented. First, a high-level circuit model and a bus fault model are introduced—these generalize the classical gate-level circuit model and the single-stuck-line (SSL) fault model. Faults are represented by vectors allowing many faults to be implicitly tested in parallel. This is illustrated in detail for the special case of array circuits using a new high-level representation, called the modified pseudo-sequential model, which allows simultaneous test generation for faults on individual lines of a multiline bus. A test generation algorithm called VPODEM is then developed to generate tests for bus faults in high-level models of arbitrary combinational circuits. VPODEM reduces to standard PODEM if gate-level circuit and fault models are used. This method can be used to generate tests for general circuits in a hierarchical fashion, with both high- and low-level fault types, yielding 100 percent SSL fault coverage with significantly fewer test patterns and less test generation effort than conventional one-level approaches. Experimental results are presented for representative circuits to compare VPODEM to standard PODEM and to random test generation techniques, demonstrating the advantages of the proposed hierarchical approach.     

Computing multivalued input-output Characteristics in the circuits containing bipolar transistors

The paper deals with dc circuits including bipolar transistors represented by the Ebers-Moll model. An important question how to efficiently compute multivalued input-output characteristics of these circuits is considered. A switching variables approach for tracing a multivalued single-branched characteristic, which can be considered as some kind of continuation method, is developed. A new strategy of switching variables is proposed and the generalized implicit function theorem is used as the mathematical background. Unfortunately, this approach suffers from major shortcomings when it is directly applied to bipolar transistor circuits, due to specific nonlinearities of the transistor model, causing the sharp-turning-point problem. To overcome this problem, a variable transformation is proposed, which leads to smooth solution curves. An efficient algorithm combining the developed variant of switching variable method with the proposed transformation is described. A generalized version of the algorithm enables us to compute multivalued characteristics composed of disconnected branches, under the assumption that at least one point on each branch can be found. It is illustrated via four examples of realistic transistor circuits including a voltage regulator, the Schmitt trigger, a line receiver, and their combination.     

A novel automatic test pattern generator for asynchronous sequential digital circuits

A novel automatic test pattern generator (ATPG) for stuck-at faults of asynchronous sequential digital circuits is presented. The developed ATPG does not require support by any design-for-testability method nor external software tool. The shortest test sequence generation is guaranteed by breadth-first search. The contribution is unique hazard identification before the test generation process, state justification on the gate level, sequential fault propagation based on breadth-first search and stepwise composition of state graphs for sequential test generation. A new six-valued logic together with a new algorithm was developed for hazardous transition identification. The internal combinational ATPG allows to generate test patterns one by one and only if it is required by sequential test generation. The developed and implemented ATPG was tested with speed-independent and quasi-delay-insensitive benchmark circuits.     

Transitional gate delay detection for combinational circuits usinga genetic algorithm

The authors present a new technique for the generation of test vector-pairs that detect both delay and single stuck-at-fault conditions in digital logic circuits. A genetic algorithm (GA), is used to pursue and extract efficient tests from a complex search space. Results obtained for the ISCAS 1985 benchmark circuits compare favourably with the results of other researchers, even when the genetic system considers both delay and single stuck-at-fault models     

Partitioning sequential circuits for pseudoexhaustive testing

In this paper, we present an algorithm for partitioning sequential circuits. This algorithm is based on an analysis of a circuit's primary input cones and fanout values (PIFAN), and it uses a directed acyclic graph to represent the circuit. An invasive approach is employed, which creates logical and physical partitions by automatically inserting reconfigurable test cells and multiplexers. The test cells are used to control and observe multiple partitioning points, while the multiplexers expand the controllability and observability provided by the test cells. The feasibility and efficiency of our algorithm are evaluated by partitioning numerous standard digital circuits, including some large benchmark circuits containing up to 5597 gates. Our algorithm is based upon pseudoexhaustive testing methods where fault simulation is not required for test-pattern generation and grading; hence, engineering design time and cost are further reduced     

Test Planning for Core-based Integrated Circuits under Power Constraints

This paper addresses reduction of test cost for core-based non-stacked integrated circuits (ICs) and stacked integrated circuits (SICs) by test planning, under power constraint. Test planning involves co-optimization of cost associated with test time and test hardware. Test architecture is considered compliant with IEEE 1149.1 standard. A cost model is presented for calculating the cost of any test plan for a given non-stacked IC and a SIC. An algorithm is proposed for minimizing the cost. Experiments are performed with several ITC’02 benchmark circuits to compare the efficiency of the proposed power constrained test planning algorithm against near optimal results obtained with Simulated Annealing. Results validate test cost obtained by the proposed algorithm are very close to those obtained with Simulated Annealing, at significantly lower computation time.     

A new fault independent test generation algorithm for combinational logic circuits

In order to improve the performance of fault independent test generation algorithms, two strategies are proposed: a critical lines maximization strategy (CLM) and a critical primary inputs flipping strategy (CPF). CLM is used to maximize the number of detected faults while generating a test pattern. CPF is used to derive new test pattern(s) from a generated test pattern with little additional effort. A new fault independent test generation algorithm (MAX) based on these strategies is introduced and illustrated.     

A test methodology for finite state machines using partial scan design

This paper presents an efficient automatic test pattern generation technique for loop-free circuits. A partial scan technique is used to convert a sequential circuit (finite state machine) with arbitrary feedback paths into a pipelined circuit for testing. Test generation for these modified circuits can be performed with a modified combinational automatic test pattern generator (ATPG), which is much faster than a sequential ATPG. A combinational model is obtained by replacing all flipflops by buffers. It is shown that a test vector for a fault in this model obtained by a combinational test generator can be expanded into a sequence of identical vectors to detect the same fault in the original sequential circuit. This technique may abort a few faults which can then be resolved with a sequential ATPG. Experiments on the ISCAS89 circuits show that only 30% to 70% of flipflops require scanning in larger circuits and 96% to 100% fault coverage for almost all the circuits without resorting to a sequential ATPG.This research was sponsored by the Semiconductor Research Corporation, Contract 90-DP-142.     

Application of the maximum principle for the circuits optimization

The solution of the problem of computational time reduce during optimization of electronic circuits allows to enhance the development quality. Generalized methodology of the circuits optimization developed before on a basis of optimal control allows to define many different optimization strategies. Definition of Lyapunov’s function of optimization process and its analysis for different strategies allows to compare these strategies from viewpoint of computational burden and select the best of them. At the same time the most grounded approach for the search of optimal development strategy in this statement is Pontryagin maximum principle. But application of this principle for solution of non-linear problems is related to essential complications. In this paper it is obtained the solution of electronic circuit optimization problem during minimal amount possible processor time on a basis of Pontryagin maximum principle in general case of N variables. It is shown that effect studied before for acceleration of the process of optimization coincides the solution on a basis of the maximum principle. This fact is the theoretical explanation of the acceleration effect. From the other hand the principle of maximum can be the basis for development of the algorithm for electronic circuits optimization with minimal processor time cost.     

On the generation of test patterns for multiple faults

This article presents a new method to generate test patterns for multiple stuck-at faults in combinational circuits. We assume the presence of all multiple faults of all multiplicities and we do not resort to their explicit enumeration: the target fault is a single component of possibly several multiple faults. New line and gate models are introduced to handle multiple fault effect propagation through the circuits. The method tries to generate test conditions that propagate the effect of the target fault to primary outputs. When these conditions are fulfilled, the input vector is a test for the target fault and it is guaranteed that all multiple faults of all multiplicities containing the target fault as component are also detected. The method uses similar techniques to those in FAN and SOCRATES algorithms to guide the search part of the algorithm, and includes several new heuristics to enhance the performance and fault detection capability. Experiments performed on the ISCAS'85 benchmark circuits show that test sets for multiple faults can be generated with high fault coverage and a reasonable increase in cost over test generation for single stuck-at faults.     

A New Duty Cycle Control Strategy for Power Factor Correction and FPGA Implementation

The bottleneck of digital control for power factor correction (PFC) implementations is mainly due to three aspects: high calculation requirements, high cost, and limited switching frequency compared with analog implementations. A new duty cycle control strategy for boost PFC implementations is proposed in this paper. The duty cycle is determined based on the input voltage, reference output voltage, inductor current, and reference current. The duty cycle determination algorithm includes two terms, the current term and the voltage term, which can be calculated in parallel and requires only one multiplication and three additions (subtractions) operations in digital implementation. A 400-kHz switching frequency boost PFC based on field programmable gate array implementation and its test results show that the proposed new duty cycle control strategy has great potential in the next generation of high switching frequency PFC implementations, due to its lower calculation requirement, lower cost, and better performance than the conventional PFC control methods     

New Techniques for Deterministic Test Pattern Generation

This paper presents new techniques for speeding up deterministic test pattern generation for VLSI circuits. These techniques improve the PODEM algorithm by reducing number of backtracks with a low computational cost. This is achieved by finding more necessary signal line assignments, by detecting conflicts earlier, and by avoiding unnecessary work during test generation. We have incorporated these techniques into an advanced ATPG system for combinational circuits, called ATOM. The performance results for the ISCAS85 and full scan version of the ISCAS89 benchmark circuits demonstrated the effectiveness of these techniques on the test generation performance. ATOM detected all the testable faults and proved all the redundant faults to be redundant with a small number of backtracks in a short amount of time.     

A synthesis-based test generation and compaction algorithm for multifaults

Because of its inherent complexity, the problem of automatic test pattern generation for multiple stuck-at faults (multifaults) has been largely ignored. Recently, the observation that multifault testability is retained by algebraic factorization demonstrated that single fault (and therefore multifault) vector sets for two-level circuits could give complete multifault coverage for multilevel circuits constructed by algebraic factorization. Unfortunately, in using this method the vector set size can be much larger than what is really required to achieve multifault coverage, and the approach has some limitations in its applicability.In this article we first present a multifault test generation and compaction strategy for algebraically factored multilevel circuits, synthesized from two-level representations. We give a basic sufficiency condition for multifault testability of such networks.We next focus on the relationship between hazard-free robust path-delay-fault testability and multifault testability. We show that the former implies the latter for arbitrary multilevel circuits. This allows the use of previously developed composition rules that maintain path-delay-fault testability for the synthesis of multifault testable circuits.We identify a class of multiplexor-based networks and prove an interesting property of such networks—if the networks are fully single stuck-at fault testable, or made fully single stuck-at fault testable, they are completely multifault testable. We give a multifault test generation and compaction algorithm for such networks.We provide experimental results which indicate that a compacted multifault test set derived using the above strategies can be significantly smaller than the test set derived using previously proposed procedures. These results also indicate the substantially wider applicability of our procedures, as compared to previous techniques.