Scan testing requires long test application time and a large hardware overhead. To avoid these disadvantages, design-for-testability methods at register transfer level based on non-scan testing are important. We assume that controllers and data paths in register transfer level circuits are isolated from each other at testing. We focus on test generation for controllers which are represented by finite state machines. In this paper, we propose a time expansion model with initial state constraints for controllers and its test generation method. Our proposed test generation method also uses the information of finite state machines. Experimental results show that our proposed method achieved higher fault coverage by 8.9% on average for all controllers compared with a commercial tool whose test generation algorithms use a time expansion model.

We present a unified test technique that targets faults in links, routers, and cores of a network-on-chip design based on test sessions. We call an entire procedure, that delivers test packets to the subset of routers/cores, a test session. Test delivery for router/core testing is formulated as two fault-tolerant multicast algorithms. Test packet delivery for routers is implemented as a fault-tolerant unicast-based multicast scheme via the fault-free links and routers that were identified in the previous test sessions to avoid packet corruption. A new fault-tolerant routing algorithm is also proposed for the unicast-based multicast core test delivery in the whole network. Identical cores share the same test set, and they are tested within the same test session. Simulation results highlight the effectiveness of the proposed method in reducing test time.

A binding method for hierarchical testability has been proposed to increase the number of testable operational units in hierarchical testing using behavioral level circuits [2]. The method aims to synthesize many operational units which can be tested by generated test sequences using hierarchical test generation. In this paper, we propose a scheduling method for hierarchical testability to increase the efficiency of the binding method [2]. Experimental results show that the combination of our proposed scheduling method and the binding method [2] improves fault coverage by 11% on average in hierarchical testing.

We present a unified test technique that targets all the components of a network-on-chip design. The proposed technique targets faults in links, routers, and cores. Link faults are first located using built-in self-test hardware inserted in the routers. Test packets for routers are delivered to the routers via the fault-free links and routers identified in the previous steps. A test packet can be corrupted by faulty links or routers, therefore, it is delivered across only previously identified fault-free routers/links. Test packet delivery for routers is implemented as a fault-tolerant unicast-based multicast scheme within the tested part of the network-on-chip. After all faulty routers are identified, a new fault-tolerant unicast-based multicast routing technique is proposed to deliver test packets for the cores. Identical cores share the same test set, and they are tested within the same test session. Simulation results highlight the effectiveness of the proposed method in reducing test time.

A 3D stacked network-on-chip (NOC) promises the integration of a large number of cores in a many-core system-on-chip (SOC). The NOC can be used to test the embedded cores in such SOCs, whereby the added cost of dedicated test-access hardware can be avoided. However, a potential problem associated with 3D NOC-based test access is the emergence of hotspots due to stacking and the high toggle rates associated with structural test patterns used for manufacturing test. High temperatures and hotspots can lead to the failure of good parts, resulting in yield loss. We describe a unicast-based multicast approach and a thermal-driven test scheduling method to avoid hotspots, whereby the full NOC bandwidth is used to deliver test packets. Test delivery is carried out using a new unicast-based multicast scheme. Experimental results highlight the effectiveness of the proposed method in reducing test time under thermal constraints.

In recent years, various high-level test synthesis methods for data paths have been proposed for the improvement in design productivity and test cost reduction. Most of the approaches assume that controllers and data paths are isolated from each other, and hence the hardware overhead becomes large. On the other hand, the approach without separation of a controller and a data path usually decreases the testability. To resolve this problem, an approach that augments a controller by adding extra control functions to make a data path easily testable was proposed. However, the approach cannot always succeed in generating test sequences with high fault coverage if a general ATPG tool is used without knowing any information of augmented control functions. In this paper, we introduce "easily testable functional time expansion models for data paths", and propose a test generation method for data paths using easily testable functional time expansion models and controller augmentation such that easily testable functional time expansion models are controllable. Experimental results show the effectiveness of the proposed method for high level synthesis benchmark circuits.

A 3D stacked network-on-chip (NOC) promises the integration of a large number of cores in a many-core system-on-chip (SOC). The NOC can be used to test the embedded cores in such SOCs, whereby the added cost of dedicated test-access hardware can be avoided. However, a potential problem associated with a 3D NOC-based test access is the emergence of hotspots due to stacking and the high toggle rates associated with structural test patterns used for manufacturing test. High temperatures and hotspots can lead to the failure of good parts, resulting in yield loss. We describe a thermal-driven test scheduling method to avoid hotspots, whereby the full NOC bandwidth is used to deliver test packets. Test delivery is carried out using a new unicast-based multicast scheme. Experimental results highlight the effectiveness of the proposed method in reducing test time under thermal constraints.

This paper presents a novel failure prediction technique that is applicable for system-on-chips (SoCs). Highly reliable systems such as automobiles, aircrafts, or medical equipments would not allow any interruptive erroneous responses during system operations, which might result in catastrophes. Therefore, we propose a failure prediction technique that can be applied during an idle time when a system is not working, such as power-on/-off time. To achieve high reliability in the field, the proposed technique should take into consideration various types of aging mechanisms and the testing environment of voltage and temperature which is uncontrollable in the field. Therefore, we propose: 1) an accurate delay measurement technique considering the variation due to voltage and temperature and 2) an adaptive test scheduling that gives more test chances to more probable degrading parts. Experimental results show the required memory space and area cost for implementing the proposed technique.

There is a need for an efficient design-for-testability to satisfy both testability and security of digital circuits. In our previous work, we reported a secure and testable scan design approach by using extended shift registers that are functionally equivalent but not structurally equivalent to shift registers, and showed a security level by clarifying the cardinality of those classes of shift register equivalents (SR equivalents). However, SR equivalents are not always secure for scan-based side-channel attacks. In this paper, we consider a scan-based side-channel attack called differential-behavior attack and propose several classes of SR-equivalent scan circuits using dummy flip-flops in order to protect the scan-based differential-behavior attack. To show the security level of those extended scan circuits, we introduce differential-behavior equivalent relation, and clarify the number of SR-equivalent extended scan circuits, the number of differential-behavior equivalent classes and the cardinality of those equivalent classes.

We propose a new test generation method for F-scan delay fault testing that uses standard full scan delay fault automatic test pattern generation (ATPG). This method shows that it is possible to generate test patterns fast for F-scannable register-transfer level (RTL) circuits by using currently well-developed and high-performance commercial ATPG tools for gate-level scan circuits.

The paper proposes a new hierarchical untestable stuck-at fault identification method for non-scan sequential circuits containing feedback loops. The method is based on deriving, minimizing and solving test path activation constraints for modules embedded into Register-Transfer Level (RTL) designs. First, an RTL test pattern generator is applied in order to extract the set of all possible test path activation constraints for a module under test. Then, the constraints are minimized and a constraint-driven deterministic test pattern generator is run providing hierarchical test generation and untestability proof in sequential circuits. We show by experiments that the tool is capable of quickly proving a large number of untestable faults obtaining high fault efficiency. As a side effect, our study shows that traditional bottom-up test generation based on symbolic test environment generation at RTL is too optimistic due to the fact that propagation constraints are ignored.

For accurate failure prediction, it is important to eliminate the environmental delay variations from the measure delays for capturing the actual delay shift caused by aging. This paper presents a novel test pattern optimization method to reduces spatial and temporal temperature variations during delay test.

Faster-than-at-speed testing is an effective approach to screen small delay defects (SDDs) and increase test quality and in-field reliability. This paper presents a novel framework of faster-than-at-speed test to minimize the slack of the sensitized path for each fault. The basic strategy is to use multiple faster-than-at-speed test timings with endpoint masking for each pattern. By performing a detailed analysis of the sensitized path delay for active faults and active endpoints in each pattern, we can minimize the slack for the detectable faults while preventing a large increase in pattern count. We also present methods to maximize the sensitized path delay and further reduce the pattern count under a constraint on the allowable slack size, instead of minimizing the slack. Experimental results for ITC'99 benchmark circuits show the effectiveness of the proposed methods in terms of slack size and sensitized path delay for detectable faults, statistical delay quality level (SDQL) and pattern count.

In this paper, we first introduce extended de Bruijn graphs to design extended shift registers that are functionally equivalent but not structurally equivalent to shift registers. Using the extended shift registers, we present a new secure and testable scan design approach that aims to satisfy both testability and security of digital circuits. The approach is only to replace the original scan registers to modified scan registers called extended scan registers. This method requires very little area overhead and no performance overhead. New concepts of scan security and scan testability are also introduced.

A globally-asynchronous and locally-synchronous (GALS) system has been known as a realistic hardware design solution for many difficulties such as global clock network that arise due to the continuous scaling of semiconductor technology. Although a full scan design method for synchronous circuits is applied to asynchronous circuits to achieve the same testability of their combinational parts, the overhead is extremely high. To reduce the overhead, several full scan design methods have been proposed but they cannot guarantee complete test. In this paper, we propose a bipartite full scan design as a new DFT method for asynchronous circuit where we guarantee complete test for both combinational and sequential parts of circuits with area and performance overhead comparable to the previous best method in terms of overhead.

This paper presents a seed ordering and selection method in LFSR-reseeding-based BIST for high quality delay test. The proposed method selects seeds based on the gain in the sum of the longest path lengths sensitized by seeds, which is highly correlated with statistical delay quality level (SDQL). We also evaluate the contributions of pseudo-random patterns in several mixed-mode BIST approaches and the impact of base seed set on the final quality of selected seeds. Experimental results show that the proposed method intelligently selects seeds and obtains significant reduction in seed count under SDQL constraint within a reasonable time.

With the exponential increase of transistor counts, scan design encounters several problems such as large test data volume, long test application time and high test power. In this paper, we propose a new method to reduce test data volume, test application time and also average and peak power during test. The proposed method is based on a scan chain disabling technique where only one internal sub scan chain is active at a time. Though our method makes a sacrifice of test generation time, instead, we can achieve reduction of test data volume, test application time and test power together. Experimental results show the effectiveness of the proposed method.

We reported a secure scan design approach using extended shift registers that are functionally equivalent but not structurally equivalent to shift registers. The security level of the secure scan architecture based on those shift register equivalents is determined by the probability that an attacker can identify the configuration of the shift register equivalent used in the circuit, and hence the attack probability approximates to the reciprocal of the cardinality of the class of shift register equivalents. In this paper, we clarify the cardinality of each class of shift register equivalents from several linear structured circuits and the cardinality of the whole class of shift register equivalents. We also consider the enumeration problem of shift register equivalents and the synthesis problem of desired shift register equivalents. A program called SREEP (Shift Register Equivalents Enumeration and Synthesis Program) is presented to solve those problems.

This paper proposes a new synthesis method for propagating information of paths from register transfer level (RTL) to gate level. The method enables false path identification at RTL without not only enforcing strong constraints on logic synthesis but also loss of the information about false paths identified. Experiments show that the proposed method can reduce hardware and timing overhead and improve propagability of false path information through logic synthesis compared with the previous methods.

Timing-aware ATPGs are being developed to detect small delay faults for high defect coverage for current nanometer VLSI design. However, it results in a large test set compared with test generation targeting traditional fault models. This paper proposes a method to get a limited size of test set with high delay test quality based on statistical delay quality level (SDQL).

