Browse Prior Art Database

Table Generator Test Generation Algorithm

IP.com Disclosure Number: IPCOM000045619D
Original Publication Date: 1983-Apr-01
Included in the Prior Art Database: 2005-Feb-07
Document File: 2 page(s) / 14K

Publishing Venue

IBM

Related People

Butler, RW: AUTHOR [+4]

Abstract

This is a system of algorithms and heuristics designed to provide efficient and effective automatic test generation for VLSI (very large-scale integration) designs. Many test generators are limited to structures of not more than 4000 gates. This test generator can effectively provide full stuck-fault test generation on unpartitioned structures in excess of 30,000 gates.

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

Page 1 of 2

Table Generator Test Generation Algorithm

This is a system of algorithms and heuristics designed to provide efficient and effective automatic test generation for VLSI (very large-scale integration) designs. Many test generators are limited to structures of not more than 4000 gates. This test generator can effectively provide full stuck-fault test generation on unpartitioned structures in excess of 30,000 gates.

This is a totally new approach to test pattern generation that is cost effective on the large LSSD (level sensitive scan design) structures. The algorithm uses a partial truth table in order to generate tests. In the description that follows the table itself is described, followed by the process of building the table, and finally the algorithm for generating a test using the table.

The table is best described as a partial truth table in that for every node (signal) in the circuit the table contains input vectors that will drive that node to a ZERO value and a ONE value. In addition to the ZERO/ONE values, the table also gives input vectors that will sensitize a path from the node to an output of the circuit. The table is "partial". Of the many possible input vectors only a few (typically one or two) are stored in the table for each node. For purposes of the table, inputs to the circuit are considered to be: Primary input pins; L1 and L3 latches; and Array outputs. Outputs (for sensitizing a path to an output) are considered to be: Primary Output Pins; L1, L2 and L3 latches; and Array inputs.

The table is built in a two-pass process. In the first pass, a forward simulation is performed beginning at the inputs and proceeding to the outputs of the circuit. During this pass the input vectors for setting a node to a ONE and ZERO are built and stored. The process is levelized. A block (gate) is simulated (calculated) only when all of its inputs have been simulated. Consider, for example, the calculaton of the ONE entry for the output of an AND circuit. The vectors already in the table) corresponding to ONE at each input to the AND circuit are examined. A compatible set of those vectors is found that will simultaneously achieve a ONE on all inputs to the AND. The composite of those vectors is then stored as the ONE entry for the output of the AND. Depending on available memory and time the table build program can continue searching for multiple entries. Typically, one or two entries are optimum. Since the build algorithm only looks back at one level of...