See discussions, stats, and author profiles for this publication at: https://www.researchgate.

net/publication/257947095

Implementation of Algorithm For Testability Measures Using MATLAB

Conference Paper · October 2008

CITATIONS READS
0 1,338

3 authors:

Usha Mehta Nirnjan M. Devashrayee

Nirma University Nirma University
43 PUBLICATIONS   166 CITATIONS    72 PUBLICATIONS   292 CITATIONS   

SEE PROFILE SEE PROFILE

Kankar S Dasgupta
Dhirubhai Ambani Institute of Information and Communication Technology
112 PUBLICATIONS   795 CITATIONS   

SEE PROFILE

Some of the authors of this publication are also working on these related projects:

"Development of Radiation hardened Polymer composites". This material is developed to withstand high frequency cosmic radiation especially for electronics devices used
in space craft and other such applications. View project

Project on X ray imaging View project

All content following this page was uploaded by Usha Mehta on 21 May 2014.

The user has requested enhancement of the downloaded file.

 Implementation of Algorithm
For Testability Measures Using MATLAB
Prof. Usha Mehta * Dr. N. M. Devashrayee** Dr. K. S. Dasgupta***

Research Scolar (VLSI Design), Nirma University, Ahmedabad : [email protected], [email protected]

**PG Coordinator (VLSI Design), Nirma University, Ahmedabad Email : [email protected]
*** Deputy Director, SAC, ISRO, Ahmedabad Email : [email protected]

