BOOM - A Heuristic Boolean Minimizer

Authors

  • Petr Fišer
  • Jan Hlavička

Keywords:

Boolean minimization, logic functions, sparse functions, implicant expansion, group minimization, covering problem solution, mutations

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.

Downloads

Download data is not yet available.

Downloads

How to Cite

Fišer, P., & Hlavička, J. (2012). BOOM - A Heuristic Boolean Minimizer. Computing and Informatics, 22(1), 19–51. Retrieved from https://www.cai.sk/ojs/index.php/cai/article/view/450