Scan circuit is widely practiced DFT technology. The scan testing procedure consist of state initialization, test application, response capture and observation process. During the state initialization process the scan vectors are shifted into the scan cells and simultaneously the responses captured in last cycle are shifted out. During this shift operation the transitions that arise in the scan cells are propagated to the combinational circuit, which inturn create many more toggling activities in the combinational block and hence increases the dynamic power consumption. The dynamic power consumed during scan shift operation is much more higher than that of normal mode operation. Due to change in design characteristic the dynamic power dissipated during scan operation becomes an important issue. The average power and peak power are the standard metric to measure dynamic power. During scan test both average power and peak power are required to be within the specified power budget for safe testing of chip. Average power causes excessive heat dissipation where as peak power causes IR drop and cross talk problem. Particularly, the excessive peak power during test-cycle of at-speed testing is vulnerable. The excessive peak power causes high rate of current in the power and ground rails which decreases the supply voltage and causes ground bounce, this phenomenon is known as IR-drop. The larger IR-drop means the worse speed performance of circuit. This degradation in performance grows if circuit is operated at high frequency which is the case during at-speed testing. This degradation in performance leads to incorrect capture of responses and this results in to undesired yield loss. Hence, to avoid yield loss the the peak power minimization is necessary especially in case of narrow test-cycle. More over the minimization of peak power is also advantageous for parallel testing of multiple core to reduce test time. In this work we have focused on the problem of peak power consumption during test-cycle for at-speed testing. The methodology proposed in this work is based on scan cells reordering. Many direction has been explored to reduce peak power during test-cycle. One of the methodology on scan reordering is proposed by Bonhomme et al. The methodology is formulated as a global optimization problem and solved using simulated annealing approach. Although the simulated annealing can provides near optimal solution if it is allowed to run for sufficient number of iteration the graph theoretic formulation will wider the solution space for scan reordering methodology. With this motivation we are proposing a graph theoretic formulation for scan reordering methodology to minimize peak power during test-cycle. The overall approach consists of graph theoretic problem formulation and an algorithm to solve it. From given scan related informations viz. scan cells, possible scan path, and power consumption a complete vector-weighted graph is constructed. The vector-weight is a weight of an edge which keeps the information of peak power consumed by each test vector. On this graph a TSP (Travelling Sales Person) problem is formulated. The cost function in this formulation is peak power. The problem formulated is NP-complete. As the problem is NP-complete we have proposed a greedy based heuristic to solve it. The proposed heuristic consists of two parts. Part 1 to find a Hamiltonian cycle which consume less peak power from the constructed complete graph and Part 2 to find a Hamiltonian path having lower peak power from Hamiltonian cycle. The Part 1 of algorithm runs in polynomial time and the Part 2 runs in linear time. The memory space required to execute these algorithms is also linear. The experiment conducted on ITC99 and ISCAS89 benchmarks show that the proposed methodology is able to reduce appreciable percentage (around 55%) of peak power compared to. Overall, this paper has proposed a novel way of formulating a graph theoretic problem for scan reordering to minimize test-cycle peak power. The scan reordering methodology may incur nominal area overhead in terms of routing and may alter the delay fault coverage for at-speed skewed-load testing. In this work we have not taken these parameters into account. However, the proposed methodology can be extended to consider these parameters. One limitation of the scan reordering methodology is it is pattern dependent. If some additional pattern has to be added on top of the existing patterns the methodology will not be able to reduce peak power effectively. This issue needs further examination.

Scan circuit testing generally causes excessive switching activity compared to normal circuit operation. This excessive switching activity causes high peak and average power consumption. Higher peak power causes, supply voltage droop and excessive heat dissipation. This paper proposes a scan cell reordering methodology to minimize the peak power consumption during scan shift operation. The proposed methodology first formulate the problem as graph theoretic problem then solve it by a linear time heuristic. The experimental results show that the methodology is able to reduce up to 48% of peak power in compared to the solution provided by industrial tool.

This paper presents a novel failure prediction testing technique that is applicable for system-on-chips (SoCs). Highly reliable systems such as automobiles, aircraft or medical equipments would not allow any interruptive erroneous responses during a system operation, which might result in catastrophe. Therefore, we propose a failure prediction delay testing technique that is applied during the time when the system is not working, such as power-on/-off times. To achieve high reliability in the field, the proposed technique should take into consideration various types of aging mechanisms. Since the testing environment of voltage and temperature is uncontrollable in the field, an accurate delay measurement considering the variation due to voltage and temperature should be developed. Moreover, we propose an adaptive test scheduling that gives more test chances to more possible degrading parts for improving detecting efficiency.

In this paper, we present an approach to constrained automatic test pattern generation (ATPG) for functional circuits at register-transfer level (RTL) with the help of a design-for-testability (DFT) technique called F-scan. The DFT method optimally utilizes existing functional elements and paths for test, thus it effectively reduces the hardware overhead due to test. This is done by arranging all registers in the circuit into F-scan-paths and augmenting necessary circuitry at RTL. After DFT, we create the constraint test generation model of the circuit based on the test environment obtained from the information of F-scan-paths. With this approach, only the applicable test vectors to the F-scan-paths can be generated and test application time is kept at the minimum. The comparison of F-scan with the performance of gate-level full scan design is shown through the experimental results.

Functional test sequences play an important role in manufacturing test for targeting defects that are not detected by structural test. In practice, functional tests are often derived from existing design-verification test sequences and they suffer from low defect coverage. Therefore, there is a need to increase their effectiveness using design-for-testability (DFT) techniques. We present a non-scan DFT technique at the register-transfer (RT) level that tackles the above problem in three steps. It can be used to increase the defect coverage for scan-based designs by making functional test sequences more effective in native (non-scan) mode. The proposed method selects a small set of control points, and through an efficient branch-and-bound strategy, determines an effective set of truth assignments to these control points (also called test modes). The original functional test is expanded by applying the same functional test sequence once with each selected test mode. Finally, a small set of state elements are chosen as observation points from the transitive fanout cone of the control points based on the number of recorded transitions. The proposed DFT method is evaluated in terms of the unmodeled defect coverage, and we introduce a new surrogate metric, called multi-segment long path sensitization, for the purpose of evaluation. Experimental results for the ITC'99 benchmark circuits, the Open RISC 1200 SoC benchmark, and the Scheduler module of the Illinois Verilog Model (IVM) show that the proposed non-scan DFT technique offers significant potential for ramping up the defect coverage of existing functional test sequences.

It is well known that the test mode exceeds the functional mode in power consumption, which is not uniformly distributed within the circuit. The non-uniformity in spatial power distribution may cause localized heating and temperature differences within the circuit. Since gate delay depends on junction temperature, thermal differences within the circuit may lead to erroneous pass or fail in at-speed testing. This paper first discusses the importance of spatial thermal uniformity for high quality and accurate at-speed testing. The paper also presents an X-filling technique that minimizes the spatial temperature variation within the circuit while preserving the overall circuit power consumption at low level. Experimental results show the effectiveness of the proposed method compared to the existing X-filling techniques.

In this paper, we propose a method for identifying false paths based on functional unsensitizability of path delay faults. By using RTL structural information, a number of gate level paths are bound into an RTL path and the bundle of them can be identified in a reasonable amount of time. The identified false paths are useful for over-testing reduction caused by DFT techniques, such as scan design, and also area and performance optimization of circuits during logic synthesis. Experimental results show that our proposed method can identify false paths in a few seconds for several benchmarks.

We present a thermal-aware test-access mechanism (TAM) design and test scheduling method for system-on-chip (SOC) integrated circuits. The proposed method uses cycle-accurate power profiles for thermal simulation; it also relies on test-set partitioning, test interleaving, and bandwidth matching. We use a computationally tractable thermal-cost model to ensure that temperature constraints are satisfied and the test application time is minimized. Simulation results for the ITC'02 SOC Test Benchmarks show that, compared to prior thermal-aware test-scheduling techniques, the proposed method leads to shorter test times under tight temperature constraints.

This paper proposes a secure scan design method which protects the circuits containing secret information such as cryptographic circuits from scan-based side channel attacks.The proposed method prevents the leakage of secret information by partial scan design based on a balanced structure. We also guarantee the testability of both the design under test and DFT circuitry, and therefore, realize both security and testability. Experiments for RSA circuit shows the effectiveness of the proposed method.

A register-transfer level (RTL) circuit meeting a design specification may contain some functionally unused paths.If functionally unused paths can be easily identified at RTL,the information can be utilized to eliminate the corresponding gate-level paths from the target of testing.Testing such gate-level paths is considered to be futile. In this paper, we present a method for identifying such functionally unused paths, called RTL don't care paths, using RTL information, and a method of synthesis for transforming the identified paths into untestable paths which will never do a mischief.As a result, our approaches contribute to identification of many untestable paths and reduction of over-testing.

Conventional random access scan (RAS) designs, although economic in test power dissipation, test application time and test data volume, are expensive in area and routing overhead. In this paper, we present a localized RAS architecture (LRAS) to address this issue. A novel scan cell structure, which has fewer transistors than the multiplexer-type scan cell, is proposed to eliminate the global test enable signal and to localize the row enable and the column enable signals. Experimental results on ISCAS'89 and ITC'99 benchmark circuits demonstrate that LRAS has 54% less area overhead than multiplexer-type scan chain based designs, while significantly outperforms the state-of-the-art RAS scheme in routing overhead.

Since scan testing is not based on the function of the circuit, but rather its structure, scan testing is considered to be a form of over testing or under testing. It is important to test VLSIs using the given function. Since the functional specifications are described explicitly in the FSMs, high test quality is expected by performing logical fault testing and timing fault testing. This paper proposes a test generation method to detect specified fault models completely and to increase defect coverage as much as possible under test length constraint. We give experimental results for MCNC'91 benchmark circuits to evaluate bridging fault coverage, transition fault coverage, and statistical delay quality level and show the effectiveness of the proposed test generation method compared with a stuck-at fault-dependent test generation method.

Similar to test pattern generation, the problem of identifying untestable faults in sequential synchronous circuits remains unsolved. The previously published works in untestability identification operate at the logic-level and, thus, they do not scale with the increasing complexity of modern designs. Current paper proposes applying model-checking for detecting untestable stuck-at faults at the register-transfer level. In particular, we present a method of generating PSL language assertions for proving untestable register stuck-on faults. Experiments show that the faults identified by the method form in fact a large subset of all the untested stuck-at faults. An additional application of the method is in high-level test synthesis, where testability of sequential designs can be improved simultaneously with minimization of the circuit area. Furthermore, identification of untestable gate-level faults from RT-level can contribute to avoiding over testing and to reducing yield loss.

As LSI manufacturing technology improves and the time-to-market for products becomes stricter, more and more circuit designs have multiple clock domains due to concerns such as design re-use, power reduction and temperature control. It is not uncommon for these designs to have multi-cycle paths which are untestable. The rapid identification of these untestable paths reduces test generation time as well as over-testing due to design for testability (DFT). For current and future designs, this has already become impractical at the gate-level. This paper presents a method to identify nonrobust untestable multi-cycle paths at the register transfer level (RTL) and the details in a case study of a benchmark circuit.

This paper presents a wrapper and TAM cooptimization method for reuse of SoC functional interconnects to minimize test time under area constraint. The proposed method consists of (1) an ILP formulation for wrapper and transparent TAM co- optimization, and (2) a simulated annealing based heuristic approach to reduce the computational cost of the proposed ILP model. Experimental results show the effectiveness of the proposed methods compared to the previous transparency-based TAM approaches and the conventional dedicated test bus approaches.

This paper presents a nonscan design-for-testability (DFT) method for register-transfer-level (RTL) circuits. We first introduce thenotationto analyze the test generation complexity, as well as two classes of sequential circuits, namely: 1) thecombinationallytestableclass and 2) theacyclicallytestableclass. Then, we introduce a new class oflinear-depthtime-boundedcircuits as one of the acyclically testable classes. The linear-depth time-bounded testability guarantees that the number of time frames required for any testable fault is bounded by a linear function of the number of flip-flops in the circuit during the test generation process. As one of the linear-depth time-bounded classes, we introduce a new class of RTL circuits, called thecycle-unrollableRTL circuits, which is shown to be linear depth time bounded. We propose a DFT method to make RTL circuits cycle unrollable and a test generation method for cycle-unrollable RTL circuits. Experimental results show that we can drastically reduce hardware overhead and test application time compared to the full-scan method and the method proposed by Ohtake Moreover, our proposed method can achieve 100% fault efficiency for gate-level single stuck-at faults in practical test generation time and allow at-speed testing.

