ABSTRACT

In the area of digital system test, fault collapsing is referred to the process of reducing faults in a circuit to only those that can be distinguished. In local fault collapsing, one fault is selected from each of the equivalent fault classes of logical gates. The selection will be based on the connections made to the ports of a gate. We have developed VHDL gate models for local equivalent fault collapsing. This paper presents test environments using fault collapsing, our VHDL modeling strategies, and an example.

Digital system test involves various tools for simulation, fault list generation, fault reduction, and test generation. Because test generation programs are time consuming, it is best to be able to generate tests for only those faults that can be distinguished, so that the redundancy in test vectors is minimized [3]. Fault collapsing is the process of reducing faults in a circuit to only those that can be distinguished. An inexpensive method for fault collapsing is the local fault collapsing. This methods is particularly efficient for gate level combinational circuits. In local equivalent fault collapsing faults on ports of logical gates are collapsed such that only one fault from each equivalent class of faults remain on the ports of the gate. A typical test environment uses fault collapsing to obtain a reduced fault list, uses test generation to generate test vectors for the list of faults, and uses fault simulation for discarding faults detected by a generated test.
In order to be able to use VHDL in an integrated design, simulation and test environment, appropriate VHDL models must be developed. In such an environment, the same VHDL gate level description can be bound to simulation models for design verification, to test models for test generation, or it can be bound to fault collapsing models for finding an optimum fault list.
VHDL gate models for local fault collapsing start with a set of all possible faults of a gate. The gate models by communicating through their IO ports decide on a minimum list of distinguishable faults and report such faults to a text file. Fault collapsing can be done for a VHDL gate level description by binding the structures of this description to the fault collapsing models. A fault list report generated for this description specifies a reduced list of faults for the entire circuit.
This paper presents VHDL models for local equivalent fault collapsing in gate level descriptions. Section 2 discusses issues related to fault collapsing. In Section 3 we will present an environment that relates fault collapsing to other test issues. Section 4 describes rules used in our VHDL models for fault collapsing. In Section 5 VHDL implementation and coding will be discussed. At the end, an example and conclusions will be presented.

Test generation for digital circuits can be done by functional analysis of the circuit or by considering individual circuit faults. A fault oriented test generation method usually deals with single stuck at faults (ssf) when are either stuck at 0 or stuck at 1 (sa0,sa1). This implies that the test generation scheme generates a structural model of a circuit with a single fault on a circuit line [2]. For a sa0 (sa1) fault the line being faulted is assumed to have a 0 (1) value, and test generation schemes generates an input pattern at primary input to cause the value of the fault to propagates to the output. Faults in a circuit may be such that no sequence can be found to distinguish between them. These faults are said to be functionally equivalent, which implies that the function of the circuit is the same when either of the faults occur [3]. A digital circuit contains many equivalent faults, and the process of reducing list of faults to contain only those that can be distinguished (not equivalent) is called fault collapsing. For example for a gate with n-input and one output there may be 2(n+1) possible single stuck at faults. This is contributed by sa0 and sa1 at each input and the output. For an AND gate, stuck at 0 faults at all inputs and the output are functionally equivalent and can not be distinguished from each other. Therefore, distinguishable faults in an n-input gate are limited to n+2 ssf. Expanding this concept to an entire circuits, it is obvious that a good number of faults in a circuits are equivalent. A test generation program will only need to generate test for such distinguishable faults.

In the previous section we indicted that many faults in a circuit are equivalent and the process of fault collapsing can be used to reduce a fault list to only those that can be distinguished. This section presents an outline of the usage of fault collapsing in a test environment. A test environment may consist of tools for test generation, simulation, and testability analysis. A possible scenario for using equivalent fault collapsing in a test environment is to generate an optimum fault list to direct test generation process.

Figure 1. A general use of fault collapsing

Such a scenario, shown in Figure 1, uses a netlist for the input to the fault collapsing process. The result of this process is a reduced fault list in which only distinguishable faults are listed. A test generation program selects a target from a fault list and generates an appropriate test. This test is fed into a fault simulation program to remove all other faults that it detects. The process of test generation and fault simulation repeats until there are not any detectable faults in the fault list. Although fault collapsing can be based on fault equivalent and/or dominance relation we will only consider fault equivalent. A test pattern based on a fault list which is obtained this way will be able to find fault location as well as detecting single stuck at faults.

