Fast Classification Algorithm Of Functions Based On NPN

In the design of digital circuit, as an important procedure, logic synthesis translates the digital circuit description from RTL (Register Transmit Layer) layer to Gate layer. The purpose of logic synthesis is to implement the Boolean function with digital circuit. As a dispensable part of logic synthesis, logic optimization puts weight on area optimization and timing optimization so as to improve the performance of digital circuit. In the process of logic optimization, the Boolean functions must be classified in order to implement equivalent substitution of circuit structure which means to substitute the original structure with the optimized structure without changing the functionality.The function classification base on NPN (Negation-Permutation-Negation) is the common method used to implement the equivalent substitution in logic optimization. The algorithms of function classification based on NPN can be divided into two kinds:(1) exact-NPN; (2) semi-NPN. The traditional method to compute the exact-NPN set is to enumerate all forms of the Boolean function. The advantage of this way is that the smaller number of NPN set can reduce the memory usage in storing the structure of digital circuits while it is a high timing complexity when enumerating all the forms of a Boolean function. However, semi-NPN set computation utilize a heuristic method to avoid the enumeration process, so it can have a good improvement in timing when computing NPN set while the number of the result NPN set will be larger which means a higher overhead in memory usage when storing the circuit structure.Based on the previous work, a fast function classification algorithm based on NPN is proposed in this paper. Comparing with the previous work, the proposed algorithm based on semi-NPN avoids the redundant computation with the usage of symmetry in Boolean functions. It improves the speed of function classification and diminishes the number of the result NPN set. In the logic synthesis of Boolean function, the speed of logic synthesis will be improved and the memory overhead will be reduced if the proposed algorithm is used.The proposed algorithm has been test in the experiment of millions of Boolean functions. Through the experimental results, the proposed algorithm will lead to a good improvement in the timing and memory overhead reduction during the process of logic synthesis and FPGA (Filed-Programmable Gate Array) technology mapping.