We present a new scan-based built-in self-test (BIST) technique, which is based on weighted scan-enable signals and a reconfigurable scan-forest architecture. A testability measure is proposed to guide test pattern generation and produce patterns with few care bits. This approach can effectively reduce the amount of test data that needs to be stored on-chip. The proposed BIST method relies on the pseudorandom and deterministic phases. The scan-forest architecture is configured as a single scan tree for deterministic test vector application in the second phase. It is found that a linear feedback shift register, with size equal to the maximum number of the care bits in the deterministic patterns for the random-resistant faults, is sufficient to encode deterministic vectors for the benchmark circuits. Experimental results for benchmark circuits demonstrate the effectiveness of the proposed method for single stuck-at faults. In addition, experimental results show that the patterns applied to the circuit under test provide more n-detection than those applied by a traditional scan-chain architecture with a single test session.

An integrated test scheduling methodology for multiprocessor system-on-chips (SOC) utilizing the functional buses for test data delivery is described. The proposed methodology handles both flat bus single processor SOC and hierarchical bus multiprocessor SOC. It is based on a resource graph manipulation and a packet-based packet set scheduling methodology. The resource graph is decomposed into a set of test configuration graphs, which are then used to determine the optimum test configurations and test delivery schedule under a given power constraint. In order to validate the effectiveness of the proposed methodology, a number of experiments are run on several modified benchmark circuits. The results clearly underscore the advantages of the proposed methodology.

This paper proposes a novel power-aware multi-frequency wrapper architecture design to achieve at-speed testability. The trade-offs between power dissipation, scan time and bandwidth are well handled by gating off certain virtual cores at a time while parallelizing the remaining. A shelf packing based optimization algorithm is proposed to design and optimize the wrapper architecture while minimizing the test time under power and bandwidth constraints.

Since scan testing is not based on the function of the circuit, but rather its structure, this method is considered to be a form of over testing or under testing. It is important to test VLSIs using the given function. Since the functional specifications are described explicitly in the FSMs, high test quality is expected by performing logical testing and timing testing. This paper proposes two test generation methods, a fault-independent test generation method and a fault-dependent test generation method, for state-observable FSMs. We give experimental results for MCNC'91 benchmark circuits. The quality and cost of the logic testing and timing testing for proposed test generation methods was evaluated.

In this paper, a new approach to NoC test scheduling based on bandwidth-sharing is presented. The test scheduling is performed under the objective of co-optimizing the wrapper area overhead and the resulting test application time using two complementary NoC wrappers. Experimental results showed that the area overhead can be optimized (to an extent) without compromising the test application time. Compared to other NoC scheduling approaches based on dedicated paths, our bandwidth sharing approach can reduce the test application time by up to 75.4%.

A new scan architecture, called enhanced scan forest, is proposed to detect path delay faults and reduce test stimulus data volume, test response data volume, and test application time. The enhanced scan forest architecture groups scan flip- flops together, where all scan flip-flops in the same group are assigned the same value for all test vectors. All scan flip- flops in the same group share the same hold latch, and the enhanced scan forest architecture makes the circuit work in the same way as a conventional enhanced scan design. The area overhead of the proposed enhanced scan forest is greatly reduced compared to that for enhanced scan design. A low- area-overhead zero-aliasing test response compactor is designed for path delay faults. Experimental results for the IS- CAS benchmark circuits are presented to demonstrate the effectiveness of the proposed method.

This paper presents a stage-based test scheduling for memory cores with BISR scheme under power constraint. We introduce a model to compute the expected test time for a given test schedule for memory cores with BISR scheme based on pass probabilities, and propose a test scheduling algorithm to minimize the expected test time. Experimental results show a significant expected test time reduction compared to the core-based test scheduling method which minimizes the test time.

While design-for-testability (DFT) techniques are generally used in order to reduce test generation complexity, they induce over-testing problems. In general, DFT techniques make a large number of untestable paths testable. However delay on the path that becomes testable does not affect circuit performance because the path was originally untestable. Therefore we consider testing such path to be over-testing. In this work, we reduce the over-testing by identifying false paths using register transfer level information. Our method identifies a subset of false paths within a reasonable time. Experimental results for some RTL benchmark circuits show the effectiveness of our false path identification method.

Smaller manufacturing processes have resulted in higher power densities which put greater emphasis on packaging and temperature control during test. For system-on-chips, peak power-based scheduling algorithms are used to optimize tests while satisfying power budgets. However, imposing power constraints does not necessarily mean that overheating is avoided due to the non-uniform power distribution across the chip. This paper presents a TAM/Wrapper co-design methodology for system-on-chips that ensures thermal safety while still optimizing the test schedule. The method combines a simplified thermal-cost model with a traditional bin-packing algorithm to minimize test time while satisfying temperature constraints. Experiments show that even minimal increases in test time can yield considerable decrease in test temperature as well as the possibility of further lowering temperatures beyond those achieved using traditional power-based test scheduling.

With the debut of a new class of multi-port ATE (e.g., Agilent 93000 series), there is a pressing need for test planning methods to fully adapting SoC test framework design to the new concurrent test capabilities and fulfil emerging demands of high-speed testing. In this paper, we propose a new test planning strategy that addresses multi-frequency SoC testing by dynamically reconfiguring ATE ports. The system integrators on-the-fly group pins into virtual ports while ATE ports simultaneously drive the testing of a set of cores at multiple independent clock domains. An effective and efficient system optimization technique is developed to manage test resources and improve test efficiency for modern complex SoC designs.

This paper presents a non-scan design-for-testability method for register transfer level circuits. We first introduce a new testability of RTL circuits called partially strong testability. The partially strong testability guarantees that the number of time frames required for any testable fault is bounded by a linear function of the number of registers in the RTL circuit during test generation process. We also propose a DFT method to make RTL circuits partially strongly testable. Experimental results show that we can reduce hardware overhead and test application time drastically compared to the previous methods. Moreover, the proposed method can achieve 100% fault efficiency in practical test generation time and allow at-speed testing.

This paper presents a reconfigurable union wrapper that can wrap multiple cores into a single wrapper design. Moreover, we present a test scheduling algorithm to minimize a test application time using the proposed reconfigurable union wrapper. The proposed heuristic algorithm can achieve short test application time with low computational cost compared to the conventional approaches where every core has its own wrapper. Experimental results for the ITC'02 SOC benchmarks show the effectiveness of our approach

In this paper, two wrapper designs are proposed for core- based test application based on Networks-on-Chip (NoC) reuse. It will be shown that the previously proposed NoC wrapper does not efficiently utilize the NoC bandwidth, which may result in poor test schedules. Our wrappers (Type 1 and Type 2) complement each other to overcome this inefficiency while minimizing the overhead. The Type 2 wrapper uses larger area overhead to increase bandwidth efficiency, while the Type 1 takes advantage of some special configurations which may not require a complex and high-cost wrapper. Two wrapper optimization algorithms are applied to both wrapper designs under channel bandwidth and test time constraints, resulting in very little or no increase in the test application time compared to conventional TAM approaches.

This paper proposes an approach to non-robust and functionally sensitizable path delay test generation through stuck- at test generation. In this approach, to generate two-pattern tests for path delay faults in a combinational circuit, checker circuitry is constructed which is composed of logic gates corresponding to the mandatory assignments for detecting the faults. This checker circuitry allows us to use any existing combinational stuck-at test generation tool. Since today’s stuck-at test generation tools reach a mature level, the proposed approach can efficiently solve the path delay test generation problem for combinational circuits. Experimental results show that the approach can speed up path delay test generation and can improve fault efficiency. This paper also discusses how a scan circuit and the issues of over-testing and test power are handled in the proposed test generation framework.

This paper presents a solution to the multi-frequency heterogeneous SoC test integration and reuse, which is considered the major hurdle of SoC manufacturing capability, and thus is the key component of SoC test automation. A hybrid system level test framework is designed and optimized to tackle heterogeneous test environment with the combination of BIST and the external test. Several interdependent design items including test access mechanism design, bandwidth matching, multi-frequency interface configuration, and test scheduling under tight power and pin count limitation, are well studies and incorporated into the test framework. The trade-off between test time, test power and bandwidth is well balanced to achieve the minimum test cost in terms of test time and test interface. The simulation study shows the promising results of the proposed floor-ceiling packing approach.

Test generation and fault simulation of path delay faults are very time-consuming. A new fault simulation method of fully enhanced scan designed circuits is proposed for path delay faults based on single stuck-at tests without circuit transformation. The proposed method identifies robustly and non-robustly testable paths first, for which a selected path circuit (SPC) is constructed. The SPC circuit contains no internal fanouts. Fault simulation of non-robustly testable paths is reduced to 3-valued logic simulation of the SPC circuit. Fault simulation is completed on the SPC circuit by only tracing the active part of SPC circuit. An effective fault dropping technique is also adopted based on the selective tracing scheme. The proposed fault simulation scheme is extended to that of robustly testable path delay faults. Experimental results confirm that the proposed fault simulator is exact. It is shown according to experimental results that the proposed fault simulator gets exact fault simulation results in very short time. Sufficient experimental results are presented to compare with previous methods on CPU time and accuracy.

We present a graph model and an ILP model for optimal TAM design for transparency-based SoC testing. The proposed method is an extension of (Chakrabarty, 2003) so that not only the system-level cost but also the core-level cost can be simultaneously taken into consideration during the optimization process. We also relax the constraints by considering test dataflows and extend it to be able to handle the case where cores cannot be made transparent due to IP protection. The proposed ILP model can represent various problems including the same problem as (Chakrabarty, 2003) and produce better results. Experimental results show the effectiveness and flexibility of the proposed method compared to (Chakrabarty, 2003).

This paper presents a novel design method for power-aware test wrappers targeting embedded cores with multiple clock domains. We show that effective partitioning of clock domains combined with bandwidth conversion and gated-clocks would yield shorter test times due to greater flexibility when determining optimal test schedules especially under tight power constraints

The conventional test-per-scan built-in self-test (BIST) scheme needs a number of shift cycles followed by one capture cycle. Fault effects received by the scan flip-flops are shifted out while shifting in the next test vector, like scan testing. Unlike deterministic testing, it is unnecessary to apply a complete test vector to the scan chains. A new scan-based BIST scheme is proposed by properly controlling the scan enable signals of the scan chains. Different weighted values are assigned to the scan enable signals of scan flip-flops in separate scan chains. Capture cycles can be inserted at any clock cycle if necessary. A new testability estimation procedure according to the proposed testing scheme is presented. A greedy procedure is proposed to select a weight for each scan chain. Experimental results show that the proposed method can improve test effectiveness of scan-based BIST greatly and most circuits can obtain complete fault coverage or very close to complete fault coverage.

A new scan architecture called reconfigured scan forest is proposed for cost-effective scan testing. Multiple scan flip-flops can be grouped based on structural analysis that avoids new untestable faults due to new reconvergent fanouts. The proposed new scan architecture allows only a few scan flip-flops to be connected to the XOR trees. The size of the XOR trees can be greatly reduced compared with the original scan forest; therefore, area overhead and routing complexity can be greatly reduced. It is shown that test application cost, test data volume, and test power with the proposed scan forest architecture can be greatly reduced compared with the conventional full scan design with a single scan chain and several recent scan testing methods

