Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

# Preanalysis for the Full Range Cutting Algorithm

IP.com Disclosure Number: IPCOM000044369D
Original Publication Date: 1984-Dec-01
Included in the Prior Art Database: 2005-Feb-05
Document File: 3 page(s) / 40K

IBM

## Related People

Gupta, V: AUTHOR [+2]

## Abstract

This article describes a technique which may be used to collect the information necessary to perform the full range cutting algorithm. The cutting algorithm is a means of bounding the signal probability and detection probability of faults in a combinational circuit. It allows an early identification of "hard to detect faults", and indicates where a circuit modification is required in order to meet a given test quality specification. There are two versions of the cutting algorithm: the full range, and the partial range. The difference between the two is that the full range is using intervals of [0,1], while the partial range is using shorter intervals. In order to perform the full range cutting algorithm, we have to collect the following information: (1) Identify the tree, and nontree lines.

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 47% of the total text.

Page 1 of 3

Preanalysis for the Full Range Cutting Algorithm

This article describes a technique which may be used to collect the information necessary to perform the full range cutting algorithm. The cutting algorithm is a means of bounding the signal probability and detection probability of faults in a combinational circuit. It allows an early identification of "hard to detect faults", and indicates where a circuit modification is required in order to meet a given test quality specification. There are two versions of the cutting algorithm: the full range, and the partial range. The difference between the two is that the full range is using intervals of [0,1], while the partial range is using shorter intervals. In order to perform the full range cutting algorithm, we have to collect the following information: (1) Identify the tree, and nontree lines. (2) Identify the fanout branches that are cut candidates. (3) Find the optimal cut, or nearly optimal cut. As indicated by this title, the identification of all these items is done by the same algorithm. Since the collection of tree lines and nontree lines constitutes the set of all possible lines in the circuit, it is only necessary to identify one of them. Thus, the procedure we describe will identify the nontree lines. A line which is not marked as a nontree line is, therefore, a tree line. To illustrate the algorithm, consider the circuit of the figure. All the lines in the circuit have been numbered. The algorithm calls for propagating tokens from each individual fanout stem to the primary outputs. Line 1 is a fanout stem, whose fanout branches are lines 7, 8, 9 and 10. The tokens T1, T2, T3 and T4 have been assigned to the above fanout branches. These tokens are now propagated through the network until the primary outputs are reached. The propagation operation is a union over the tokens that were collected at the block's inputs. For example, the set of tokens collected on line 42 is a union of the sets collected on its input lines 21, 32, and 33.

A line with multiple tokens assigned to it constitutes a nontree line. Thus, the process of the fanout stem 1 has revealed that lines 27, 30, 31, 32, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47 and 48 are all nontree lines. Since these algorithm steps have to be repeated for each fanout stem, all the other nontree lines, which are not discovered by the first processing, will be discovered later. The algorithm also identified the cut candidates. Fanout stem 1 splits into 4 fanout branches: lines 7, 8, 9, and 10. It is always possible to get by with a maximal cut - pattern which constitutes cutting all the fanout branches, except for one. In the case of fanout stem number 1, it would have been possible to get by with 3 cuts. However, by looking at the group of tokens collected at the primary outputs it is possible to achieve a better cut, which will lead to computation of tighter bounds. Consider the group of tokens collected at primary output line 46...