Design of testable sequential circuits by repositioning flip-flops

This paper presents a technique to enhance the testability of sequential circuits by repositioning flip-flops. A novel retiming for testability technique is proposed that reduces cycle lengths in the dependency graph, converts sequential redundancies into combinational redundancies, and yields retimed circuits that usually require fewer scan flip-flops to break all cycles (except self-loops) as compared to the original circuit. Our technique is based on a new minimum cost flow formulation that simultaneously considers the interactions among all strongly connected components (SCCs) of the circuit graph to minimize the number of flip-flops in the SCCs. A circuit graph has a vertex for every gate, primary input and primary output. If gatea has a fanout to gateb, then the circuit graph has an arc from vertexa to vertexb. Experimental results on several large sequential circuits demonstrate the effectiveness of the proposed retiming for testability technique in reducing the number of partial scan flip-flops.     

A three-stage partial scan design method to ease ATPG

A new three-stage process for partial scan design is presented. The first two stages focus on cyclebreaking, and on limiting the maximum length of consecutive self-loops, as proposed by previous researchers. For the third stage, combinational blocks and their effects on sequential test generation are evaluated using a graphtheoretic representation designated the circuit flow graph. Costs calculated from the circuit flow graph representation are then used to select additional scan flip-flops. Sequential test generation results show that our selection of scan flip-flops is generally smaller than that reported by earlier researchers, and leads to a comparable fault coverage and smaller test generation time.     

Integration of partial scan and built-in self-test

Partial-Scan based Built-In Self-Test (PSBIST) is a versatile Design for Testability (DFT) scheme, which employs pseudo-random BIST at all levels of test to achieve fault coverages greater than 98% on average, and supports deterministic partial scan at the IC level to achieve nearly 100% fault coverage. PSBIST builds its BIST capability on top a partial scan structure by adding a test pattern generator, an output data compactor, and a PSBIST controller in a way similar to that of deriving a full scan BIST from a full scan structure. However, to make the scheme effective, there is a minimum requirement regarding which flip-flops in the circuit should be replaced by scan flip-flops and/or initialization flip-flops. In addition, test arents are usually added to boost the fault coverage to the range of 95 to 100 percent. These test points are selected based on a novel probabilistic testability measure, which can be computed extremely fast for a special class of circuits. This ciass of circuits is precisely the type of circuits that we obtain after replacing some of the flip-flops.withscan and/or initilization flip-flops. The testability measure is also used for a very useful quick estimation of the fault coverage right after the selection of sean flip-flops, even before the circuit is modified to incorporate PSBIST capability. While PSBIST provides all the benefits of BIST, it incurs lower area overhead and performance degradation than full scan. The area overhead is further reduced when the boundary scan cells are reconfigured for BIST usage.     

Layout Driven Selection and Chaining of Partial Scan Flip-Flops

In an era of sub-micron technology, routing is becoming a dominant factor in area, timing, and power consumption. In this paper, we study the problem of selection and chaining of scan flip-flops with the objective of achieving minimum routing area overhead. Most of previous work on partial scan has put emphasis on selecting as few scan flip-flops as possible to break all cycles in S-graph. However, the flip-flops that break more cycles are often the ones that have more fanins and fanouts. The area adjacent to these nodes is often crowded in layout. Such selections will cause layout congestion and increase the number of tracks to chain the scan flip-flops. To take layout information into consideration, we propose a matching-based algorithm to solve the problem. First, an initial placement will be performed before scan flip-flops are selected. Then, iteratively, a matching-based algorithm taking the current layout into account is proposed to select and chain the scan flip-flops. Experimental results show that, on the average, our algorithm can reduce 8.1% area overhead as compared with the previously proposed methods that do not utilize the layout information in flip-flop selection.     

Partial scan flip-flop selection by use of empirical testability

Partial serial scan as a design for testability technique permits automatic generation of high fault coverage tests for sequential circuits with less hardware overhead and less performance degradation than full serial scan. The objective of the partial scan flip-flop selection method proposed here is to obtain maximum fault coverage for the number of scan flip-flops selected. Empirical Testability Difference (ETD), a measure of potential improvement in the testability of the circuit, is used to successively select one or more flip-flops for addition or deletion of scan logic. ETD is calculated by using testability measures based on empirical evaluation of the circuit with the acutal automatic test pattern generation (ATPG) system. In addition, once such faults are known, ETD focuses on the hard-to-detect faults rather than all faults and uses heuristics to permit effective selection of multiple flip-flops without global optimization. Two ETD algorithms have been extensively tested by using FASTEST ATPG [1, 2] on fourteen of the ISCAS89 [3] sequential circuits. The results of these tests indicate that ETD yields, on average, 35% fewer uncovered detectable faults for the same number of scanned flip-flops or 27% fewer scanned flip-flops for comparable fault coverage relative to cycle-breaking methods.This work was performed while the author was with the University of Wisconsin-Madison.     