Numerous solutions have been proposed to reduce test data volume and test application time during manufacturing testing of digital devices. However, time to market challenge also requires a very efficient debug phase. Error identification in the test responses can become impractically slow in the debug phase due to large debug data, slow tester speed, and limited memory of the tester. In this paper, we investigate the problems and solutions related to using a relatively slow and limited memory tester to observe the at-speed behavior of fast circuits. Our method can identify all errors in at-speed scan BIST environment without any aliasing and using only little extra overhead by way of a multiplexer and masking circuit for diagnosis. Our solution takes into account the relatively slower speed of the tester and the reload time of the expected data to the tester memory due to limited tester memory while reducing the test/debug cost. Experimental results show that the test application time by our method can be reduced by a factor of 10 with very little hardware overhead to achieve such advantage.

With the increasing demand for SoCs to include rich functionality, SoCs are being designed with hundreds of small memories with different sizes and frequencies. If memory BIST logics were individually added to these various memories, the area overhead would be very high. To reduce the overhead, memory BIST logic must therefore be shared. This paper proposes a memory-grouping method for memory BIST logic sharing. A memory-grouping problem is formulated and an algorithm to solve the problem is proposed. Experimental results showed that the proposed method reduced the area of the memory BIST wrapper by up to 40.55%. The results also showed that the ability to select from two types of connection methods produced a greater reduction in area than using a single connection method.

The paper presents a new scan-based BIST technique, which is based on weighted scan enable signals and a scan forest architecture. A new testability measure is proposed to guide test pattern generation and produce patterns with fewer specified bits. This approach can effectively reduce the amount test data that needs to be stored on-chip. The proposed BIST method relies on a pseudorandom phase and a deterministic phase. The scan forest architecture is configured as a single scan tree for deterministic test vector application in the second phase. It is found that an LFSR with size equal to the maximum number of the specified bits in the deterministic patterns for the random-resistant faults is sufficient to encode deterministic vectors for the benchmark circuits. Experimental results for benchmark circuits demonstrate the effectiveness of the proposed method

Numerous solutions have been proposed to reduce test data volume and test application time during manufacturing testing of digital devices. However, time to market challenge also requires a very efficient debug phase. Error identification in the test responses can become impractically slow in the debug phase due to large debug data, slow tester speed and limited memory of the tester. In this paper, the authors investigate how a relatively slow and limited memory tester can observe the at-speed behavior of fast circuits. Our method can identify all errors in at-speed scan BIST environment without any aliasing and negligible extra hardware while taking into account the relatively slower speed of the tester and the re-load time of the expected data to the tester memory due to limited tester memory. Experimental results show that the test application time by our method can be reduced by a factor of 10 with very little hardware overhead to achieve such advantage

In this paper, the authors propose a design for testability method for test programs of software-based self-test using test program templates. Software-based self-test using templates has a problem of error masking where some faults detected in a test generation for a module are not detected by the test program synthesized from the test. The proposed method achieves 100% template level fault efficiency in a sense that the proposed method completely resolves the problem of error masking. Moreover, the proposed method adds only observation points to the original design, and it enables at-speed testing and does not induce delay overhead

VLSI design has moved from bottom-up design approach to top-down design methodology with the aid of advanced computer-aided design (CAD) technology. This paper introduces a new scan design technique as a design-for-test (DFT) method for sequential circuits by exploiting the information of thru functions available at high-level description of the circuit. This DFT method reduces the number of flip-flops to be converted into scan flip-flops because some existing thru functions allow the flip-flops to be controllable from primary inputs or observable at primary outputs or both. Moreover, the DFT method can be applied to both structural RT-level circuits and gate-level circuits. The paper also presents a test generation procedure for the augmented sequential circuits using a combinational ATPG tool. The experimental results show the comparison of our DFT method with conventional scan techniques in terms of hardware overhead, test generation time, fault coverage, fault efficiency and test application time

We present an approach to prevent over testing in scan-based delay test. The test data is transformed with respect to functional constraints while simultaneously keeping as many positions as possible unspecified in order to facilitate test compression. The method is independent of the employed delay fault model, ATPG algorithm and test compression technique, and it is easy to integrate into an existing flow. Experimental results emphasize the severity of over testing in scan-based delay test. Influence of different functional constraints on the amount of the required test data and the compression efficiency is investigated. To the best of our knowledge, this is the first systematic study on the relationship between over testing prevention and test compression

This paper presents a wrapper and test access mechanism design for multi-clock domain SoCs that consists of cores with different clock frequencies during test. We also propose a test scheduling algorithm for multi-clock domain SoCs to minimize test time under power constraint. In the proposed method, we use virtual TAMto solve the frequency gaps between cores and the ATE, and also to reduce power consumption of a core during test while maintaining the test time of the core. Experimental results show the effectiveness of our method not only for multi-clock domain SoCs, but also for single-clock domain SoCs with power constraints.

In this paper, we are proposing a core-based test methodology that utilizes the functional bus for test stimuli and response transportation. An efficient algorithm for the generation of a complete test schedule that efficiently utilizes the functional bus under a power constraint is described. The test schedule is composed of a set of test vector delivery sequences in small chunks, denoted as packets. The utilization of small packet sizes optimizes the functional bus utilization. The experimental results show that the methodology is highly effective compared to previous approaches that do not use the functional bus. The strong results of the proposed approach are particularly highlighted when small bus widths are considered, an important consideration in current SOC designs where increasingly larger bus widths pose routing and reliability challenges.

This paper introduces a new class of sequential circuits called acyclically testable sequential circuits which is wider than the class of acyclic sequential circuits but whose test generation complexity is equivalent to that of the acyclic sequential circuits. We also present a test generation procedure for acyclically testable sequential circuits and elaborate a design-for-test (DFT) method to augment an arbitrary sequential circuit into an acyclically testable sequential circuit. Since the class of acyclically testable sequential circuits is larger than the class of acyclic sequential circuits, the DFT method results in lower area overhead than the partial scan method and still achieves complete fault efficiency. Besides, we show through experiment that the proposed method contributes to lower test application time compared to partial scan method. Moreover, the proposed method allows at-speed testing while the partial scan method does not.

A new rest generation method of fully scanned or combinational circuits is proposed for complete coverage of path delay faults based on single stuck-at tests. The proposed method adds the target path into the original circuit, where all off inputs of the path are connected with corresponding nodes in the original circuit. Test generation of the path delay fault is reduced to that of the single stuck-at fault at the fanout branch, where the additional path connects with its source node in the original circuit. A disjoint dynamic test compaction scheme is proposed to reduce the size of the test set in the process of test generation. A conjoint test compaction scheme is proposed based on fanout counts of the paths. The proposed method presents a very compact test set for complete coverage of robustly and non-robustly testable path delay faults.

This paper proposes a new test generation model for broadside transition testing of partial scan circuits. In the proposed scheme, given a partial scan circuit whose kernel circuit is acyclic, the kernel circuit is transformed into some combinational circuits which are called broadside test generation models. These circuits are constructed by using a time-expansion model of the kernel circuit. All the broadside transition tests are generated by performing constrained stuck-at test generation on the transformed circuits. This means that, without developing a special test generation tool, existing combinational stuck-at test generation tools can be used to generate broadside transition tests for partial scan circuits. Experimental results show that the proposed scheme can reduce area overhead compared with the fully enhanced scan and full scan methods, and can generate broadside transition tests in reasonable test generation time

The object of this paper is to analyze the potential benefits of conducting a BIST pretest before launching a functional test of ICs during post manufacturing screening. In (Nakamura et al., 2005) the impact of BIST on the chip defect level after test has been addressed. It was assumed in (Nakamura et al., 2005) that no measures are taken to assure that the BIST circuitry is fault-free before launching the functional test. In this paper, we assume that a BIST pretest is first conducted in order to rid of all chips that fail it. Only chips whose BIST circuitry has passed the pretest are kept, while the rest are discarded. The BIST pretest, however, is assumed to have only a limited coverage against its own faults. This paper studies the product quality improvements as induced by the BIST pretest, and provides some insight as to when this pretest maybe worthwhile performing. As the study shows, in many cases the potential benefits outweigh any potential risks

The problem with increasing test application time for testing core-based system-on-chip (SOC) designs is addressed with test architecture design and test scheduling. The scan-chains at each core are configured into a set of wrapper-chains, which by a core wrapper are connected to the test access mechanism (TAM), and the tests are scheduled in such a way that the test time is minimized. In this paper, we make use of reconfigurable core wrappers that, in contrast to standard wrappers, can dynamically change (reconfigure) the number of wrapper-chains during test application. We show that by using reconfigurable wrappers the test scheduling problem is equivalent to independent job scheduling on identical machines, and we make use of an existing preemptive scheduling algorithm that produces an optimal solution in linear time (O(n); n is the number of tests). We also show that the problem can be solved without preemption, and we extend the algorithm to handle: 1) test conflicts due to interconnection tests and 2) cases when the test time of a core limits an optimal usage of the TAM. The overhead in logic is given by the number of configurations, and we show that the upper-bound is three configurations per core. We compare the proposed approach with the existing technique and show, in comparison, that our technique is 2% less from lower bound.

Aggressive processor design methodology using high-speed clock and deep submicrometer technology is necessitating the use of at-speed delay fault testing. Although nearly all modern processors use pipelined architecture, no method has been proposed in literature to model these for the purpose of test generation. This paper proposes a graph theoretic model of pipelined processors and develops a systematic approach to path delay fault testing of such processor cores using the processor instruction set. The proposed methodology generates test vectors under the extracted architectural constraints. These test vectors can be applied in functional mode of operation, hence, self-test becomes possible. Self-test in a functional mode can also be used for online periodic testing. Our approach uses a graph model for architectural constraint extraction and path classification. Test vectors are generated using constrained automatic test pattern generation (ATPG) under the extracted constraints. Finally, a test program consisting of an instruction sequence is generated for the application of generated test vectors. We applied our method to two example processors, namely a 16-bit 5-stage VPRO pipelined processor and a 32-bit pipelined DLX processor, to demonstrate the effectiveness of our methodology

Testing of VLSI circuits is challenged by the increasing volume of test data that adds constraints on tester memory and impacts test application time substantially. Space compactors are commonly used to reduce the test volume by one or two orders of magnitude. However, such level of compaction reduces the quality of the diagnostic of faults because it is difficult to identify the locations of errors in the compacted response. In this paper, we introduce a design of space compactors that can be used in pass/fail mode as well as in diagnostic mode with enhanced performance by trading off compaction ratio for diagnostic ability. We analyze the properties of the compactors and evaluate their performance through simulations

Hierarchical test generation is an efficient method of test generation for VLSI circuits. In this paper, we study a test plan generation algorithm for hierarchical test based on strong testability. We propose a heuristic algorithm for finding a control forest requiring a small number of hold functions by improving an existing test plan generation algorithm based on strong testability. Experimental results show that the proposed algorithm is effective in reducing additional hold functions, i.e., reducing hardware overhead and delay penalty of datapaths.

This paper presents a non-scan design-for-testability (DFT) method that guarantees complete fault efficiency (FE) for register transfer level (RTL) data paths. We first define the partially strong testability as a characteristic of data paths. Then we propose a DFT method to make a data path partially strongly testable and a test generation method for partially strong testable data paths based on the time expansion model (TEM). The proposed DFT method can reduce hardware overhead drastically compared with the previous method based on strong testability. Moreover, the proposed DFT method can generate test patterns with complete FE in practical time and allow at-speed test.

This paper presents efficient method to extract constraints from a test program template and synthesize a test program using constraint circuits. A test program template is an instruction sequence with unspecified operands, and represents paths for justification of test patterns and observation of test responses for a module under test (MUT). The constraint circuit represents a relation between operand values and inputs/output of the MUT, therefore it enables to obtain operand values using a standard automatic test pattern generator. Experimental results show that the proposed method generates accurate and compact constraint circuits, and we obtain high fault efficiency.