Generally fault collapsing involves collapsing faults on adjacent nodes of a line, and removing equivalent faults on local I/O port of basic logic gates. This fault collapsing is usually refereed to as local gate level equivalent fault collapsing. A method based on local processing of gates and lines that can be efficiently implied by VHDL gate models will be presented here.


4.1. Isolated Structural Faults

Figure 2-a shows an AND gate with all possible faults at its inputs and outputs. A filled (hollow) circle signifies an sa0 (sa1) fault. It is clear that sa0 fault at any of the inputs or at the output can not be distinguished when the output of the gate is observed or is propagated to next logic stages. Therefore a complete set of all distinguishable faults for this gate include sa1s (hollow circles) at the input and the output and a sa0 at either of the input or the output, as shown in Figure 2-b. Another way of considering the three options in placement of the sa0 fault is to consider it as a "float fault" that belongs to the AND gate and can go on any of its ports. This is shown in Figure 2-c. Non floats faults are referred to as fixed faults [4].

Figure 2. Float and Fixed faults

4. 2. Local Collapsing Rules

Float and fixed faults can be collapsed into their adjacent faults when gates are connected to fanouts, primary inputs or directly to outputs of the gates [5]. Figure 3 shows how various forms of these connections cause collapsing of gate input faults for a 2 input AND gate. These rules are local to each gate.

Figure 3. Fault collapsing based on input connections

If an input of a gate is driven by an output of another gate, the fixed fault at the gate input collapses into a similar fault at the output of the driving gate. For example in Figure 3-(a,b,c) if the driving gate connected to the input of the AND gate is output of an OR gate, the AND gate, based on the fact that the previous gate has the same fault at its output, removes the sa1 fault at its input driven by the OR gate. Similarly the float fault that can go on any of the inputs or the output of the AND gate finds the output of the previous gate and appropriate place for itself to collapse into. There is a chance the driving gate can further collapse this fault into its driving input. If an input is connected to a primary input, the fixed fault at the gate input is collapsed into the same fault on the same connecting line driven by the primary input. This is illustrated in Figure 3-(d,e,f). The fault on gate input connecting to primary inputs is moved away from the gate to the primary input side of the connecting line. A float fault can collapse into faults on any of the ports of a gate. Since a primary input is a dead-end as far as further collapsing is concerned, we do not collapse a float fault into a primary input. For a gate with all its inputs connected to primary inputs, we have chosen the output to the gate to hold the float fault. This way, the float fault absorbs all similar faults at all primary inputs. Float fault in Figure 3-e finds a gate output at one of its inputs to collapse into. As shown in Figure 3-(g,h,i), float and fixed faults at gate inputs connected to fanouts behave like those of inputs connected to primary inputs.
Rules described in the previous paragraphs specify the placement of a fault on a specific end of a connecting line. Clearly, a fault can be placed on either end of a line. In the implementation of our models, faults are generated and reported by the gate that uses a line as input.
Rules described here can be justified by use of a simple example. Figure 4-a shows a circuit with fixed and float faults at gate ports, primary inputs and fanouts. Figure 4-b shows the resulting faults after applying the above rules. Gate 8 has three fixed and a float fault. The fixed faults at its inputs are collapsed into the outputs of gates 6 and 7, and its float fault can be collapsed into any of these gates. Gate 6 collapses both its fixed faults into lines that it is connected to. The float fault on this gate absorbs both similar faults at the PI and the fanout, and appears only on the output of the gate. Application of our rules reduce the number of faults from 24 to only 13. As described earlier, faults on fanout stems can be reported by the gates connected to the stems.

Figure 4. Example collapsing

A special situation arises when a gate has input stems branched from the same fanout, as show in Figure 5. Application of our rules results in faults shown in Figure 5-b. Faults on lines A ,B, and are all equivalent and, can be represented by a similar fault on line A or the output. On the other hand, the float fault on the output of the gate can absorb the sa0 fault on line A resulting into a single float fault. Circuit with the reduced faults is shown in figure 5(c). This figure shows two float fault for the entire gate structure. These faults can collapse into faults of connecting structure by applying rules of this section. It is worth while to mention that a buffer and an inverter, figure 6, also have two float faults as is the structure of Figure 5.

In the previous section we presented rules for a fault collapsing method. This method is a variation of several existing methods which have been adapted so that their combination can work as independent local VHDL models. In this section the general outline of VHDL codes for the implementation of these models will be discussed. We will present types used, resolution functions and a typical gate model [6],[7].