Abstract— Increase in transistor density has a great impact on can be observed that the number of possible paths that the test
testing as well as design. In worst case, test complexity increases generator must examine, in order to compute a test pattern,
exponentially with number of transistors and number of flipflops. increases exponentially with the number of nodes of the
The amount of data and complexity of data generation required circuit, i.e. the number of gates [4,5].
to test ICs is growing rapidly in each new generation of
technology. The testing of any circuit is based on two specific
This paper describes a procedure that can be used to estimate
tasks : to set a particular net to a specific value ( to control the
net) and to observe the value available on a particular net( to the testability of the nodes of a combinational circuit [6-81; an
observe the net). Depending upon the type of net, the types of existing ATPG procedure [9] uses the algorithm as a pre-
components connected to the net and the level of the net, the processing step in order to improve its performance; in fact, as
effort needed to control the net or to observe the net varies. In proved in [2], searching test patterns using the nodes of the
such era, the search process of any Test Generation algorithms circuit having the highest testability insures the reduction of
involved with the combinational automatic test pattern the test generation time, and guarantees the computation of a
generation involves two important decisions. The first one being better quality test set.
to select one of the several unsolved problems existing at a certain
stage in the execution of the algorithm . The second type is to
The rest of this paper is organized as follows. Section 2
select one possible way to solve the selected problem. Selection
criteria differ mainly by the cost functions they are used to describes the motivation behind developing testing measures
measure “difficulty’. This paper describes a technique to estimate algorithm, Section 3 introduces the circuit representation that
the testability of the nets of a combinational circuit, whose has been used. Section 4 formally defines the testability
description can be either at the gate-level. Three weight measures, section 5 gives the implementation steps for their
functions, CC0( combinational controllability 0), CC1( computation. Section 6 illustrates how these measures can be
combinational controllability 1) and CO ( combinational determined on a practical example. Section 7 shows the
observability ) are evaluated for each net of the network, and the benefits, in terms of test generation time, produced by the
results obtained are employed in an existing ATPG procedures in application of the testability measures to the test generator
order to reduce the test generation time. Experimental results
described in [9]. Finally, Section 8 is devoted to conclusions.
obtained on the ISCAS’ 85 benchmark circuits show the
effectiveness of the method.
II MOTIVATION
I. INTRODUCTION
The amount of data and complexity of data generation
The study and the implementation of efficient algorithms for required to test ICs is growing rapidly in each new generation
integrated circuits testing becomes every day more difficult of technology. The combinational automatic test pattern
because of the large number of logic gates that can be packed generator (ATPG) is the main building block of any testing
together on a single silicon wafer [1,2]. tool. The automatic test pattern generator for combinational
design is of the most importance because after scan chain
An automatic test pattern generation (ATPG) program is a insertion, any of sequential testing will also use the
computer aided design (CAD) tool that, given a fault in the combinational ATPG for a given state of sequential circuit. So
circuit under test, calculates the sequence of input vectors (i.e. it may be said that the combinational ATPG is the backbone of
the test pattern) that has to be applied to the circuit in order to today’s testing tool. The testing of any circuit is based on two
detect the fault. Given the location of the fault, the procedure specific tasks. 1. To set a particular net (either primary input
starts investigating all possible paths of the network that allow or any internal net to a particular value) 2. To observe the
its propagation through the circuit, until its symptoms can be value on a particular net (i.e. either primary output or any
observed on a primary output (forward propagation); then, it internal net). Depending upon the type of net, the types of
computes the input vectors required to satisfy all the components connected to the net and the level of the net ( i.e
conditions imposed on the internal nodes of the network place : how far it is from the primary input or output ) the
during the propagation phase (backward justification) [3]. It effort needed to set that net or to observe that net varies. In
such era, the search process of any Test Generation(TG) In this section we discuss the format of the circuit
algorithms involved with the combinational ATPG involves specification that we input to the program which calculates the
two important decisions. The first one being to select one of testability measures of the circuit. In particular, we focus our
the several unsolved problems existing at a certain stage in the attention on circuit description
execution of the algorithm . The second type is to select one The topological description of the combinational network under
possible way to solve the selected problem. Selection criteria consideration is gate –level.
differ mainly by the cost functions they are used to measure Any ATPG tool takes the Design Under Test (DUT) as an
“difficulty’. Typically cost functions are of two types: input and generate the test vector for given fault in the DUT.
1. Controllability - For a digital circuit it is defined as Most of the ATPG tool accepts DUT as an input in form of
the difficulty of setting a particular logic signal to netlist (text file) and by processing on netlist; it generates the
state 0 or 1. fault directory which will contain the fault and its
2. Observability - For a digital circuit it is defined as the corresponding test vector. Considering the same concept, for
difficulty of observing the state of a logic signal . testability algorithm implementation also the input is required
Controllability measures can be used both to select the most in the standard format for netlist. A set of standard benchmark
difficult line-justification problem , and then to select among type circuit set on which the results can be proved was also
the unspecified inputs of G the one that it is easiest to set to required. For both of these reasons, ISCAS 85 (International
the controlling value of the gate. Observability measures can Symposium for Circuits and Systems) combinational circuits
be used to select the gate from the D-frontier whose input and netlist format were quite adequate so the ISCAS85 format
error is the easiest to observe. Goldstein was the first one to is used as an input netlist format.
implement a computer program to calculate those
controllability and observability values which he named as IV TESTABILITY MEASURES
SCOAP acronym for Sandia Controllability and Observability
Analysis Program. An attempt to quantify testability by Goldstein ’79 and Grason
’79 resulted in two testability measures, controllability and
The testing system consists of two basic tasks 1. Test observability. Controllability is defined as the difficulty of
Generation 2. Fault Simulation. setting a particular logic signal to a 0 or a 1. PIs are free
To reduce the cost and complexity of test pattern generation, (usually assigned a value of 1). Output 1 values for AND gates
the following goals should be achieved. are more expensive than OR gates.
1. to increase the fault coverage Observability defined as the difficulty of observing the state of
2. to reduce the overall efforts (CPU time) a logic signal. Purpose to define such terms are :
3. to reduce the number of test vectors required ( to 1. Analysis of difficulty of testing internal circuit nodes
reduce the test application time) 2. May need to modify circuit, add observation points or
To reduce the cost and complexity of fault simulation, the test hardware
following goals should be achieved 3. Can be used to guide ATPG algorithms, i.e., to help
1. to reduce the fault list them make decisions by providing information about
2. to use efficient and diverse fault simulation methods the difficulty of setting lines.
3. to use efficienf fault sampling methods 4. Can be used to estimate fault coverage
The testability measures is a powerful heuristic used during 5. Can be used to estimate test vector length.
test generation which will show its effect on fault simulation Testability analysis attributes requires topological analysis
also. (but no test vectors). It should be linear in complexity
The testability measures are useful in following ways. otherwise it’s pointless, i.e., might as well use ATPG to
• In ATPG during backtracing (controllabilities) and compute exact fault coverage.
propagating the fault effect (observabilites) since they • Controllability: From 1 (easiest) to infinity (hardest).
give the path of least resistance. Some caution is • Observability: From 0 (easiest) to infinity (hardest).
necessary since reconvergent fanout introduce error in Combinational measures are related to the number of signals
controllabilites and fanout stems introduce error in that may be manipulated to control or observe l.
observabilities. This method consists of 3 numerical measures for each signal
• It tells designer which parts of the design are extremely (l) in the circuit:
hard-to-test. Either redesign or special-purpose test • Combin. 0-controllability, CC0(l)
hardware is needed to achieve high fault coverage. • Combin. 1-controllability, CC1(l)
• Extremely useful for estimating fault coverage and test • Combin. observability, CO(l)
vector length. Fault coverage estimation via testability
can reduce CPU time by orders of magnitude over fault Controllabilities:
simulation (and has only a 3-5% error).
The basic process: Set PIs to 1, progress from PIs to POs, add
III CIRCUIT FORMAT 1 to account for logic depth.
In general, if only one input sets gate’s output:
output controllability = min(input controllabilites) + 1
If all inputs set gate output:
output controllability = sum(input controllabilities) + 1
If gate output is determined by multiple input sets, e.g., XOR:
output controllability = min(controllabilities of input sets) + 1
For the fanouts the controllability values remain to be same as
for the line from which it is emerging. Details are given in
figure 2.1

Figure 2 Observability Measures

Observabilities:
The basic process for observability is started after The accuracy problem occurs for the computation of the
controllabilities computed, set P0s to 0, progress from PO to observability of a fanout stem with n branches. One attempt is
PIs, add 1 to account for logic depth. to bound the stem probability by: • min(all fanout branch
For example, the difficulty of observing a designated input to observabilities) The events of observing a signal through each
a gate is the sum of (1) the output observability (2) the branch are independent. • max(all fanout branch
difficulty of setting all other inputs to non-dominant values (3) observabilities) They are all dependent, therefore branch that’s
plus 1 for logic depth. Further details are given in figure 2.2 hardest to observe is correct choice.
For our implementation, the first option is chosen.

V IMPLEMENTATION

This testability_tool accepts the DUT in ISCAS85 netlist

format text file and generates the combinational controllability
0(CC0), combinational controllability 1(CC1) and
combinational observability (CO) for each of the nets in given
circuit. It stores results in controlobserv.txt file which file
further can be used as a part of ATPG tool.

The main requirement here was linear computational

complexity otherwise it is pointless – might as well use
automatic test-pattern generation and calculate exact fault
coverage exact test vectors and So the results of controllability
are derived by computing first the controllability of each node
and then using it, observability is derived so this code is linear
in computational complexity.

Figure 1 Controllability Measures Following steps describes the algorithm implementation.

1: Open the netlist file which is in text format.

2: Assign each column of netlist to corresponding array
i) Array 1 : net number
ii) Array 2 : gat
iii) Array 3 :type of net (inpt, nor, nand, od, nor,
from)
iv) Array 4 : total fan out from that net
v) Array 5 : total fan in to that net ( if net is gate
output then inputs to gate is fan in to that net)
vi) Array 6 : fan in 1
vii) Array 7 : fan in 2
3: Initialize the arrays for 1. controllability 0 (c_0) 2.
controllability 1 (c_1) 3. Observability (observ) of
length equal to total number of net in circuit. All the
element of c_0 and c_1 is assigned value 0 and all the
elements of observ are assigned with -1. As
controllability can be any value out of [1, α ) and
value of observability can be [0, α ), the logic here is
 to assign value which is an unvalid or not possible 20: Find c_o and c_1 for second input to gate using its