Unlike deterministic testing, it is unnecessary for scan-based BIST to apply a complete test vector into the circuit via the scan chains. A new scan-based BIST scheme is proposed by properly controlling the test signals of the scan chains. Different weighted random signals are assigned to the test signals of different scan chains. In the proposed test scheme, capture cycles can be inserted at any clock cycle. Testability calculation procedure according to the proposed testing scheme is presented. Techniques for selecting different weights on the test signals of the scan chains are also proposed. Experimental results show that the proposed method can improve the test effectiveness of scan-based BIST greatly, and most circuits can reach complete fault coverage or very close to complete fault coverage.

A new scan architecture called reconfigured scan forest is proposed for cost-effective scan testing. Multiple scan flip-flops can be grouped based on structural analysis that avoids new unstable faults due to new reconvergent fanouts. The proposed new scan architecture makes all scan flip-flop groups have similar size because of flexibility of the scan flip-flop grouping scheme, where many scan flip-flops become internal scan flip-flops. The size of the exclusive-or trees can be reduced greatly compared with the original scan forest. Therefore, area overhead and routing complexity are reduced greatly. It is shown that test application cost and test power with the proposed scan forest architecture can be reduced to even less than 1% of the conventional full scan design with a single scan chain

This paper presents a design-for-testability method that transforms a given SoC into consecutively testable one under power constraint. When a power constraint and a user defined importance ratio between area overhead and test time are given, the proposed method can create an optimal TAM design and a test schedule for the importance ratio under the power constraint with low computational cost. Experimental results show that the proposed method can achieve area and time co-optimization under power constraint. Moreover, the proposed method can obtain better results for SoCs without power constraint compared to test bus method and our previous method based on consecutive testability of SoCs.

This paper introduces a new concept of hierarchical testability called Single-Port-Change (SPC) two-pattern testability. We propose a non-scan design-for-testability (DFT) method which makes each path that needs to be tested in a data path SPC two-pattern testable. An SPC two-pattern test guarantees robust (resp. non-robust) test if the path is robust (resp. non-robust) testable. Since it is easy to find justification paths for SPC two-pattern tests at register-transfer level, the proposed DFT method can reduce hardware overhead compared to that of our previous DFT method for arbitrary two-pattern tests. Furthermore, we propose a method to reduce test generation effort by removing a subset of sequentially untestable paths from targets of test generation. Experimental results show that the proposed method can reduce hardware overhead without losing the quality of test.

This paper presents a transition test generation method for acyclic sequential circuits. In this method, to generate test sequences for transition faults in a given acyclic sequential circuit, constrained combinational stuck-at test generation is performed on its double time-expansion model that is composed of two copies of a time-expansion model of the given circuit. This method is complete, i.e., this method can generate test sequences for all the testable transition faults and can identify all the untestable transition faults in a given acyclic sequential circuit. Experimental results show that our method can achieve higher fault efficiency with drastically shorter test generation time than that achieved by a conventional method.

This paper presents a methodology for testing a superscalar processor using functional mode of operation for the performance oriented delay faults. The functional mode test issues for superscalar are discussed. A graph based model is developed and used to develop for the generation of test programs.

Occurrence of unknown values in scan chains in response to test vectors is a common phenomenon. This paper presents a method for designing matrices for linear test output compactors by using rows of multiple weights. Compared to previously proposed compactors, the method reduces the masking caused by unknowns by an order of magnitude provided that the unknowns are non-uniformally distributed among the scan chains. Also, using multiple rather than single weight compactors increases the compaction ratio and reduces the hardware overhead. The effectiveness of multiple weight compactors is demonstrated through analysis, simulations and experiments with test response from an industrial design.

Test effectiveness of a test-per-scan built-in self-test (BIST) scheme is highly dependent on the length and number of scan chains. Fewer cycles are used to capture test responses when the length of the scan chains increases and the total number of clock cycles is fixed. Another important feature of the test-per-scan BIST scheme is that test responses of the circuit at the inputs of the scan flip-flops are not observable during the shift cycles. A new scan architecture is proposed to make a scan-based circuit more observable. The scan chain is partitioned into multiple segments. Multiple capture cycles are inserted to receive test responses during the shift cycles compared to the test-per-scan test scheme. Unlike other BIST schemes using multiple capture cycles after the shift cycles, our method inserts multiple capture cycles inside the shift cycles, but not after the shift cycles. Unlike the previous method that drives multiple scan segments by a single scan-in signal, the proposed method uses a new architecture to control all scan segments by different signals. Sufficient experimental results are presented to demonstrate the effectiveness of the method.

The paper uses the concept of time expansion model (Innoue et al., 2000) to find the test generation for acyclic sequential circuits. It identifies a class of sequential circuits called as max-testable sequential circuits, where test generation can be obtained using a combinational test generator with the capability of detecting multiple faults on a kernel of combinational circuit. Any acyclic sequential circuit without hold registers belongs to this class. For the sequential circuits having hold registers, a subset of such circuits is found to be belonged to max-testable class. The paper also suggests an algorithm to find such class of circuits.

This paper presents a method of template generation for instruction-based self-test of processor cores. A test program template is an instruction sequence with unspecified operands, and represents paths for justification of test patterns and propagation of test responses for a module under test (MUT). In order to justify value of MUT inputs, we introduce a concept of adjacent registers of the MUT that makes it possible to consider input spaces of the MUT determined by signals from other modules as well as signals directly from registers. We efficiently generate possible templates considering dependence of instructions each of which invokes one or more data transfers between registers. The method also generates multiple templates in effective order to detect faults, which may cover different input spaces, and therefore, different detectable fault sets.

In this paper, we introduce a new test generation complexity notation called /spl tau//sup k/ notation, which consists of /spl tau//sup k/-equivalent and /spl tau//sup k/-bounded, in order to clarify the classification of sequential circuits based on combinational test generation complexity. We reconsider the test generation complexity for the existing classes of acyclic sequential circuits. Several new classes of sequential circuits that cover some cyclic sequential circuits have been identified as being /spl tau/-equivalent and /spl tau/-bounded.

This paper proposes two power-constrained test synthesis schemes and scheduling algorithms, under non-scan BIST, for RTL data paths. The first scheme uses boundary non-scan BIST, and can achieve a low hardware overhead. The second scheme uses generic non-scan BIST, and can offer some tradeoffs between hardware overhead, test application time and power dissipation. A designer can easily select an appropriate design parameter based on the desired tradeoff. Experimental results confirm good performance and practicality of our approaches.

International audience

This paper proposes a non-scan design scheme to enhance delay fault testability of controllers. In this scheme, we utilize a given state transition graph (STG) to test delay faults in its synthesized controller. The original behavior of the STG is used during test application. For faults that cannot be detected by using the original behavior, we design an extra logic, called an invalid test state and transition generator, to make those faults detectable. Our scheme allows achieving short test application time and at-speed testing. We show the effectiveness of our method by experiments.

A test solution for a complex system requires the design of a test access mechanism (TAM), which is used for the test data transportation, and a test schedule of the test data transportation on the designed TAM. An extensive TAM will lead to lower test-application time at the expense of higher routing costs, compared to a simple TAM with low routing cost but long testing time. It is also possible to reduce the testing time of a testable unit by loading the test vectors in parallel, thus increasing the parallelization of a test. However, such a test-time reduction often leads to higher power consumption, which must be kept under control since exceeding the power budget could damage the system under test. Furthermore, the execution of a test requires resources and concurrent execution of tests may not be possible due to resource or other conflicts. In this paper, we propose an integrated technique for test scheduling, test parallelization, and TAM design, where the test application time and the TAM routing are minimized, while considering test conflicts and power constraints. The main features of our technique are the efficiency in terms of computation time and the flexibility to model the system's test behavior, as well as the support for the testing of interconnections, unwrapped cores and user-defined logic. We have implemented our approach and made several experiments on benchmarks as well as industrial designs in order to demonstrate that our approach produces high-quality solution at low computational cost.

This paper proposes a test generation method using several partly compacted test plan tables for RTL data paths. Combinational modules in data paths are tested using several partly compacted test plan tables. Each partly compacted test plan table is generated from each grouped test plan set and is used to test combinational modules corresponding to the grouped test plans. The values of control signals in a partly compacted test plan table are supplied from a test controller. This paper also proposes the architecture of a test controller which can be synthesized in a reasonable amount of time, and proposes a test plan grouping method to shorten the test length for data paths under a test controller area constraint. Experimental results for benchmarks show that the test lengths are shortened by 4 to 36 % with 9 to 8 % additional test controller area compared with the test generation method using test plans.

This paper proposes a test syntheses method for datapaths. The proposed method goes on design-for-testability while generating control sequences for justification and propagation at register-transfer level. Since the method fully utilizes functions of controllers as well as datapaths, it achieves small area overhead.

This paper presents a new structure, called discontinuous reconvergence structure (DR-structure), of sequential circuits with easy testability for delay faults. We show that the delay fault test generation problem for sequential circuits with DR-structure can be reduced to that for their time-expansion models, which are combinational circuits. Based on the reducibility, we propose a test generation method for delay faults in sequential circuits with DR-structure. This method can be applied to several delay fault models. By some experiments, we show that the proposed method is effective in the hardware overhead, the test generation time and the fault efficiency.

In this paper, we show that the scheduling of tests on the test access mechanism (TAM) is equivalent to independent job scheduling on identical machines and we make use of all existing preemptive scheduling algorithm to produce an optimal solution in linear time. We extend the algorithm to handle (1) test conflicts elite to interconnection tests and (2) cases when a test limits all optimal usage of the TAM by using reconfigurable core test wrappers. Our extensions preserve the production of all optimal solution in respect to test time and minimizes the number of wrapper configurations as well as the TAM usage at each core. which implicitly minimizes the TAM routing. Experiments with our implementation shows its efficiency in comparison with previous approaches.

This paper proposes an SoC test architecture generation framework. It contains a database which stores the test cost information on several DFTs for every core, and DFT selection part which performs DFT selection for test cost minimization using this database in the early phase of the design flow. Moreover, the DFT selection problem is formulated and the algorithm which solves it is proposed Experimental results showed that bottlenecks in test application time when using the single DFT method for all cores in a SoC are reduced by performing DFT selection from several DFTs. As a result, the whole test application time is drastically shortened.

This paper presents a software-based self-testing methodology for delay fault testing. Delay faults affect the circuit functionality only when it can be activated in functional mode. A systematic approach or the generation of test vectors, which are applicable in functional mode, is presented. A graph theoretic model (represented by IE-Graph) is developed in order to model the datapath. A finite state machine model is used for the controller. These models are used for constraint extraction so that the generated test can be applied in functional mode.

The test effectiveness of a test-per-scan BIST scheme is highly dependent on the length and the number of the scan chains. Fewer cycles are adopted to capture test responses when the length of the scan chains increases. On the other hand, the number of test inputs should be increased when the number of the scan chains increases. Another important feature of the test-per-scan BIST scheme is that test responses of the circuit at the inputs of the scan flip-flops are unobservable during the shift cycles. A new scan architecture is proposed to make a scan-based circuit more observable. The scan chain is partitioned into multiple segments, according to which multiple capture cycles can be inserted to receive test responses during the shift cycles based on the test-per-scan test scheme. This scheme directly makes the circuit more observable and testable. Unlike other BIST schemes using multiple capture cycles after the shift cycles, our method inserts multiple capture cycles inside the shift cycles, but not after the shift cycles. Sufficient experimental results are presented to demonstrate the effectiveness of the method.

A non-scan design for testability method for RTL circuits based on conflict analysis is proposed. Conflict analysis is presented based on a new 5-valued system to estimate testability of data paths. New test point structures for RTL circuit design for testability are introduced. Nonscan design for testability is proposed based on conflict resolution. Unlike most of the previous methods, our method considers testability of data paths and the controller simultaneously. Different classes of test points can be inserted into data paths and the controller. Intensive techniques are presented to connect extra inputs of test points with PI ports, which avoids generating reconvergent fanouts that cause new conflicts.