5.1. General Structures

A simulation run begins with all gates having all possible faults on their ports. The models are designed such that they report faults that remain on their input and output lines after fault collapsing has been completed. Primary inputs are treated as components that originally contain sa0 and sa1 faults on their only output line. These component also report collapsed faults if they drive fanouts. In order to be able to pass information to and from various components via their inputs and outputs, all signals are of INOUT mode and resolved.


5.2. Signal Types

All interconnecting signals are of a record type shown in Figure 7. This record (carrier) contains fields for passing enough information between gates so that each gate can decide on faults that collapse on its ports. Base type declaration for the fields of this record are shown in Figure 8.

TYPE carrier IS RECORD
   N:node_r;
   S:stem_r;
   I:id_r;
   F:nin_r;
END RECORD;

TYPE node IS (branch,lin,tree);
TYPE stem IS (gate_in,gate_out,primary_in);
SUBTYPE id   IS natural;
SUBTYPE nin  IS natural;  

The four types shown in this figure use resolution functions identified by node_f, stem_f, id_f, and nin_f. The base type for field N is node. The node_f resolution function is shown in Figure 9. This field is used for distinguishing between simple lines and fanouts.

FUNCTION node_f(drivers:node_vector) RETURN node IS
  BEGIN
      IF  drivers'LENGTH > 2  THEN 
         RETURN tree;
      ELSE
         RETURN lin;           
      END IF;
END node_f;

All component ports report to this function. The function counts the number of connecting lines and returns lin if there are only two drivers on the end of a line, and returns tree if there are more than two connections (fanout). Since rules of Section 4 treat fanout differently, this information is needed by the models.
The next field of the carrier record is of type stem. This field (S) uses the stem_f resolution function shown in Figure 10 and is used for identifying the logic driver of a line. The values this field can take are gate_in, primary_in or gate_out. If a line is connected to a gate output, the S field value becomes gate_out, and if it is connected to a primary input S becomes primary_in.

FUNCTION  stem_f(drivers:stem_vector) RETURN stem IS
  BEGIN
       FOR i IN drivers'RANGE LOOP
           IF drivers(i)=primary_in THEN    
              RETURN primary_in;
           ELSIF drivers(i)=gate_out THEN 
              RETURN gate_out;
           END IF;
       END LOOP;
              RETURN  gate_in; 
 END stem_f;   

The I field of the carrier record is of type id_r, and returns the id number of the gate or PI where output is connected to a line. The id number of each gate is a unique natural number produced by an up-counter. Input lines assign 0 to the id_f resolution function and this function, shown in Figure 11, returns the only non zero driving value.

FUNCTION id_f( drivers:id_vector)RETURN id is
  BEGIN
       FOR i IN drivers'RANGE LOOP
           IF drivers(i) > 0 THEN      RETURN  drivers(i);
           END IF;
       END LOOP;
       RETURN  0;
END id_f;

The id field is necessary for the implementation of rules for collapsing faults on several fanout stems driving the inputs of the same gate, Figure 5. Such a gate knows of its special case when it finds the same id on both its inputs.

FUNCTION nin_f( drivers:nin_vector)RETURN nin is
  BEGIN
