Multi-level logic minimization through fault dictionary analysis

Abstract

This thesis presents the results of the study of a new ics. algorithm for multi-level logic minimization. This study is based upon the premises that an investable node is a redundant node and that nodes that do not demonstrably cause conflicting behavior at primary outputs may be compatible. Using fault simulation data, compatible nodes are identified and merged. While offering some improvement, this technique by itself leaves many potential reductions undiscovered. As has been noted in (1), adding wires may allow more gated to be eliminated. Using similar fault data to those used to identify compatible bates, implied gate functions are identified and injected. The addition of these new implicant functions creates more compatible pairs, which in some cases can then be eliminated. Data gathered using these techniques show that matrix analysis is a powerful tool that produces minimization results in selected benchmark circuits superior to any previously published academic work. The algorithm developed in this study, Texas Aggies Logic Optimizing Netlister (TALON), is shown to be competitive with, and complimentary to, other methodologies. TALON can be used by itself to reduce the size of a logic network, or it can be used as a preprocessor or postprocessor for other tools, giving superior results to those obtained by any of them working independently.