Test access mechanism and test scheduling are integral parts of SoC test. This paper presents an area overhead and test time co-optimization method for SoCs based on consecutive testability. The proposed method creates TAM and a test schedule by using integer linear programming, and augments a given SoC into consecutively testable one where area overhead and test time are co-optimized. Consecutive testability of SoCs guarantees that arbitrary test/response sequences including timing information can be propagated to/from all embedded cores and all interconnects without information loss. Therefore, the method can handle any test sequence that requires consecutive application of test patterns at speed of system clock such as a test sequence for timing faults. Moreover, the proposed method achieves low area overhead because existing interconnects are used as a part of TAM. Experimental results show advantages of the proposed method compared to test bus architecture which is a well known TAM architecture.

We propose a test resource partitioning and optimization technique for core-based designs. Our technique includes test set selection and test resource floor-planning with the aim of minimizing the total test application time and the routing of the added TAM (test access mechanism) wires. A feature of our approach is that it pinpoints bottlenecks that are likely to limit the test solution, which is important in the iterative test solution development process. We demonstrate the usefulness of the technique through a comparison with a test scheduling and TAM design tool.

This paper presents a design-for-consecutive-transparency method that makes a soft core (RTL description) consecutively transparent using integer linear programming. Consecutive transparency of a core guarantees consecutive propagation of arbitrary test/response sequences from the core inputs to the core outputs with some latency. Therefore, it is possible to apply/observe arbitrary test/response sequences to/from an embedded core consecutively at the speed of the system clock by using interconnects and consecutively transparent cores in an SoC. Experimental results show that the proposed method introduces a lower area overhead compared to the bypass method that adds direct paths from PIs to POs with multiplexers.

A testability measure called conflict, based on conflict analysis in the process of sequential circuit test generation is introduced to guide nonscan design for testability. The testability measure indicates the number of potential conflicts to occur or the number of clock cycles required to detect a fault. A new testability structure is proposed to insert control points by switching the extra inputs to primary inputs, using whichever extra inputs of all control points can be controlled by independent signals. The proposed design for testability approach is economical in delay, area, and pin overheads. The nonscan design for testability method based on the conflict measure can reduce many potential backtracks and make many hard-to-detect faults easy-to-detect; therefore, it can enhance actual testability of the circuit greatly. Extensive experimental results are presented to demonstrate the effectiveness of the method.

This paper introduces a design for testability, (DFT) scheme for delay faults of a controller-data path circuit. The scheme makes use of both scan and non-scan techniques. Firstly, the data path is transformed into a hierarchically two-pattern testable (HTPT) data path based on a non-scan approach. Then an enhanced scan (ES) chain is inserted on the control lines and the status lines. The ES chain is extended via the state register of the controller. If necessary, the data path is further modified. Then a test controller is designed and integrated into the circuit. Our approach is mostly based on a path delay fault model. However, the multiplexer (MUX) select lines and register load lines are tested as register transfer level (RTL) segments. For a given circuit, the area overhead incurred by our scheme decreases proportionally with increase in bit-width of the data path of the circuit. The proposed scheme supports hierarchical test generation and can achieve fault coverage similar to that of the ES approach.

In this paper, we present a technique for reducing the test length of counter-based pseudo-exhaustive built-in self-testing (BIST) using a width compression method and a divide-and-conquer strategy. More formally, the target faults are divided into K groups such that a binary counter can generate a test set for each group. By selecting the size of the binary counter, this technique allows a trade-off between test application time and area overhead. The experimental results for the ISCAS'85 and ISCAS'89 benchmark circuits demonstrate the efficiency of the proposed technique. In all cases, this low-overhead BIST technique achieves complete fault coverage of the stuck-at faults in reasonable test application time.

Acyclic partial scan design is an efficient DFT method. This paper presents a scheduling method for reducing the number of scan registers for an acyclic structure. In order to estimate the number of scan registers during scheduling, we propose provisional binding of operational units, and show a force-directed scheduling algorithm with the provisional binding. Experimental results show that the number of scan registers in the resulting RTL datapaths can be reduced by our method combined with the binding algorithm for acyclic partial scan.

We propose a technique integrating test scheduling, scan chain partitioning and test access mechanism (TAM) design to minimize the test time and the TAM routing cost while considering test conflicts and power constraints. The main features of our technique are (1) the flexibility in modelling the systems test behaviour and (2) the support for interconnection test of unwrapped cores and user-defined logic. Experiments using our implementation on several benchmarks and industrial designs demonstrate that it produces high quality solution at low computational cost.

A two stage non-scan design for testability method is proposed. The first stage selects test points based on an earlier testability measure conflict. A new testability measure conflict+ based on conflict analysis of hard-faults in the process of test generation is introduced, which emulates most general features of sequential ATPG. A new design for testability algorithm is proposed to select test points by using conflict+. Test points are selected in the second stage based on the hard faults after the initial ATPG run of the design for testability circuit in the preliminary stage. Effective approximation schemes are adopted to get reasonable estimation of the testability measure. Several effective techniques are adopted to accelerate the process of the proposed design for testability algorithm.

We introduce a class of sequential circuits with internally switched balanced structure which allows test generation with combinational test generation complexity. The proposed class includes any other known classes with this feature. This paper also considers faults in hold registers and switches regarded as macros, while any related work does not consider faults in such macros. Experimental results show the effectiveness of using combinational test generation for the circuits with internally switched balanced structure.

This paper shows that path delay fault test generation problem for sequential circuits with balanced structure can be reduced to segment delay fault test generation problem for their combinationally transformed circuits. We also propose a test generation method and a partially enhanced scan design method for path delay fault.

In this paper, an efficient test pattern generation (TPG) algorithm for combinational circuits based on the Boolean satisfiability method (SAT) is presented. The authors propose a new data structure for the complete implication graph that increases the precision of implication process. Next, they examine approaches like a single-cone processing, single path-oriented propagation, and backward justification and show that they are efficient to improve robustness of TPG algorithms. Finally, the authors propose efficient techniques and heuristics for these approaches. The resultant automatic test pattern generation system, called SPIRIT (Satisfiability Problem Implementation for Redundancy Identification and Test generation), combines the flexibility of the SAT-based TPG algorithms with the efficiency of the structural TPG algorithms. Experimental results demonstrate the robustness of the proposed TPG algorithm. Without fault simulation, SPIRIT is able to achieve 100% fault efficiency for a large set of benchmark circuits in a reasonable amount of time.

The pin overhead problem of nonscan design for testability (DFT) and built-in self-test design has been an unsolved problem for a long time. A new algorithm is proposed to connect extra pins of control test points with primary inputs. An economical test point structure is introduced, in which only one gate delay is added to the corresponding functional paths inserted into a control test point. Unlike almost all of the previous nonscan DFT methods which do not handle pin overhead well, this method allows at most three extra pins. Techniques are presented to connect an extra input of a control test point to a primary input in order to avoid conflicts produced by the newly generated reconvergent fanouts. Similar techniques are proposed to connect more than one control input with the same PI. Sufficient experimental results are presented to demonstrate the effectiveness of the method.

This paper proposes a non-scan design-for-test-ability method for register-transfer level circuits where a circuit consists of a controller and a data path. It achieves complete fault efficiency with low hardware overhead and at-speed testing.

Introduces the concept of hierarchical testability, of data paths for delay faults. A definition of a hierarchically two-pattern testable (HTPT) data path is developed. Also, a design for testability (DFT) method is presented to augment a data path to an HTPT one. The DFT method incorporates a graph-based analysis of an HTPT data path and makes use of some graph algorithms. The proposed method can provide similar advantages to the enhanced scan approach at the cost of much lower hardware overhead.

This paper presents a new BIST (Built-In Self-Test) method for register transfer level data paths based on both hierarchical testing and a "test-per-clock" scheme. In the proposed method, test pattern generators and response analyzers are placed on primary inputs and primary outputs, and test patterns and test responses are transferred along paths in the data paths. This paper proposes a new testability for BIST, concurrent single-control testability, and presents a new BIST method based on the testability. The concurrent single-control testability is an extension of a previous single-control testability and has advantage that test application time becomes shorter because multiple combinational modules can be tested at the same time (i.e., concurrent testing). Our experimental results show that the proposed method reduces test application time without increasing so much hardware overhead compared with the previous method.

This paper introduces a new concept of testability of core-based systems-on-a-chip (SoCs) called consecutive testability and proposes a design-for-testability (DFT) method for making a given SoC consecutively testable based on an integer programming problem. For a consecutively testable SoC, testing can be performed as follows. Test patterns of a core are propagated to the core inputs from the SoC inputs consecutively at the speed of the system clock. Similarly the test responses are propagated to the SoC outputs from the core outputs consecutively at the speed of the system clock. The propagation of test patterns and responses is achieved by using the consecutive transparency properties of surrounding cores and interconnects between cores. All interconnects can be tested in a similar fashion. Therefore, the method can test not only logic faults such as stuck-at faults, but also timing faults such as delay faults that require consecutive application of test patterns at system clock speed.

In this paper, we present a new data structure for a complete implication graph and two techniques for low complexity static learning. We show that using static indirect &Lgr-implications and super gate extraction some hard-to-detect static and dynamic indirect implications are easily derived during static and dynamic learning as well as branch and bound search. Experimental results demonstrated the effectiveness of the proposed data structure and learning techniques.

In this paper we present a robust test generation algorithm for combinational circuits based on the Boolean satisfiability method called SPIRIT. We elaborate some well-known techniques as well as presenting new techniques that improve the performance and robustness of test generation algorithms. As a result, SPIRIT achieves 100% fault efficiency for a full scan version of the ITC'99 benchmark circuits in a reasonable amount of time.

Abstract — This paper presents a non-scan design-fortestability (DFT) method for VLSIs designed at registertransfer level (RTL) to achieve complete fault efficiency. In RTL design, a VLSI generally consists of a controller and a data path. The controller and the data path are connected with internal signals: control signals and status signals. The proposed method consists of the following two steps. First, we apply our DFT methods [1] and [2, 3] to the controller and the data path, respectively. Then, to support at-speed testing, we append a test plan generator which generates a sequence of test control vectors for the modified data path. Our experimental results show that the proposed method can reduce significantly both of test generation time and test application time compared with the full-scan design, though the hardware overhead of our method is slightly larger than that of the full-scan design. I.

In this paper an efficient test pattern generation (TPG) algorithm for combinational circuits based on the Boolean satisfiability method (SAT) is presented. We examine some not so popular approaches as a single cone processing, single path oriented propagation and backward justification. We give a new definition for SAT-based test generation and present duality of learning phenomenon. The resultant ATPG system, called SPIRIT, combines the flexibility of SAT-based TPG algorithms with the efficiency of structural TPG algorithms. Experimental results demonstrate the efficiency and robustness of the proposed TPG algorithm. Without fault simulation, SPIRIT is able to generate complete test sets for the ISCAS'85 benchmark circuits and full scan version of the ISCAS'89 benchmark circuits within 3 minutes on a 450 MHz Pentium-III PC.

We show that the test generation problem for all single stuck-at-faults in sequential circuits with internally balanced structures is reduced into the test generation problem for single stuck-at-faults in combinational circuits. In our previous work, we introduced internally balanced structures as a class of sequential circuits with the combinational test generation complexity. However, single stuck-at-faults on some primary inputs, called separable primary inputs, corresponded to multiple stuck-at faults in a transformed combinational circuit. In this paper we resolve this problem. We show how to generate a test sequence and identify undetectability for single stuck-at-faults on separable primary inputs.

In this paper, we introduce strong self-testability for data paths at register transfer level (RTL). A high-level synthesis scheme is proposed for producing such strongly self-testable data paths. This is achieved by incorporating testability constraints during processes of register assignment and interconnection assignment. This method is based on the use of test resources reusability to improve the self-testability of data path. Experimental results are presented to demonstrate the effectiveness of the proposed approach.

