BOOM - A Heuristic Boolean Minimizer

Abstract

This paper presents an algorithm for two-level Boolean minimization (BOOM) based on a new implicant generation paradigm. In contrast to all previous minimization methods, where the implicants are generated bottom-up, the proposed method uses a top-down approach. Thus, instead of increasing the dimensionality of implicants by omitting literals from their terms, the dimension of a term is gradually decreased by adding new literals. The method is advantageous especially for functions with many input variables (up to thousands) and with only few care terms defined, where other minimization tools are not applicable because of the long runtime. The method has been tested on several different kinds of problems and the results were compared with ESPRESSO.