1. Fast Exact NPN Classification by Co-Designing Canonical Form and Its Computation Algorithm.
- Author
-
Zhou, Xuegong, Wang, Lingli, and Mishchenko, Alan
- Subjects
- *
ALGORITHMS , *LOGIC design , *BOOLEAN functions , *CLASSIFICATION , *APPROXIMATION algorithms - Abstract
NPN classification of Boolean functions is a powerful technique used in many practical applications, including logic synthesis, technology mapping, architecture exploration, circuit restructuring, and approximate logic synthesis. Computing the canonical form of a function is the most common approach to NPN classification. Exact classification of practical functions is an open problem because there are difficult functions beyond the capability of the state-of-the-art exact algorithms, which may take several months to compute a canonical form. This article proposes a new approach to exact NPN classification, in which a series of canonical forms and the algorithms to compute them are designed together. As a result, the runtime of the exact classification for difficult functions is effectively controlled by making both representation and computation cost-aware. Experimental results show that the proposed algorithm can perform exact classification of the worst-case 16-input functions in less than 3 minutes. This indicates that, for the first time, the problem of exact classification can be effectively solved for any Boolean functions with up to 16 inputs arising in practical applications. [ABSTRACT FROM AUTHOR]
- Published
- 2020
- Full Text
- View/download PDF