A Fast Method to Derive Minimum SOPs for Decomposable Functions
Abstract
This paper shows that divide-and-conquer derives a minimum sum-of-products expression (MSOP) of functions that have an AND bi-decomposition when at least one of the subfunctions is orthodox. This extends a previous result showing that divide-and-conquer derives the MSOP of the AND bidecomposition of two orthodox functions. We show that divide-and- conquer does not always produce an MSOP when neither function is orthodox. However, our experimental results show that, in this case, it derives a near minimal SOP. At the same time, our approach significantly reduces the time needed to find an MSOP or near minimal SOP. Also, we extend our results to functions that have a tri-decomposition.
Document Details
- Document Type
- Technical Report
- Publication Date
- Jan 01, 2004
- Accession Number
- ADA605403
Entities
People
- Jon T. Butler
- Tsutomu Sasao
Organizations
- Naval Postgraduate School