value for that function. index.
Starting calculation for controllability 21: Find the observability for output from gate using its
4: Set element of c_0 and c_1 corresponding to primary index and observ array.
input to value 1 22: If observability of output from gate is not -1, it is a
5: Now we will start to count value for other nets by valid observability. Calculate the observability for net
calling controllability fuction for each of the net in under consideration using following rule.
array 1. For ‘and’ gate : observ(e)=
Controllability function observ(output_index)+ c_1_second_ip +1;
6: If current net is an input , already c_0 and c_1 is set. For ‘nand’ gate : observ(e)=
7: If it is not an input, it is output from the gate or observ(output_index)+ c_1_second_ip +1;
branch from a stem For ‘or’ gate : observ(e)=
8: If it is branch of the stem, as the branch has the same observ(output_index)+ c_0_second_ip +1;
controllability values as stem, find its stem from For ‘nor’ gate : observ(e)=
array 3 and index of stem in array 1 and observ(output_index)+ c_0_second_ip +1;
corresponding element value from c_0 and c_1. If 23: If given net is a stem, find its branches and
this values are non zero, assign this value at index corresponding index.
for given stem in c_0 and c_1 respectively. 24: Find the observabilities for both the branches
9: If given net is output from some gate, find the type 25: Assign minimum observability out of the two
of gate from array 3 (like nor, nand, or, and), number observabilities for branches to stem.
of fan ins to this gate from array 4 and name of fan 26: Make an array from observ which has element values
ins from array 6 and 7( let’s call it fan1 and fan2). more than -1. If the length of this array is equal to
10: Find out the index of fan1 and fan2 from aray1 and total number of net, all valid observabilities has set
corresponding element from c_0 and c_1 each for else repeat the loop.
fan1 and fan2. (let’s call it c1_0, c1_1, c2_0, c2_2)
11: Apply following rules to calculate the c_0 and c_1 of VI AN APPLICATION EXAMPLE
current net. As an application example of the proposed technique, let us
12: If c1_0 and c2_0 are non zero, consider the circuit C17. It is the smallest circuit in the ISCAS
For 'and' c_0(e)=min(c1_0, c2_0) +1; ‘85 [lo] set, and its schematic is shown in Fig. 3. Notice that
For 'nand' c_1(e)=min(c1_0, c2_0) +1; the S27 description contains both gate and block elements. By
For 'or' c_0(e)= c1_0 + c2_0 +1; applying the COs and 00s
For 'nor' c_1(e)= c1_0 + c2_0 +1;
13: If c1_1 and c2_1 are non zero,
For 'and' c_1(e)= c1_1 + c2_1 +1;
For 'nand' c_0(e)= c1_1 + c2_1 +1;
For 'or' c_1(e)= min(c1_1, c2_1) +1;
For 'nor' c_0(e)= min(c1_1, c2_1) +1;

