A Testability Measure.
Stephen Louis Kessler · 1983
This thesis presents the current status of an algorithm which is used to calculate how testable a digital circuit is. The algorithm, or testability measure, is easier than calculating the entire test set. The algorithm calculates controllability and observability figures for each and every node in a given combinational or sequential circuit. These figures are approximations to the actual amount of time, and fraction of total input combinations which are needed to control and observe a given circuit node. Algorithm results can be compared to benchmark figures to determine their accuracy. Testability measure results are shown to be exact for fanout-free combinational circuits and feedback-free shift register circuits which are made using D flip-flops. Poor results are found to occur among the observability figures for stem fanout nodes, which showed up most noticably in multiple level parity trees. Chapter 1 TM Fundamentals 1.0 Introduction In this thesis we present a testability measure, abbreviated TM. The testability measure is an algorithm which works from a digital circuit at the gate and flip-flop level to produce a metric for each lead, or node in the given circuit. Testability measure results can be used to determine how testable the given circuit is. A small result, or figure, indicates that a node is difficult to test, while conversely, easily tested nodes have large figures. This chapter contains the background information that is necessary to be able to use the TM. The following section defines the applicability of the testability measure. The algorithm's objectives are discussed in the third section, Section 1.2. In the next section we define the terms that are used in this thesis. The last section contains an overview of the algorithm. A flow chart is included to add clarity to the discussion. The remaining chapters contain details of the TM calculations and the performance of the algorithm. Chapter 2 presents details of the algorithm calculations. In Chapter 3 we show how to calculate exact testability 2 figures and thus judge their accuracy. The TM's major strong and weak points are discussed in Chapter 4. The last chapter, Chapter 5, contains our concluding remarks on the algorithm and our ideas concerning future research. 1.1 Scope of the TM Algorithm TM calculations are performed on digital circuits. The permitted class of circuits includes combinational circuits and clocked sequential logic networks. The algorithm has been formulated to operate only on circuits with a single output, so that multiple outputs must be treated as an array of single outputs. Redundant networks (circuits which contain excessive logic) and asynchronous circuits are not included in the permitted class of circuits. The permitted combinational logic gates include And, Or, Nand, Nor gates and inverters. Exclusive Or gates must be broken down into a more basic form. D flip-flops and JK flip-flops are the permitted sequential logic elements. For SR flip-flops our algorithms are incomplete. 1.2 Algorithm Objectives The objective of this thesis is to formulate a testability measure that is indicative of testing difficulty. The algorithm must show which portions of a given circuit are hard to test, and which are easy to test. It also must be easier to compute than finding the entire test set. If this were not true, then there would be no advantage in using the TM. And finally, we should be able to compare the testability measure's results to a rigorous measure's results. Thus we want to create a measure which is easy to calculate and has results that are meaningful. A primary feature of our TM is that the results have meaning. They are approximations to exact results in purely combinational networks. In sequential circuits they are approximations to benchmark calculations. The benchmark results, while not exact, do indicate how testable a circuit is. 1.3 Definition of Terms The TM requires that all combinational logic be. level organized. Level organized circuits are set up in the following manner. All primary inputs (PI) will be placed at the left-hand side of the circuit. The first level, the left-most set of gates, have as inputs only Pi's and complemented Pi's. The next level should have as inputs the outputs of the first-level gates, complements of the first level outputs and only complemented or uncomplemented Pi's. A gate, G,, cannot be on the same level with a gate, G„, if the output of G„ is used as an input to G. . Gates can have as inputs onlygate outputs of the previous level(s) and possibly Pi's. Thus a gate at level i must have at least one input from a gate output at level i-1 and can have other inputs which are either Pi's or outputs of gates in level 1, 2,...,i-2. Each possible primary input combination is called N a vector. If there are N Pi's, then there are 2 distinct vectors. The term vector is also associated with sequential circuits. A state vector in a sequential circuit is the set of bits that make up the coding of a M state. A circuit with M flip-flops has 2 different state vectors. The TM generates two figures for each node in a circuit. One of these is the controllability figure, a concept first developed by Goldstein (see Reference (2) ) . Each node has two controllability figures, the onecontrollability and the zero-controllability. The onecontrollability describes the ease, or difficulty, of setting a node to a one. The one-controllability of node x is denoted by C . The zero-controllability of node x, denoted C , describes the difficulty of setting node x to a zero. Control of a lead to a one (zero) is dependent on the fraction of the total number of vectors which set the lead to a one (zero) and on the amount of time that must pass before the node is actually set. To describe these factors the one (zero)-controllability is split into the fractional one (zero)-controllability and the one (zero) time frame number respectively. The time frame number, abbreviated TFN, denotes the number of clock periods, or time frames, which are needed to control a node to a one (zero). The TFN is taken from Kovijanic[4]. In a purely combinational network, for example, the one (zero)-TFN is equal to zero for all nodes because the circuit is unclocked (gate delays are ignored). In Eg. (1-1) we write the one (zero)-controllability of node x as a two-tuple C^ = {A,B} (1-1) where A is the fractional one (zero)-controllability and B is the one (zero)-TFN. The fractional one-and zerocontrollabilities are restricted to the range [0,1]; thus in Eq. (1-1) we have 0 £ A 1 1. (1-2) We must ensure that the fractional controllabilities never exceed these bounds. Any results which are out of bounds are forced back into the permitted range by using Eq. (1-3). If A > 1, then A = 1.0 (1-3) If A 1 -»• F = 1.0 (1-6) F F=0.0 1.4 Overview of the TM Figure 1-1 is a flow chart of the TM algorithm. It highlights the procedure and order of the TM calculations; details are contained in the next chapter. The controllability calculations are performed first and the network is processed level-by-level, proceeding from inputs to outputs. This is another idea which was first formulated by Goldstein in Reference [2]. For sequential circuits with feedback loops we iterate through the levels until the fractional controllability figures converge. Observability calculations are performed second, proceeding from output to input.* We do not iterate the OBS calculations. The remainder of this section is devoted to explaining selected portions of Fig. 1-1. * see Goldstein, Reference [2]