Figure 1. A typical automated design environment
Fatemeh Khaani* and Zainalabedin Navabi
Electrical and Computer Engineering Department
Faculty of Engineering, Campus No. 2
University of Tehran
14399, Tehran IRAN
We have developed a modeling strategy in VHDL for gate level components for automatic test generation. A gate level structural description using these models is capable of generating its own test vectors for induced faults on its lines. A testbench places a fault on a line of the gate level description, and the models communicate through their ports for finding a test vector detecting the fault. This paper describes a test environment, our VHDL models, and a fault activation testbench.
In the area of digital system design, test generation plays an important role. The process of finding input test vectors for detecting possible circuit faults is referred to as test generation. Fault oriented deterministic test generation is referred to the algorithmic generation of a test vector that targets a specific fault in the circuit. The D-algorithm and PODEM are such test generation methods. These algorithms are generally slow and limited in scope. A uniform test environment in which various test related tools such as test generation and fault reduction programs are interactively used, can make up for the inefficiency of test generation programs.
Because VHDL has become an important part of the design automation of digital systems, it is appropriate to think of this language as a tool that can be used in all aspects of digital design. Ideally, the same language and circuit description used for design and simulation should be used for the generation of test vectors and fault dictionaries. Using VHDL for test generation is an important step towards using VHDL as the basis of an integrated design environment for digital circuits. Furthermore, the use of concurrent programming techniques, such as those available in VHDL, can benefit test related programs for their implementation on distributed systems.
We have developed VHDL models for test generation. The models generate test using a sensitized path, deterministic fault oriented test generation method. Basic logical gate models and line resolution functions constitute the main part of our modeling. For test generation, a testbench uses a structural description of hardware bound to our test generation gate models, and activates a fault on a resolved circuit line. The models interact through their ports and find a test vector for the fault. This test vector will be reported by the testbench.
During the generation of test, the models are placed in two main modes of propagation and justification. In the propagation mode, the models interact through their ports for finding a sensitized path from the site of an introduced fault to the primary outputs. In the justification mode, the models justify node values by justifying a set of values on the primary inputs. The values found on the primary inputs constitute the test vector for the introduced fault.
This paper discusses a general test environment, VHDL based path sensitization test generation, VHDL models for test generation and details of our VHDL test generation methodology. Section 2 discusses test in VHDL and presents a justification for the use of VHDL in such environments. In Section 3 we will present an overall view of the VHDL test generation models. Details of the models and VHDL coding techniques will be discussed in Section 4. Although many test environments can take advantage of VHDL test generation models, a simplified testbench for the activation and usage of our models will be demonstrated in Section 5. In conclusions, Section 6, a simple circuit and test vectors generated for this example will be presented.
A general design environment consists of various CAD tools for simulation, synthesis and test. In an ideal situation all such tools work in an integrated environment using the same file formats and platforms.
2.1. A Design Environment
A typical automated design, shown in Figure 1, begins with a high level description of the design. After high level design verification, the design is synthesized into a gate list which can be used as the input of a low level simulation as well as a test generation program. Generation of fault dictionaries and fault lists are also done at this stage using the same netlist. After test generation, and design verification, the netlist is used as input to a placement and wiring program for the final hardware generation and fabrication.
Present CAD tools based on VHDL make this language an ideal basis for the development of an integrated design automation environment. Although extensive works has been done on VHDL based simulation and synthesis, test generation and other test related issues are still to explore the capabilities of VHDL.
Figure 1. A typical automated design environment
An initial requirement in the design of VHDL was to be able to have a media for design documentation, synthesis, simulation and test of digital systems. Although simulation and synthesis have been successful in using this language, little attention has been given to test and test applications with VHDL. Using VHDL in test will enable a designer to simulate, design and test various parts of his circuit under the same environment. Thus using VHDL for test generation is an important step in taking advantage of this standard in test applications.
Strong support for the libraries makes VHDL an appropriate tool for use in an integrated design environment. A VHDL netlist can be used for simulation by binding its components to a simulation library. The same netlist can be bound to a test generation library for test generation for the circuit.
The syntax and semantics of VHDL make the implementation of various test related problems possible in this language. Concurrency in the language, resolution functions, and event driven nature of the language are useful in the implementation of test generation.
In addition to test generation, we have used VHDL for critical path analysis, fault simulation, and fault collapsing. The set of these test related tools, and using them along with present synthesis and simulation programs, can create an integrated design environment based on VHDL. In this environment, use of various test programs can be intelligently decided by a VHDL test program. Appropriate use of fault lists, using fault list generation programs, choosing fault-independent test generation versus fault-based test generation are tasks that an overall VHDL program can make decisions on.
In our method of test generation in VHDL, we start with a VHDL netlist of a combinational circuit. The components of this netlist are basic logical gates, and test is generated by special test models that we have developed for these gates. In implementing the VHDL gate models, we have used the path sensitization method and D notation for generating tests for SSFs using structural model of the given circuit. In this section we will describe the general strategies used in the development of VHDL models for structural test generation. The next section describes details of the models.
3.1. Gate Level Modeling
As mentioned above, the focus of our modeling is for the structural test generation. This implies that the analysis is based on a structural, rather than a functional, model of the circuit. The components of this structural model are primitive logical gates; AND, OR, NAND, NOR and NOT.
In addition, for resolving problems associated with reconvergent fanouts, a fanout component has also been used. Using components for fanout is a common approach in fault simulation and test generation [3]. A fanout component has one input and two outputs. Any number of these components can be cascaded together for obtaining multi-output fanouts.
3.2. Bidirectionality
Sensitized path method generates test in two phases, fault propagation and line justification. Thus it is clear that a gate must be able to react to changes on its inputs as well as its output (or outputs in the case of fanout components). In propagating values towards primary outputs, gates take input values and generate output values, and in justifying a set of values at the primary outputs, gates propagate values from their output to their inputs and towards the primary inputs.
To make this bi-directional behavior possible, INOUT has been used for the mode of all ports. When in the propagation mode, gates only react to events on their inputs, and when in the justification mode, gates react to transactions on their outputs as well as on their inputs. Another mode of operation is initialization, in which gates are sensitive to events on both their inputs and outputs.
3.3. Node Resolutions
Since all lines are INOUT, each interconnecting line is driven by at least two drivers. Therefore, we have used resolved signals for all interconnecting lines. This enables gates to use their ports in both directions for fault propagation and line justification.
Using resolved signals allows the corresponding resolution function to resolve conflicts that occur between a gate output and a gate input. When a conflict occurs, the resolution function informs both conflicting gates. Such gates will take appropriate actions according to the type of the conflict.
The next section presents a more detailed view of the behavior of the models and the resolution functions.
We have used VHDL for the implementation of path sensitization test generation methodology. For this purpose a test generation model is developed for gate level hardware primitives. For test generation of a logical circuit, circuit primitives are bound to test models, and by proper fault insertion and gate activation, a test is generated for that specific fault. In this section we will describe the details of the models for path sensitization test generation.
4.1. How Models Work
Each gate model is designed to be able 1) to receive a fault at one of its inputs and propagate the fault to its output, and 2) to receive a signal on its output and justify its inputs accordingly.
Fault representation is done by the use of the D notation. In this notation D and DBAR values represent faulty node values. D (DBAR) at a node indicates that the good circuit value at this node is '1' ('0') and the faulty value is '0' ('1'). Figure 2 shows a minimum logic value system for the implementation of test generation in VHDL.
'0' : A line value of '0'
'1' : A line value of '1'
'X' : either a '0' or a '1'
D : A faulty line value, Good '1' & Bad '0' (1/0)
DBAR : A faulty line value, Good '0' & Bad '1' (0/1)
'U': Undefined value ( initial value of all nodes)
Initially, for fault activation, a D or DBAR value is placed on a circuit node. The model sensing this event (a delta time later) propagates this value to its output node. The gates seeing this propagated value (at the next delta time values) at their inputs continue the propagation process until the error (D or DBAR) reaches a primary output several delta times later than the original placement of fault. At this point the justification process must begin.
4.1.2. Justification
In the justification process events originate on the gate outputs, and each gate model places values on its unassigned inputs such that these values justify its output value. In order for the gates to be able to distinguish between propagation and justification phases of operation, we have separated these two phases by 1femtosecond. As shown in the illustration of Figure 3, at a certain time ti an event on a node causes all gates to propagate input value(s) to their outputs. At this same time, a primary output receives the error. At time ti+1femtosecond the error value (D or DBAR) at the primary outputs are placed back on these lines. Gates sensing these transactions begin operating in the justification mode. Each gate depending on its output value and its inputs that were valued in the propagation phase, determines certain values for its undecided inputs. Assignment of these values to the inputs causes the justification process to go farther towards the primary inputs. When the primary inputs are justified, the test for the fault applied at time ti has been found.
Figure 3. Propagation and justification phases
Before applying the next fault, the circuit is reset (initialized) at time ti+2 femtoseconds. In this phase SU value (Strong 'U') will be imposed on all circuit nodes. An SU value overrides all previous node values.
The next fault is applied after the circuit node values are reset. At time ti+1 a new fault will be placed on a circuit node and the processes of propagation and justification begin for this fault. The difference between ti+1 and ti has chosen to be at least 3 femtoseconds. Figure 4 shows timing of these phases of operation.
|
We will discuss the working of the VHDL gate models by use of several examples covering various decisions made by the models. We start with the simple circuit of Figure 5. A test can easily be found for a stuck-at-zero on node l9, i.e., no conflicts will occur and a simple justification pass is required.
Figure 5. An illustrative example
|
In certain cases when justifying values, two conflicting values may reach a fanout node. In this case, the fanout node should inform the driving gates that a conflict exists and all gates must try to resolve this situation. In such cases, gates may be able to resolve the conflict locally, or they have to propagate the conflict to other gates they are driving. In this section we will discuss the situation that gates can resolve conflict locally. Figure 7 shows a conflict that occurs when the AND gate requires a '0' output and the OR gate requires a '1' output.
Before a conflict propagates out of the local area it has occurred, we will make sure that all gates in this local area have tried all their possibilities. For example for the conflict shown in Figure 7 the AND gate or the OR gate can resolve the conflict by choosing another set of input values that can still lead to the same output value of the gate. For this reason, before a gate propagates a conflict to its output, it insists on its values, so that other gates in this local conflict will consider resolving the situation.
Figure 7. Illustration of a conflict
A conflict can simply be resolved if gates that have option in changing their input values inform the conflicting node of their possible input change. Consider the example shown in Figure 8. VHDL gate models for the generation of a test vector for l9 Sa0 (D) fault, behave as outlined in Figure 9.
Figure 8. Local conflict resolution; non insisting
|
|
If a gate can not change its input values, it returns insisting value to the resolution function. This situation will be discussed in the following section.
Figure 11. Local conflict; insisting on present values
A different situation than that presented in the previous section is that the gate seeing a conflict on its input can not change its input value and therefore insists on its existing value. We will use the example of Figure 11 to illustrate this case.
For detecting a Sa0 on line l5, a D value is placed on this line. The sequence of events for propagation and justification of this value is shown in Figure 12. As shown in Step 6 of Figure 12, a normal propagation and justification causes a conflict on the fanout node of circuit of Figure 11. As in the previous section, the resolution function tries to resolve the conflict by placement of CM0 and CM1 on lines l3 and l4. Assuming a CM0 is placed on lines l3 and l4, G2 finds that it can not change its l3 input to agree with the presented majority (CM0) vote. It will therefore insists on its '1' value by assigning an IO1 to this line (IO0 and IO1 stand for Insist On '0' and Insist On '1' respectively).
|
|
4.3. What If Conflicts Grow Out Of A Local Area
In the previous section conflicts were resolved by either of gates that contributed to the creation of the conflict. In this section we will describe the case that a conflict can not be resolved locally. Consider the example of Figure 14. For a Sa1 on l6, the fanout node driving stems l2 and l3 has a '0' on l2 and a '1' on l3. According to the sequence of events of Figure 15, this conflict must be propagated beyond G1 into G2.
Figure 14. Conflict resolution; out of the local area
|
As in most test problems, test generation methods must give special attention to reconvergent fanouts. The situation becomes more difficult when fanout branches with different inversion parities converge. The main problem of reconvergent fanout is the possibility of propagation of fault via several paths. Using multiple paths to propagate a fault may result in one propagation path to be masked by another. On the other hand, choosing another set of fanout branches for fault propagation may properly lead the fault to occur on a primary output. We will therefore need a systematic exploration of the complete space of possible solutions in order to reach an appropriate set of propagating paths. In other words, for a fanout node with n branches, 2n-1 possible paths exist, only some of which may propagate a fault to a primary output.
Figure 16. Illustration of reconvergent fanout problem
In the VHDL implementation, in order to choose propagation branches and separate them from those that are not to propagate a fault, we use two new values NPD and NPDBAR (Non Propagating D or DBAR) to indicate that a fault is not to be propagated through a branch. Because different fanout branches take different values and also because the choice of the combination of values on fanout branches has to be remembered, we have used a fanout component at fanout nodes. Note that a resolution function, as is used in all other nodes, would not be capable of memorizing any information.
In the example of Figure 16, the fanout component at the fanout node would initially chose to propagate (D,D) on l4 and l5 from the set of { (D,D), (D,NPD), (NPD,D) } possibilities. As described above, (D,D) leads to a '1' on the primary output. The second choice (D,NPD) would cause the DBAR value to reach l9, while NPD at l5 remains on that line and the G3 gate does not react to this value.
4.5. Faults That Cannot Be Detected
Two Categories of faults can not be detected. One is undetectable and the other is aborted faults. The former occurs in circuits with reconvergent fanout(s). As described in the previous section a complete set of all possibilities of propagating through branches is tried at a fanout node. If all possibilities are tried, and none of them leads to propagation of the desired fault to a primary output, the fault is declared as undetectable. Such faults occur only in circuits with redundancy [3].
The second category, referred to as aborted faults, are those that our method finds them hard to detect, and therefore declares them as undetectable. In section 4.4 if backtracking is repeated more than a fixed limit, the fault is assumed undetectable.
|
4.6. VHDL Style
We have presented modeling details for VHDL gate models for test generation. In this part we will present a partial VHDL code that shows the outline of the model for a 2-input gate.
As shown in Figure 17, a gate model consists of a PROCESS that always waits until a TRANSACTION appears on one of its inputs or output. After this TRANSACTION, according to mode of operation and value of the signal that activates the PROCESS, initialization, error propagation, line justification or attempt in conflict resolution will be done. Details of these operations were discussed in the previous sub-sections.
The previous sections described VHDL models for basic logical gates. This section presents an environment in which a circuit description using the gate models can be used for generation of test pattern for the circuit. Figure 18 shows a general outline of the VHDL code for a testbench.
|
After several delta times, either a test is generated, or the fault is declared as undetected. If fault is detected, fault list array is updated by removing the present fault and other faults known to be detected by the generated test. The process described here for generating test vector continues until there are no more faults in the fault list.
|
|
Figure 21 . A typical use environment
We have used VHDL for test generation which is an important tool for design and analysis of digital systems. Although we have only considered combinational test generation, design for testability (DFT) techniques make such methodologies applicable to general digital circuits. In addition to test generation VHDL models, we have also developed VHDL models for fault collapsing, VHDL models for critical path tracing, as well as models for parallel fault simulation. After simulation and synthesis, test seems to be an appropriate area for using VHDL in digital system design automation.
Models presented here have been tested with most circuits available in various texts and literature. We have been able to generate test for all circuits found in literature that contain classical hard to detect faults.