14: Make the array of elements of c_0 and c_1 with

nonzero values. If the length of this array is same as
length of total number of net than, all the net is
considered for c_0 and c_1. If not then repeat until
both arrays have same length.
Observability Figure 3 ISCAS’85 Benchmark Circuit C17
15: For elements of array 1 which are primary output, set
corresponding element of observ to 0 value. CC0(10)=CC1(1)+CC1(8)+1= 3
16: for each of the member of array 1 , call the function CC1(10)=min(CC0(1),CC0(8))+1= 2
observability CC0(11)=CC1(9)+CC1(6)+1= 3
Observability function CC1(11)=min(CC0(9),CC0(6))+1= 2
17: find the index of net for which observability is being CC0(16)=CC1(9)+CC1(6)+1= 4
calculated CC1(16)=min(CC0(9),CC0(6))+1= 2
18: If given net is not a primary output or stem, it should CC0(19)=CC1(15)+CC1(7)+1= 4
be input to a gate. Find out the type of that gate, CC1(19)=min(CC0(15),CC0(7))+1= 2
second input to that gate and fan out net from that CC0(22)=CC1(10)+CC1(20)+1= 5
gate. CC1(22)=min(CC0(10),CC0(20))+1= 4
19: Find the index for fan out net from gate, and index CC0(23)=CC1(21)+CC1(19)+1= 5
for second input to that gate. CC1(23)=min(CC0(21),CC0(19))+1= 5
 Figure 4 The calculated Controllabilities for each net in C17.

