Published In

VLSI Design

Document Type

Article

Publication Date

2002

Subjects

Logic synthesis, Logic circuits -- Design and construction

Abstract

A compact data representation, in which the typically required operations are performed rapidly, and effective and efficient algorithms that work on these representations are the essential elements of a successful CAD tool. The objective of this paper is to present a new data representation—term trees (TTs)—and to discuss its application for an effective and efficient structural automatic test-pattern generation (ATPG). Term trees are decision diagrams similar to BDDs that are particularly suitable for structure representation of AND–OR and AND–EXOR circuits. In the paper, a flexible algorithm for minimum term-tree construction is discussed and an effective and efficient algorithm for ATPG for AND–EXOR and AND–OR circuits is proposed. The term trees can be used for many other purposes in logic design and in other areas—for all purposes where compact representation and efficient manipulation of term sets is important. The presented experimental results show that term trees are indeed a compact data representation allowing fast manipulations. They form a good base for algorithms considering the function’s and circuit’s term structures.

Description

This is the publisher's final PDF. Copyright © 2002 Hindawi Publishing Corporation. This is an open access article distributed under theCreative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited. Version of record can be found at: http://dx.doi.org/10.1080/10655140290009837

DOI

10.1080/10655140290009837

Persistent Identifier

http://archives.pdx.edu/ds/psu/12969

Download

Share

COinS