Fast Exact NPN Classification with Influence-aided Canonical Form
Yonghe Zhang Liwei Ni Jiaxi Zhang Guojie Luo Huawei Li Shenggen Zheng
NPN classification has many applications in the synthesis and verification of
digital circuits. The canonical-form-based method is the most common approach,
designing a canonical form as representative for the NPN equivalence class
first and then computing the transformation function according to the canonical
form. Most works use variable symmetries and several signatures, mainly based
on the cofactor, to simplify the canonical form construction and computation.
This paper describes a novel canonical form and its computation algorithm by
introducing Boolean influence to NPN classification, which is a basic concept
in analysis of Boolean functions. We show that influence is
input-negation-independent, input-permutation-dependent, and has other
structural information than previous signatures for NPN classification.
Therefore, it is a significant ingredient in speeding up NPN classification.
Experimental results prove that influence plays an important role in reducing
the transformation enumeration in computing the canonical form. Compared with
the state-of-the-art algorithm implemented in ABC, our influence-aided
canonical form for exact NPN classification gains up to 5.5x speedup.