VII RESULTS

The above implementation is done using MATLAB 7.0 VI FUTURE SCOPE

software. The implementation is tested using ISCAS85 The assumption of signal independence is the key behind this
benchmark circuits and other higher order circuits. The values linear time algorithm. However, this reduces its accuracy in
obtained by tool are perfectly matching with calculated values predicting which individual faults will remain undetected and
in all the case. which will be detected. So for higher complex circuits,
Only two cases are given below for demonstration view. predictive controllability concepts can be used.
1. For ISCAC85 C17 circuit
VII REFERENCES
[1] H. Fujiwara, Logic Testing and Design for Tesfability. MIT Press, Mass.
(1985).
[2] M. Abramovici, M. A. Breuer and A. D. Friedman, Digital Systems Testing
and Testable Design. Computer Science Press (1990).
[3] G. R. Putzolu and J. P. Roth, A heuristic algorithm for the testing of
asynchronous circuits. IEEE Trans. Computers C-20, 639-647 (1971).
[4] M. A. Breuer and A. D. Friedman, Diagnosis and Reliable Design of Digital
Circuits. Computer Science Press (1976).
[5] A. Miczo, The sequential ATPG: a theoretical limit. ITC-83: IEEE
International Test Conference, pp. 143-147 (1983).
[6] L. H. Goldstein, Controllability/observability analysis of digital circuits.
IEEE Trans. Circuits Systems CAS26, 685493 (1979).
[7]J. Grason, TMEAS-a testability measurement program. DAC-16: 16th IEEE
Design Automarion Conference, pp. 156-161 (1979).
[8] J. E. Stephenson and J. Grason, A testability measure for register transfer
level digital circuits. FTCS-6: 6th IEEE International Symposium on Fault-
Tolerant Compuling, pp. 101-107 (1976).
[9] E. Macii and A. R. Meo, Algebraic/topological combined strategies for
sequential ATPG. 25th IEEE AsilomarConference on Signals, Systems and
Computers, pp. 1240-1244 (1991).
[10] F. Brglez, D. Bryan and K. Kozminski, Combinational profiles of
sequential benchmark circuits. ISCAS ‘89: IEEE
International Symposium on Circuifs and Systems, pp. 1929-1934 (1989).
[11] Micahel L. Bushnell, Vishwani D. Agrawal, Essentials of electronic
testing for digital, memory and mixed signal VLSI circuits, Kluwer Academics
Publishers, 2002.
[12] L.H. Goldstein & Evelyn .L.Thigpen, SCOAP : SANDIA
Controllability/Observability analysis program,SANDIA national laboratories
[13] L.H. Goldstein, Controllability/Observability analysis of digital circuits,
Cande workshop, Mt. Hood Oregon (1978)
[14] David Bryan, ISCAS’85 benchmark circuits and netlist format, North
Carolina State University
[15] http://iwls.org/iwls2005/benchmarks.html
[16] http://www.eecs.umich.edu/~jhayes/iscas.restore/benchmark.html
[17] http://www.cerc.utexas.edu/itc99-benchmarks/itsw.bench.pdf

View publication stats