BOOM: a heuristic boolean minimizer

摘要: We present a two-level Boolean minimization tool (BOOM) based on new implicant generation paradigm. In contrast to all previous methods, where the implicants are generated bottom-up, proposed method uses top-down approach. Thus instead of increasing dimensionality by omitting literals from their terms, dimension term is gradually decreased adding literals. Unlike most other tools like ESPRESSO, BOOM does not use definition function be minimized as basis for solution, and thus original coverage influences solution only indirectly through number used. Most methods two basic phases introduced Quine-McCluskey, known prime (PI) covering problem solution. Some more modern combine these phases, reducing PIs processed. This approach also used in BOOM, search included into aims at maximum output function. The defined its on-set off-set, listed truth table. don't care set, often representing dominant part table, need specified explicitly. efficient above functions with large input variables while few terms defined. procedure very fast, hence if first meet requirements, it can improved an iterative manner. has been tested several different kinds problems, MCNC standard benchmarks or larger problems randomly.