ComputingComputer EngineeringComputer ScienceAlgorithmsDesign AutomationOptimizationBoolean OperationsCombinatorial OptimizationHeuristic OptimizationBoolean Function MinimizationBoolean MinimizationCircuit MinimizationLogic MinimizationMaximum CoverageMinimizationMinimization Of Boolean FunctionsOptimization Heuristics
We present a two-level Boolean minimization tool (BOOM) based on a new implicant generation paradigm. In contrast to all previous minimization methods, where the implicants are generated bottom-up, the proposed approach 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. Unlike most other minimization tools like ESPRESSO, BOOM doesn't use the definition of the function to be minimized as a basis for the solution, thus the original coverage influences the solution only indirectly through the number of literals used. Most of the minimization methods use two basic phases introduced by Quine-McCluskey and known as prime implicant (PI) generation and covering problem solution. Some more modern methods, like ESPRESSO, combine these two phases, reducing the number of PIs to be processed. This approach is also used in BOOM, the search for new literals to be included into a term aims at maximum coverage of the output function. The function to be minimized is defined by its on-set and off-set listed in a truth table. Thus the don't care set, often representing the dominant part of the truth table, need not be specified explicitly. The proposed minimization method is efficient above all for functions with a large number of input variables while only few care terms are defined. The minimization procedure is very fast, hence if the first solution does not meet the requirements, it can be improved in an iterative manner. The minimization method has been tested on several different kinds of problems. The MCNC standard benchmarks were solved many times in order to evaluate the minimality of the solution and the runtime.
14
Minimization of Boolean Functions*
E.J. McCluskey · Bell System Technical Journal · 1956 · 1.2K citations
The Problem of Simplifying Truth Functions
W. V. Quine · American Mathematical Monthly · 1952 · 801 citations
Logic synthesis for vlsi design
Richard Rudell, Alberto Sangiovanni‐Vincentelli · 1989 · 298 citations
Two-level logic minimization: an overview
Olivier Coudert · Integration · 1994 · 185 citations