Logic and Foundations Commons^™

Fast Adjustable Npn Classification Using Generalized Symmetries, Xuegong Zhou, Lingli Wang, Peiyi Zhao, Alan Mishchenko

Mathematics, Physics, and Computer Science Faculty Articles and Research

NPN classification of Boolean functions is a powerful technique used in many logic synthesis and technology mapping tools in FPGA design flows. Computing the canonical form of a function is the most common approach of Boolean function classification. In this paper, a novel algorithm for computing NPN canonical form is proposed. By exploiting symmetries under different phase assignments and higher-order symmetries of Boolean functions, the search space of NPN canonical form computation is pruned and the runtime is dramatically reduced. The algorithm can be adjusted to be a slow exact algorithm or a fast heuristic algorithm with lower quality. For …