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

# Algorithm for Fast Determination of Paths in a Logic Circuit

IP.com Disclosure Number: IPCOM000100399D
Original Publication Date: 1990-Apr-01
Included in the Prior Art Database: 2005-Mar-15
Document File: 6 page(s) / 158K

IBM

## Related People

Shearon, PC: AUTHOR

## Abstract

This algorithm for fast determination of paths in a logic circuit, when used in the test generator ETG, provided more efficient test generation in terms of increased test coverage and reduced running time. Its advantage is that it not only leads to more efficient test generation, but is itself fast. The following is a definition of terms: Path: A come from block trace. End block: The last block in a path. Begin block: A block in a path (loop) which is the same as the end block. Root: A group of paths having a common begin block. Root block: The first block in a root. Prune: Remove from a path. Prune block: A block which is a PI or has all its inputs pruned.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 52% of the total text.

Algorithm for Fast Determination of Paths in a Logic Circuit

This algorithm for fast determination of paths in a logic
circuit, when used in the test generator ETG, provided more efficient
test generation in terms of increased test coverage and reduced
running time.  Its advantage is that it not only leads to more
efficient test generation, but is itself fast.  The following is a
definition of terms:
Path:               A come from block trace.
End block:          The last block in a path.
Begin block:        A block in a path (loop) which is the
same as the end block.
Root:               A group of paths having a common begin block.
Root block:         The first block in a root.
Prune:              Remove from a path.
Prune block:        A block which is a PI or has all its inputs
pruned.

A flag (PBFLAG) in a table which is one to one with the blocks
is set to mark the block as a prune block.
Prune block input:  A block input which is fed by a prune block.  A
flag (PBIFLAG) in a table which is one to one with the block inputs
is set to mark the input as a prune block input. The PCFP(n) in the
path list is set "PRUNED" to mark the input as a prune block input
for a particular path.
Prune root:         A root where all paths terminate with an end
block whose begin block is in the root.
The following are new features contained in the algorithm:
1.  Roots are pruned to reduce repeated tracing of the same paths
in PRUNE ROOT.
2.  Blocks and block inputs are marked "prune block" and "prune
block input" to terminate the tracing of a path in MARK PRUNE BLOCK
INPUTS AND PRUNE BLOCKS.
3.  The input of a block in a...