RETURN    (drivers'LENGTH -1);
END nin_f;

The F field is of type nin_r which is used with the nin_f resolution function shown in Figure 12. The nin_f resolution function returns the total number of its connecting lines. This information is used by gates with more than one input connected to the same fanout. Reading nin, such a gate will recognize if fanout is also feeding other gate structures. Only in this case a fanout is treated the same as other fanouts. The example of Figure 13(a) shows a fanout which we will treat as a regular node, while Figure 13(b) shows a fanout node of two stems.

Figure 13. Use of nin for identifying real fanouts (a) Not a fanout, (b) A real fanout

5.3. Gate Architectures

Using types and resolution functions described above, architecture for basic logical gates have been developed. Each gate is identified by a unique id number passed to it via a generic parameter. This number appears in all fault reports in a text file. Gates wait for a certain amount time that is proportional to their gate_id before reporting their faults to the text file. Therefore fault report is sorted according to the gate id numbers.

ENTITY nand2_fc IS
  GENERIC(gate_id:NATURAL); PORT(i1,i2,o1:INOUT status);
END nand2_fc;
--
ARCHITECTURE collapse OF nand2_fc IS
BEGIN
o1 <= (branch,gate_out,gate_id,gate_id);
i1 <= (branch,gate_in,0,0);  i2 <= (branch,gate_in,0,0);
PROCESS
BEGIN
... 
  WAIT FOR  gate_id*1 NS;
  IF (i1.N=lin) AND (i1.S=gate_out) THEN 
   	   IF (i2.N=lin) AND (i2.S=gate_out) THEN report ... 
   	   ELSIF  ... report  ...
  ELSIF (i1.N=lin) AND (i1.S=primary_in) THEN
            IF (i2.N=lin) AND (i2.S=gate_out) THEN  report ...
	     ELSIF  ... report...
  ELSIF (i1.N=tree) THEN
 ...
   END IF;
  END IF;
 WAIT;
END PROCESS;  END collapse;

As shown in Figure 14 each gate provides information regarding its line type, id, and input or output line on all its bi-directional IO ports. A two-input NAND gate, for example, places branch on the node field of its ports. The gate reads from this field either lin or tree indicating a fanout of it exists. On the stem field (for clarity, field is being referred to by its type, instead of its name) the output places gate_out and the inputs place gate_in. The gate_id is only placed on the id and nin fields of the outputs. In the collapsing process of a gate architecture, a wait statement delays fault calculation and reporting by (gate_id * 1 FS). This process needs information provided on the input and output ports and provides fault reports using rules described in the previous section. After faults are reported, the process is suspended.

6 . An ALU Example

Using our fault collapsing models, gate level circuit of a 74LS181 four bit ALU was analyzed. The main body of the ALU model is simply an instantiation list, a portion of which is shown in Figure 15.

...
G108: and2   GENERIC MAP(108) PORT MAP(y(5),y(3),y(9));
G109: or2    GENERIC MAP(109) PORT MAP(y(6),y(7),y(8));
G110: nor2   GENERIC MAP(110) PORT MAP(y(10),y(9),y(11));
G111: nor2   GENERIC MAP(111) PORT MAP(y(8),y(2),y(12));
G112: not1   GENERIC MAP(112) PORT MAP(z(1),z(3));

This circuit has 121 components consisting of NAND, NOR, PI and PO structures. For fault collapsing this architecture is instantiated in a test bench and a report file is generated. The simulation ceases after all gates report faults that remain on their ports after fault collapsing. Figure 16 shows a partial report generated for this circuit. A total of 288 faults were reported, while the number of original uncollapsed faults was 426. This is a 30% reduction in a circuit that contains a relatively high number of fanouts.

TYPE.GATE ID [     SINGLE STUCK FAULT (SSF)  LIST       ]
...
AND2( 108  ) [ I1:none      ;I2:sa_1      ;O1:sa_1      ]
OR2 ( 109  ) [ I1:none      ;I2:none      ;O1:sa_0      ]
NOR2( 110  ) [ I1:none      ;I2:none      ;O1:sa_1      ]
NOR2( 111  ) [ I1:none      ;I2:sa_0      ;O1:sa_1      ]
NOT ( 112  ) [ O:sa_1,sa_0 ]
...
...

[1] P. Goel. " Test generation costs analysis and projections." in Proc. DAC-17. 17th IEEE ACM Design Automation. Conf. . June 1980, pp. 77-84.

[2] J. A. Abraham, "Fault Modeling in VLSI," in VLSI Testing, ed. T. W. Williams, North Holland, Amsterdam, The Netherlands, 1986.

[3] E. J. McCluskey and F. W. Clegg, "Fault Equivalence in Combinational Logic Networks," IEEE Trans. Computers, Vol. C-20, pp. 1286-1293, November 1971.

[4] D. R. Schertz and G. Metze, " A New Representation for Faults in Combinational Digital Circuits," IEEE Trans. Computers, Vol. C-21, pp. 858-866, August 1972.

[5] K. To. "Fault folding for irredundant and redundant combinational circuits."IEEE Trans. Comput., Vol . C-22, no. 11.pp.1008-1015, Nov. 1973.

[6] Z. Navabi, VHDL: Analysis and Modeling of Digital Systems, McGraw Hill, New York, 1993.

[7] Z. Navabi, N. Cooray and R. Liyanage. " Using VHDL in parallel fault simulation " proc. scs., International Conference on Simulation in Engineering Education. January 17-20, 1993,Vol . C-25, no. 3.pp.198-203.