This paper presents a new BIST method for RTL data paths based on single-control testability a new concept of testability. The BIST method adopts hierarchical test. Test pattern generators are placed only on primary inputs and test patterns are propagated to and fed into each module. Test responses are similarly propagated to response analyzers placed only on primary outputs. For the propagation of test patterns and test responses, paths existing in the data path are utilized. The DFT method for the single-control testability is also proposed. The advantages of the proposed method are high fault coverage (for single stuck-at faults), low hardware overhead and capability of at-speed testing. Moreover test patterns generated by test pattern generators can be fed into each module at consecutive system clocks, and thus, the BIST can also detect some faults of other fault models (e.g., transition faults and delay faults) that require consecutive application of test patterns at the speed of the system clock.

We present a method of test generation for acyclic sequential circuits with hold registers. A complete (100% fault efficiency) test sequence for an acyclic sequential circuit can be obtained by applying a combinational test generator to all the maximal time-expansion models (TEMs) of the circuit. We propose a class of acyclic sequential circuits for which the number of maximal TEMs is one, i.e., the maximum TEM exists. For a circuit in the class, test generation can be performed by using only the maximum TEM. The proposed class of sequential circuits with the maximum TEM properly includes several known classes of acyclic sequential circuits such as balanced structures and acyclic sequential circuits without hold registers for which test generation can also be performed by using a combinational test generator. Therefore, in general, the hardware overhead for partial scan based on the proposed structure is smaller than that based on balanced or acyclic sequential structure without hold registers.

A non-scan design for testability method is presented for synchronous sequential circuits. A testability measure called conflict based on conflict analysis in the process of synchronous sequential circuit test generation is introduced. Reconvergent fanouts with nonuniform inversion parity are still the main cause of redundancy and backtracking in the process of sequential circuit test generation. A new concept called sequential depth for testability is introduced to calculate the conflict-analysis-based testability measure. Potential conflicts between fault effect activation and fault effect propagation are also checked because they are closely related. The testability measure implies the number of potential conflicts to occur or the number of clock cycles required to detect a fault. The non-scan design for testability method based on the conflict measure can reduce many potential backtracks, make many hard-to-detect faults easy-to-detect and many redundant faults testable, therefore, can enhance fault coverage of the circuit greatly. It is believed that non-scan design for testability using the conflict measure can improve the actual testability of a circuit. Extensive experimental results are presented to demonstrate the effectiveness of the method.

We introduce a new class of sequential circuits with combinational test generation complexity which we call internally balanced structures. It is shown that sequential circuits can be classified by their structure as follows: (sequential circuits of acyclic structure) /spl sup/ (sequential circuits of internally balanced structure) /spl sup/ (sequential circuits of balanced structure) and that internally balanced structures allow test generation with combinational test generation complexity. On the other hand, if finite state machines (FSMs) are classified by their realization possibility, it can be shown that (FSMs which can be realized as a sequential circuit of acyclic structure)=(FSMs which can be realized as a sequential circuit of internally balanced structure) /spl sup/ (FSMs which can be realized as a sequential circuit of balanced structure). Hence, any FSM realizable with acyclic structure can also be realized with internally balanced structure which allows test generation with combinational test generation complexity. In addition, we discuss the definition of test generation possibility with combinational test generation complexity and introduce a new definition which covers the previous narrow definition. Finally, we study applications to design for testability based on the partial scan and to test generation time reduction for sequential circuits in general, using characteristics of the internally balanced structures. The experimental results show the effectiveness of this approach.

As opposed to scan schemes, a non-scan DFT allows at-speed testing. This paper suggests three techniques on non-scan DFT of sequential circuits. The proposed techniques guarantee 100% fault efficiency by using a combinational ATPG tool. In all techniques, an additional circuit called CRIS is proposed to reach unreachable states on the state register of a machine. The second and third techniques use an additional hardware called differentiating logic (DL), that uniquely identifies a state appearing in a state register. The design of DL is universal, i.e., not dependent on the circuit structure. Hardware overhead of DL and CRIS is lower than that of full scan. Test generation and application time are found to compare favorably with those of earlier designs.

Test sequences for acyclic sequential circuits can be generated using a time expansion model. The test sequences have features that: (1) the length of each test sequence for each target fault is uniform, and (2) positions of 'don't cares' (X) of each test sequence for each target fault are independent of any target fault. In this paper, focusing on the features, we present two test sequence compaction methods: static compaction and dynamic compaction. The static test sequence compaction method uses a template. The dynamic test sequence compaction method uses a reverse transformation fault simulation: a fault simulation for a time expansion model with test patterns into which test sequences are reversely transformed after the static compaction. Experimental results for some acyclic sequential circuits show that the compaction methods reduce the number of test patterns by 66% to 81%.

Weak testability is a testability measure for register-transfer level (RTL) data paths. If a data path satisfies weak testability, for each hardware element of the data path, there exist paths from some primary inputs to the element to justify some values on its output and paths from the hardware element to some primary outputs to propagate some values on its output. For a weakly testable data path, a sequential ATPG tool can generate a test sequence with high fault efficiency in a short test generation time. In this paper, we introduce a notion called test knowledge, use of which by commercial ATPG tools can further decrease the test generation time and increase the fault efficiency in weakly testable data paths. This test knowledge is information which is relevant to structure of weakly testable data paths, and also easy to find. Use of this test knowledge to facilitate the test generation and increase the testability of data path is established in experimental results.

This paper presents a high-level synthesis method for testable data paths with partial scan design based on acyclic structure. For a given scheduled data flow graph, we propose a heuristic method of operational unit binding and register binding to minimize the number of scan registers for acyclic structure without sacrifice of area overhead.

In this paper, we theoretically and experimentally show the effectiveness of partial scan design based on internally balanced structure, which is a sequential circuit capable of generating tests with a combinational test generation algorithm. Moreover, we introduce a method of extended partial scan design, which replaces part of not only flip-flops by scan flip-flops but also wires by bypass flip-flops in a sequential circuit, and propose a method of extended partial scan design based on internally balanced structure. Experimental results for benchmark circuits show that the proposed partial scan design and extended partial scan design can be implemented with low area overhead.

We present an approach to test generation using time expansion models. The tests for acyclic sequential circuits can be generated by applying combinational ATPG to our time expansion models. We performed experiments on application to partial scan designed register-transfer circuits. The results show that our approach can reduce hardware overhead and test length compared with full scan while preserving almost 100% fault efficiency.

We present a high-level synthesis method that considers weak testability of generated register-transfer level (RTL) data paths, as well as their area and performance. The weak testability, proposed in our previous work, is a testability measure of RTL data paths for nonscan design. We introduce a design objective for weak testability that is a condition on resource sharing sufficient for weak testability: We propose a heuristic synthesis algorithm that generates a weakly testable data path while minimizing area under a performance constraint.

This paper presents a non-scan design-for-testability method for controllers that are synthesized from FSMs (Finite State Machines). The proposed method can achieve complete fault efficiency: test patterns for a combinational circuit of a controller are applied to the controller using state transitions of the FSM. In the proposed method, at-speed test application can be performed and the test application time is shorter than previous methods. Moreover, experimental results show the area overhead is low.

We present a new non-scan DFT technique for register-transfer (RT) level data paths. In the technique, we add thru operations to some operational modules to make the data path easily testable. We define a testable measure, weak testability, and consider the problem to make the data path weakly testable with minimum hardware overhead. We also define a measure to estimate the test generation time. Experimental results show the effectiveness of our technique and the proposed measure.

In this paper, we introduce universal fault diagnosis such that when applied to an unprogrammed FPGA, it locates a fault in any faulty programmed FPGA corresponding to the unprogrammed FPGA. If a faulty part in an FPGA can be identified prior to programming it, we can implement a required logic function on the fault-free part by isolating the faulty part. Then, we propose a universal fault diagnosis procedure that locates a faulty CLB in a look-up table FPGA. The complexity of the universal diagnosis procedure for FPGAs with block-sliced loading is independent of its array size, i.e., C-diagnosable.

The programming circuit of look-up table based FPGAs consists of two shift registers, a control circuit and a configuration memory (SRAM) cell array. Because the configuration memory cell array can be easily tested by conventional test methods for RAMs, we focus on testing for the shift registers. We show that the testing can be done by using only the faculties of the programming circuit, without using additional hardware.

The test generation problem for a sequential circuit capable of generating tests with combinational test generation complexity can be reduced to that for the combinational circuit formed by replacing each FF in the sequential circuit by a wire. In this paper, we consider an application of this approach to general sequential circuits. We propose a test generation method using circuit pseudo-transformation technique: given a sequential circuit, we extract a subcircuit with balanced structure which is capable of generating tests with combinational test generation complexity, replace each FF in the subcircuit by wire, generate test sequences for the transformed sequential circuit, and finally obtain test sequences for the original sequential circuit. We also estimate the effectiveness of the proposed method by experiment with ISCAS'89 benchmark circuits.

Initialization of sequential circuits is one of time-consuming processes in test generation for sequential circuits, and hence synthesizing sequential circuits of which synchronizing sequences are short is an important approach to reducing the cost of test generation for the circuits. In this paper, we propose an approach to the synthesis of finite state machines (FSMs) with partial scan. We focus on repeating partial scan for synchronizing FSMs, and present an extended synchronizing sequence which consists of scan inputs and normal inputs, and which takes a circuit to a single specific state, regardless of the initial state. To synthesize synchronizable FSMs, we formulate a problem of minimizing extended synchronizing sequence length, and present a heuristic algorithm for the problem. We show the experimental results of the minimization of extended synchronizing sequence length on MCNC'91 benchmark FSMs. The experimental results show that the proposed heuristic algorithm can find a minimum-length extended synchronizing sequence for most of MCNC'91 benchmark FSMs, and the length of the extended synchronizing sequence is three or less for all the benchmark FSMs.

In this paper we consider testing for programmable interconnect structures of look-up table based FPGAs. The interconnect structure considered in the paper consists of interconnecting wires and programmable points (switches) to join them. As fault models, stuck-at faults of the wires, and extra-device faults and missing-device faults of the programmable points are considered. We heuristically derive test procedures for the faults and then show their validness and complexity.

This paper considers distributed algorithms for distributed mobile systems. Many distributed algorithms have been designed for distributed systems consisting of static computers only. But most of them cannot be directly applied to mobile systems. This paper proposes a model of mobile systems. Management of movements of mobile hosts is abstracted in our model to simplify design of algorithms for mobile systems. This paper also defines the snapshot problem, one of the fundamental problems, on the model. The problem requires to find a strongly consistent configuration in which topological consistency is satisfied in addition to causal consistency. Furthermore, this paper presents a snapshot algorithm for mobile systems.

A field-programmable gate array (FPGA) can implement arbitrary logic circuits in the field. In this paper we consider universal test such that when applied to an unprogrammed FPGA, it ensures that all the corresponding programmed logic circuits on the FPGA are fault-free. We focus on testing for look-up tables in FPGAs, and present two types of programming schemes; sequential loading and random access loading. Then we show test procedures for the FPGAs with these programming schemes and their test complexities. In order to make the test complexity for FPGAs independent of the array size of the FPGAs, we propose a programming scheme called block-sliced loading, which makes FPGAs C-testable.

The order of faults which are targeted for test-pattern generation affects both the processing time for test generation and the number of test-patterns. This order is referred to as a test generation schedule. In this paper, we consider the test generation scheduling problem which minimizes the cost of testing. We analyze the effect of scheduling based on test-pattern generation time and dominating probability. Then, we present experimental results on the ISCAS'85 benchmark circuits.

