×

Two-level logic minimization: An overview. (English) Zbl 0818.94025

Summary: Forty years ago, W. V. Quine [Am. Math. Mon. 59, 521-531 (1952; Zbl 0048.245)] noted that finding a procedure that computes a minimal sum of products for a given propositional formula is very complex, even though propositional formulas are fairly simple. Since this early work, this problem, known as two-level logic minimization, has attracted much attention. It arises in several fields of computer science, e.g., in logic synthesis, reliability analysis, and automated reasoning. This paper exposes the classical approach for two-level logic minimization, and presents the recent developments that overcome the limitations of the procedures proposed in the past. We show that these new techniques yield a minimizer that is from 10 up to 50 times faster than the previously best known ones, and that is able to handle more complex functions.

MSC:

94C10 Switching theory, application of Boolean algebra; Boolean functions (MSC2010)
03B05 Classical propositional logic
68W10 Parallel algorithms in computer science

Citations:

Zbl 0048.245
PDFBibTeX XMLCite
Full Text: DOI