Optimal state assignment technique for partial scan designs

The state assignment of a finite state machine greatly affects the delay, area and testability of sequential circuits. To reduce the length and number of feedback cycles, a new state assignment technique based on m-block partitioning is introduced. Following the completion of the proposed state assignment and logic synthesis stage, partial scan design is performed to choose the minimal number of scan flip-flops. Experimental results show that a drastic improvement in testability can be realised while maintaining a low area and delay overhead     

Scan power-aware deterministic test scheme using a low-transition linear decompressor

Growing test data volume and excessive testing power are both serious challenges in the testing of very large-scale integrated circuits. This article presents a scan power-aware deterministic test method based on a new linear decompressor which is composed of a traditional linear decompressor, k-input AND gates and T flip-flops. This decompression architecture can generate the low-transition deterministic test set for a circuit under test. When applying the test patterns generated by the linear decompressor, only a few transitions occur in the scan chains, and hence the switching activity during testing decreases significantly. Entire test flow compatible with the design is also presented. Experimental results on several large International Symposium on Circuits and Systems’89 and International Test Conference’99 benchmark circuits demonstrate that the proposed methodology can reduce test power significantly while providing a high compression ratio with limited hardware overhead.     

Partial Reset Methodology and Experiments for Improving Random-Pattern Testability and BIST of Sequential Circuits

Partial reset has been shown to have significant impact on test generation for sequential circuits in a stored-pattern test application environment. In this paper, we explore the use of partial reset in fault-independent testing and built-in self-test (BIST) of non-scan sequential circuits. We select a subset of flip-flops in the circuit to be resetable to logic one or zero during the application of the test vectors. The resetting is performed with random frequency. The selection of the flip-flops and the reset polarity is based on fault-propagation analysis, which determines the impact of a selected flip-flop on fault propagation from the circuits structure. Application of partial reset as described above yields an average improvement of 15% in fault-coverage for sequential circuits resistant to random pattern testing. To further enhance testability, we also present a methodology for selecting observable test points based on propagation of switching activity. Overall, high fault coverages (about 97%) are obtained for many of the ISCAS89 benchmark circuits. Thus, partial reset BIST provides a low cost alternative for testing sequential circuits when scan design is unacceptable due to area and/or delay constraints. The routing overhead for implementing BIST is seen to be about 6%.     

Design of ternary flip-flops and sequential circuits based uponU hgate

According to the next-state equations of various ternary flip-flops (tri-flop), which are based upon ternary modular algebra, various ternary flip-flops are implemented by using universal-logic-modules,U _hs. Based on it ternary sequential circuits are implemented by using array of universal-logic-modules,U _hs. Supported by the National Natural Science Foundation of Zhejiang Province, China.     

Low-power sequential circuit design using T flip-flops

This paper presents a novel circuit design technique to reduce the power dissipation in sequential circuits by using T flip-flops. The unwanted triggering action of the master clock to flip-flops can be isolated during T = 0. An example design of a decimal counter demonstrates the large power saving and improved performance of the resulting circuit.     

Testability-based partial scan analysis

In this paper, we present a new method for selecting flip-flops for partial scan. Our method ranks all flip-flops in a circuit based on a sensitivity analysis which estimates the relative improvement in the testability of the circuit as a result of scanning a flip-flop. The testability is an estimate of the fault coverage expected for the circuit and is computed with respect to a given set of target faults. Several cost functions are used to compute testability, taking both structural and logical aspects of the circuit into account. Our results show a good correlation between the computed testability and the actual fault coverage. We give a testability-based estimate on the number of scan flip-flops needed to reach a high fault coverage.     

Deterministic built-in test pattern generation for high-performancecircuits using twisted-ring counters

We present a new approach for built-in test pattern generation based on the reseeding of twisted-ring counters (TRCs). The proposed technique embeds a precomputed deterministic test set for the circuit under test (CUT) in a short test sequence produced by a TRC. The TRC is designed using existing circuit flip-flops and does not add to hardware overhead beyond what is required for basic scan design. The test control logic is simple, uniform for all circuits, and can be shared among multiple CUTs. Furthermore, the proposed method requires no mapping logic between the test generator circuit and the CUT; hence it imposes no additional performance penalty. Experimental results for the ISCAS benchmark circuits show that it is indeed possible to embed the entire precomputed test set in a TRC sequence using only a small number of seeds     

Improving path delay testability of sequential circuits

