Browse Prior Art Database

# Restricted Range Cutting Algorithm

IP.com Disclosure Number: IPCOM000047138D
Original Publication Date: 1983-Sep-01
Included in the Prior Art Database: 2005-Feb-07
Document File: 4 page(s) / 65K

IBM

## Related People

Ditlow, G: AUTHOR [+2]

## Abstract

This publication describes how to take advantage of the inversion parity of the reconvergent fanout branches to compute tighter bounds of signal probabilities in the use of cutting algorithms for circuit design test. It is shown that in some cases it is possible to assign one of the ranges (0,g) or (g,1) to the cut fanout branch, where g is the signal probability of the stem of the fanout. If g is in itself a range (P,u), then one of the ranges (0,u) or (P,1) will be assigned. Theorem 1: te fanout stem with signal probability g, from which only one pair of reconverging paths emanates. Let this pair of reconverging paths be the only one in the network. Let H be the gate through which the pair of paths reconverges. Let h be the output of this gate.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 45% of the total text.

Page 1 of 4

Restricted Range Cutting Algorithm

This publication describes how to take advantage of the inversion parity of the reconvergent fanout branches to compute tighter bounds of signal probabilities in the use of cutting algorithms for circuit design test. It is shown that in some cases it is possible to assign one of the ranges (0,g) or (g,1) to the cut fanout branch, where g is the signal probability of the stem of the fanout. If g is in itself a range (P,u), then one of the ranges (0,u) or (P,1) will be assigned. Theorem 1: te fanout stem with signal probability g, from which only one pair of reconverging paths emanates. Let this pair of reconverging paths be the only one in the network. Let H be the gate through which the pair of paths reconverges. Let h be the output of this gate. Then, if a fanout branch is cut and assigned a range according to the appropriate case of Table 1, all the signal probability ranges computed on the resultant tree will include the true values. Before the Theorem 1 is proven, first consider the following example: Example 1: Consider the circuit of Fig. 1. The two paths emanating at w and reconverging at h have unequal inversion parities, and the type of the reconverging gate is a NOR. Suppose it is desired to cut the upper path, which has an odd parity between w and h. According to Table 1 below, the assigned range should be (3/4,1). The signal probability ranges computed for the resultant tree are shown in Fig. 1. Proof of Theorem 1: Proof of one of the entries of Table 1 is provided hereinbelow.

The proof for the rest is similar. Proof is provided for the case where both paths have even parity and where the reconverging gate is an AND. Table 1: The restricted ranges assigned to a cut fanout branch as a function of type of reconverging gate, the path inversion parity, and the signal probability of the stem. It is necessary to show that a range of (g,1) for the cut branch will yield true bounds on all other lines in the circuit. Because of the assumptions imposed in the Theorem, it is sufficient to prove that the signal probability range computed for line h includes the true value. The Boolean function of h expressed in terms of g can be written as: h = (A1g + B1) (A2g + B2) where g is independent of A1, B1, A2, B2. If the first fanout branch is cut and assigned a primary input x, then the function realized by h expressed in terms of x and g is: h* = (A1x + B1) (A2g + B2). The question now is what should ps(x) be so that ps(h) = ps(h*). (Ps is the signal probability.) (3) The steps of the restricted range cutting algorithm is spelled out in the following procedure. Procedure: Step 1 - Assign a signal probability of 1/2 to all input lines, and compute the signal probabilities of all the tree lines. Step 2 - Moving from the inputs towards the outputs, cut reconvergent fanout branches to turn the circuit into a tree. When a fanout branch is cut, assign to it a restricted range, if all reconverging pairs of...