Recursive Optimization of Digital Circuits
Abstract
The goal of this thesis is twofold: first, to identify the advantages and disadvantages of existing optimization systems and second, to develop an optimization system that uses Boolean principles to generate a recursive realization of combinational logic. Current multi-level optimization systems fall into two categories: local optimization which removes redundancy by pattern matching on a local scale and global optimization which works with the equations that specify a circuit rather than with the circuit implementation itself. While global systems are very flexible and can produce near-optimal solutions, they are inherently complex. This research effort demonstrates that an effective global optimization system can be built upon sound Boolean principles. A recursive optimization system built in scheme was thoroughly evaluated. The system achieved gate-input reductions as high as 52 percent. Subsequent modifications targeted improving the system's speed and effectiveness. As a result of these efforts, the optimization speed for a variety of sample specifications was doubled. Other findings led to a better understanding of this approach and showed that it is a technique for the optimization of digital circuits.
Document Details
- Document Type
- Technical Report
- Publication Date
- Dec 14, 1990
- Accession Number
- ADA230778
Entities
People
- John Knutson
Organizations
- Air Force Institute of Technology