We analyze the causes of low path delay fault coverage in synchronous sequential circuits and propose a method to improve testability. The three main reasons for low path delay fault coverage are found to be: (A) combinationally false (nonactivatable) paths; (B) sequentially nonactivatable paths; and (C) unobservable fault effects. Accordingly, we classify undetected faults in Groups A, B, and C. Combinationally false paths ran be made testable by modifying the circuit or resynthesizing the combinational logic as discussed by other researchers. A majority of the untestable faults are, however found in Group B, where a signal transition cannot be functionally propagated through a combinational path. A test requires two successive states necessary to create a signal transition and propagate it through the target path embedded in the sequential circuit. We study a partial scan technique in which flip-flops are scanned to break cycles and shun that a substantial increase in the coverage of path delay faults is possible     

基于电路状态信息和冲突分析的部分扫描设计

该文提出了一种割断关键回路的方法来选择扫描触发器。该方法在选择一定数量的扫描触发器后,采用逻辑模拟更新电路的状态信息,这样可以得到更为精确的可测试性信息。当电路中的关键回路割断后,转向消除冲突的处理,而不是降低时序深度。该方法致力于消除冲突,并使用了一种基于冲突分析的测度conflict。足够的实验结果表明该方法是非常有效的。     

A novel clocking technique for VLSI circuit testability

Scan-testable digital designs have a special `scan' operating mode to set and read the states of flip-flops in the circuit. All previous scan-testable design implementations required at least one additional input pin to specify either scan or normal operating mode, and this mode specification signal had to be routed to every flip-flop. A new clocking structure is described which eliminates these requirements for certain designs with static flip-flops that are controlled by two independent signals (master clock and slave clock). This is possible because, in normal circuit operation, the master and slave clocks are never simultaneously active. The new clocking structure uses the `all clocks active' condition to specify the scan mode. Implementation of the concept is discussed in detail for two-clock circuits. Single-clock circuits can be modified to use this scheme, and the results for this class of design are also presented.     

三值动态和静态广义时序机理论

该文在三值电路三要素理论的基础上提出了三值动态和静态广义时序机理论。首先找出三值状态图和电路方程间的关系,该关系既适用于静态电路,又适用于动态电路。对静态电路文中推导出各型三值触发器完整特性方程,它描述了触发器全时刻的行为,用以代替常规特性方程,使三值同步和异步时序电路统一。对动态电路该文用电容代替触发器存储三值信息,实现三值动态时序电路(特别是三值同步动态时序电路,属于非触发器式的时序电路)。因动态电路和静态电路主要差别是负载行为,故此可以在三值电路三要素理论和广义时序机理论下统一三值动态和静态,同步和异步时序电路。     

A partitioning algorithm for technoiogy-mapped designs onsingle-chip emulation systems

Reconfigurable single-chip emulation systems were proposed as an alternative to multichip emulation systems. Because they cannot be emulated on a single chip at once, large designs are sliced into partitions that are downloaded and executed sequentially on the same reconfigurable emulation chip. In this paper, we address the problem of partitioning a design on a reconfigurable single-chip emulator under resource constraints. First, we extract an acyclic flow graph of the design to be emulated. Then, we model the problem as an integer linear programming problem (IP) based on the acyclic flow graph of the design where the structure of the assignment and precedence constraints produce a tight formulation. To partition a design, our algorithm uses two distinct steps with different objectives. In the first step, we minimize the number of cycles needed to schedule every look-up table (LUT) in the circuit. Then flip-flops (FFs) are inserted into the appropriate cycles of the schedule in the second step. Experiments are conducted on small- and medium-size circuits from the MCNC Partitioning93 benchmark suite. The obtained results show that our algorithm produces optimal partitioning schedules     

Metastability tests of flip-flops in programmable digital circuits

This paper describes the methods and experimental techniques for determination of the metastability behavior of the flip-flops used in the programmable digital circuits. A dual model of the metastability distinguishes two transitions at the flip-flop output (L/H and H/L) which have different impact on the Mean Time Between Failures (MTBF) of the flip-flop. A new circuit of the late transition detector (LTD) allows for determination of the pairs of the metastability parameters, the window W and the time constant τ, for both transitions. The test results are presented for four types of programmable digital circuits fabricated commercially in CMOS technology. In the all tests, the H/L transition clearly dominates with respect to MTBF (as a worse one). The presented test methods can also be used for evaluation of flip-flops in nonprogrammable digital circuits.     

Double-edge-triggered D-flip-flops for high-speed CMOS circuits

Two circuits are proposed for double edge-triggered D flip-flops (DETDFFs). A DETDFF responds to both edges of the clock pulse. As compared with positive or negative edge-triggered flip-flops, a DETDFF has advantages in terms of power dissipation and speed. Delay figures for these circuits are measured by simulation. It is shown that these circuits are faster and have lower transistor counts than previously reported circuits. It is shown that these flip-flops can be used at 320-400-MHz clock frequency in a 2-μm technology