Client-Agent-Server model (CAS model) which can decrease the work load of the client by adding agent processors to the Client-Server model (CS model) is proposed and an approach to parallel test generation for logic circuits on the CAS model is presented. Two problems are considered: optimal granularity problem and optimal scheme problem. First, the problem of parallel test generation on the CAS model is formulated to analyze the effect of the granularity (grain size of target faults allocated to processors) in both cases of static and dynamic task allocation (optimal granularity problem). Then the relationship between the number of processors and the total processing time is analyzed (optimal scheme problem). From the analysis, it is shown that the CAS model can reduce the total processing time over the CS model and that there exists an optimal scheme (an optimal pair of numbers of agent processors and server processors) for the CAS model which minimizes the total processing time for a given number of processors. To corroborate the analysis, the proposed parallel test generation algorithm is implemented on a network of more than 100 workstations and experimental results for the ISCAS benchmark circuits are presented. It is shown that the experimental results are very close to the theoretical results which confirms the existence of optimal granularity and optimal scheme which minimizes the total processing time for the CAS model.>

Points out that scan design approach is representative of those techniques that can reduce the cost of test generation for sequential circuits. However, the length of a test sequence for the scan design approach can grow quite large due to the scan operation shifting the values into the scan chain, which makes the cost of test application large. A design-for-testability approach called parity-scan design which can reduce the cost of test application as well as the cost of test generation for sequential circuits is discussed. The parity-scan design approach is a combination of scan technique and parity testing. Two types of parity-scan designs, preparity and postparity scan design, are presented. Experiments on ISCAS89 circuits show that as high as 91.2% (91.1%) test length reduction and 32.4% (27.0%) average reduction can be obtained for preparity (postparity) scan design under the single scan chain approach. More reduction can be achieved by applying a multiple scan chain technique.>

Points out that scan design approach is representative of those techniques that can reduce the cost of test generation for sequential circuits. However, the length of a test sequence for the scan design approach can grow quite large due to the scan operation shifting the values into the scan chain, which makes the cost of test application large. A design-for-testability approach called parity-scan design which can reduce the cost of test application as well as the cost of test generation for sequential circuits is discussed. The parity-scan design approach is a combination of scan technique and parity testing. Two types of parity-scan designs, preparity and postparity scan design, are presented. Experiments on ISCAS89 circuits show that as high as 91.2% (91.1%) test length reduction and 32.4% (27.0%) average reduction can be obtained for preparity (postparity) scan design under the single scan chain approach. More reduction can be achieved by applying a multiple scan chain technique. >

The computational complexity of fault detection problems and various controllability and observability problems for combinational logic circuits are analyzed. It is shown that the fault detection problem is still NP-complete for monotone circuits limited in fanout, i.e. when the number of signal lines which can out from a signal line is limited to two. It is also shown that the observability problem for unate circuits is NP-complete, but that the controllability problem for unate circuits can be solved in time complexity O(m), where m is the number of lines in a circuit. Two classes of circuits, called k-binate-bounded circuits and k-bounded circuits, are then introduced. For k-binate-bounded circuits the controllability problem is solvable in polynomial time, and for k-bounded circuits the fault detection problem is solvable in polynomial time, when k>

The problem of test generation for logic circuits is known to be NP-hard, hence it is very difficult to speed up the test-generation process due to its backtracking mechanism. An approach to parallel processing of test generation for logic circuits in a loosely coupled distributed network of general-purpose computers is presented, and the effects of allocating target faults to processors, the optimal granularity (grain size of target faults), and the speed up ratio of the multiple processor system compared with a single processor system are analyzed.>

The problem of test generation for logic circuits is known to be NP-hard, and hence it is very hard to speed up the test generation process due to its backtracking mechanism. The authors present an approach to parallel processing of test generation for logic circuits in a loosely coupled distributed network of general-purpose computers. They analyze the effects of the allocation of target faults to processors, the optimal granularity (grain size of target faults), and the speedup ratio of the multiple-processor system to a single-processor system. To analyze the case in which a test pattern generated for one fault can also be a test pattern for other faults if fault simulation is performed, they introduce a ratio of newly processed faults to target faults and derive the expressions of optimal granularity in cases of both static and dynamic task allocation. They also derive an expression of the speedup of a multiple-processor system in the homogeneous case. The analysis indicates that the speedup approaches N, the number of servers, if the data transfer time per fault and the waiting time per communication are much smaller than the processing time per fault and if the decrease ratio of newly processed faults due to overlapped processing is much smaller than the ratio of newly processed faults.>

A testable design of programmable logic arrays (PLAs) with high fault coverage for random test patterns is presented. The proposed design is realized with low area overhead by adding two mask arrays to the AND and OR arrays of the PLA. An experiment was performed to demonstrate the effect of the masking technique. In the experiment, eight large PLAs were modified by adding mask arrays of various sizes; fault simulation with random patterns for modified and unmodified PLAs was then carried out to obtain random-pattern test coverage curves. Fault coverage can be significantly enhanced via the proposed masking technique with very low area overhead.>

A testable design is presented of programmable logic arrays (PLAs) with high fault coverage for random test patterns. The proposed design is realized with low area overhead by adding two mask arrays to the AND and OR arrays of the PLA. To clarify the effect of the masking technique, an experiment was performed in which eight large PLAs were modified by adding various sizes of mask arrays, and then performing fault simulation with random patterns for those random-pattern test coverage curves. It was found that fault coverage could be significantly enhanced by the proposed masking technique with very low area overhead.>

A testable design of programmable logic arrays (PLAs) with high fault coverage for random test patterns is introduced. Low area overhead is achieved by adding a mask array between the input-decoder and the AND array of the PLA. Several variations of the proposed approach are presented. The probability of fault detection and the test length are examined for both stuck-type and crosspoint-type faults to estimate the fault coverage achievable with the random patterns.>

This correspondence presents a new built-in self-test design for PLA's, that has a lower area overhead and higher multiple fault coverage (of three types of faults: crosspoint, stuck, and bridging) than any existing design. This new design uses function independent test input patterns (which are generated on chip), compresses the output responses into a function independent string of parity bits (whose fault-free expected values are generated on-line with a simple circuit), and detects all siqgle faults and more than ( 1 −−2(m+2n) of all multiple faults where m and n represent the number of product terms and input variables, respectively.

A new design of universally testable PLA's is presented in which all multiple faults can be detected by a universal test set which is independent of the function being realized by the PLA. The proposed design has the following properties. 1) It can be tested with function-independent test patterns; hence, no test pattern generation is required. 2) The amount of extra hardware is significantly decreased compared to the previous designs of universally testable PLA's. 3) Very high fault coverage is achieved, i. e., all single and multiple stuck faults, crosspoint faults, and adjacent line bridging faults are detected. 4) It is appropriate for built-in testing approaches. 5) It can be applied to the high-density PLA's using array folding techniques.

In order to accelerate an algorithm for test generation, it is necessary to reduce the number of backtracks in the algorithm and to shorten the process time between backtracks. In this paper, we consider several techniques to accelerate test generation and present a new test generation algorithm called FAN (fan-out-oriented test generation algorithm). It is shown that the FAN algorithm is faster and more efficient than the PODEM algorithm reported by Goel. We also present an automatic test generation system composed of the FAN algorithm and the concurrent fault simulation. Experimental results on large combinational circuits of up to 3000 gates demonstrate that the system performs test generation very fast and effectively.

In this paper, the problem of fault detection for multiple faults in programmable logic arrays (PLA's) is discussed. An easily testable design of PLA's has been proposed which has the following properties: 1) for a PLA with n inputs, m product terms, there exists a test set such that the test patterns do not depend on the function realized by the PLA; 2) the number of tests to detect multiple stuck type and cross point faults is m(2n + 1) + 4n + 4; 3) the number of additional pins for the testable design is 3; 4) the design philosophy is compatible with the built-in-testing approaches.

In this correspondence we analyze the computational complexity of fault detection problems for combinational circuits and propose an approach to design for testability. Although major fault detection problems have been known to be in general NP-complete, they were proven for rather complex circuits. In this correspondence we show that these are still NP-complete even for monotone circuits, and thus for unate circuits. We show that for k-level (k ≥ 3) monotone/unate circuits these problems are still NP-complete, but that these are solvable in polynomial time for 2-level monotone/unate circuits. A class of circuits for which these fault detection problems are solvable in polynomial time is presented. Ripple-carry adders, decoder circuits, linear circuits, etc., belong to this class. A design approach is also presented in which an arbitrary given circuit is changed to such an easily testable circuit by inserting a few additional test-points.

The concept of closedness of a set of logic functions under stuck-type faults is introduced. All sets of logic functions closed under stuck-type faults are classified. For the sets of logic functions closed under stuck-type faults, the test complexity and the universal test sets are considered. It is shown that for each class of linear functions, OR functions, and AND functions, both the minimum numbers of multiple fault detection tests and multiple fault location tests are exactly n + 1, where n is the number of inputs of the circuits, and that there exists universal test sets with n + 1 tests to detect and locate all multiple faults in such circuits.

In this paper the problem of fault detection in easily testable programmable logic arrays (PLA's) is discussed. The easily testable PLA's will be designed by adding extra logic. These augmented PLA's have the following features: 1) for a PLA with n inputs and m columns (product terms), there exists a "universal" test set such that the test patterns and responses do not depend on the function of the PLA, but depend only on the size of the PLA (the values n and m); 2) the number of tests is of order n + m. For the augmented PLA's, universal test sets to detect faults in PLA's are presented. The types of faults considered here are single and multiple stuck faults and crosspoint faults in PLA's. Fault location and repair of PLA's are also considered.

In this paper we analyze the computational complexity of system diagnosis. We show that several problems for instantaneous and sequential fault diagnosis of systems are polynomially complete and that for single-loop systems these problems are solvable in polynomial time.

This correspondence is concerned with probabilistic fault diagnosis for digital systems. A graph-theoretic model of a diagnosable system introduced by Preparata et al.[3] is considered in which a system is made up of a number of units with the probability of failure. The necessary and sufficient conditions are obtained for the existence of testing links (a connection) to form probabilistically t-diagnosable systems with and without repair. Methods for connection assignments are given for probabilistic fault diagnosis procedures with and without repair. Maheshwari and Hakimi [10] gave the necessary and sufficient condition for a system to be probabilistically t-diagnosable Without repair. In this correspondence, we show the necessary and sufficient condition for a system to be probabilistically t-diagnosable with repair.

This correspondence is concerned with probabilistic fault diagnosis for digital systems. The model considered in this correspondence is the diagnostic model introduced by Maheshwari and Hakimi where each unit has a probability of failure. For this model under both fault assumptions by Maheshwari-Hakimi and by Barsi-Grandoni-Maestrini, some existence theorems are obtained for probabilistically diagnosable systems. 1) Necessary and sufficient conditions for the existence of testing links to form probabilistically t-diagnosable systems with and without repair. 2) Necessary and sufficient conditions for the existence of probabilities of failure of all units to form probabilistically t-diagnosable systems with and without repair which have no hardcore.

In this paper, an easily testable machine is defined as one which possesses: 1) a distinguishing sequence of length [log2 n] which forces the machine into a specific state S1, and 2) transfer sequences of length at most [1og2 n] to carry the machine from state S1 to state Si for all i. A design procedure is presented in which an arbitrary machine is augmented to an easily testable machine by adding two special input symbols to the original machine. An efficient procedure is also described for designing checking experiments for the easily testable machines. For an n-state, m-input symbol machine, this procedure gives a bound on the length of the checking experiment that is approximately mn[log2,n]. Furthermore, the total checking experiments are preset.

This paper is concerned with the problem of designing easily testable sequential machines, output-observable machines, for which there exist very short checking experiments. A sequential machine for which any initial state can be uniquely determined only by the output response is said to be output-observable. An algorithm is developed to modify a given machine to an output-observable one by adding a minimum number of extra outputs. This method is based on the fact that the output-observable realization of a given machine M exists if and only if M is semi-FSR realizable (a special type of feedback shift register realization).