Section 3.5 Optimum minimization
Implicants.
The question, "What is the simplest reduced form of a logic equation?" does not have a unique answer. There can be more than one good solution, requiring the same amount of circuitry. So what constitutes even one simplest solution? To answer this precisely, it helps to introduce some terminology, illustrated in Figure 3.5.1.
- A minterm is a product term that occupies only one cell on a Karnaugh map. A minterm also corresponds to one row of a truth table. In the figure, \(AB'C'D'\) and the other cells containing 1s are minterms.
- An implicant is any product term (a single minterm is a trivial product term) that makes an expression TRUE. In the expression \(A + A'B\text{,}\) \(A\) and \(A'B\) are implicants. In the figure, \(AB'C'D'\text{.}\) \(BC'D\text{,}\) \(ABD\text{,}\) and \(AC\) are implicants.
- A prime implicant is an implicant that cannot be combined with another implicant to make a product term with fewer variables. In the figure, \(BC'D\text{,}\) \(ABD\text{,}\) and \(AC\text{,}\) are all prime implicants. While \(AB'C'D'\) is an implicant, it is not a prime implicant, since it can be grouped with \(AB'CD'\) to make \(AB'D'\) (which is prime).
- An essential prime implicant is a prime implicant that covers at least one cell not covered by any other implicant. It is "essential" because removing it would leave at least one cell uncovered. In the figure, \(BC'D\) and \(AC\) are essential prime implicants, because they cover cells not covered by any other groups. However, \(ABD\) is not essential. If it were removed, its cells would still be covered by \(BC'D\) and \(AC\text{.}\)
A minimized logic equation is a sum of essential prime implicants. In Figure 3.5.1, the minimized logic equation is \(Y = AB'D' + BC'D + AC\text{.}\)
Algorithmic minimization.
The process of logic minimization is to find the smallest number of essential prime implicants that will cover the 1s on the Karnaugh map. With practice, it isn’t hard to use a Karnaugh map to identify essential prime implicants for functions of four or fewer variables. For five and six variables, the Karnaugh map goes three-dimensional, becoming a stack of two or four planar four-variable maps with groups that extend vertically as well as horizontally. Beyond that, the Karnaugh map is in hyperspace and no longer visually tractable, though it can be represented by a data structure in a computer program.
The systematic nature of logic minimization invites algorithmic solutions that search for all the prime implicants and from that set identify the essential prime implicants. It has been found, however, that tabulating all possible implicants and then searching for the prime ones rapidly becomes computationally unwieldy. A better algorithm, called Espresso, is described in the textbook by Katz and in lecture notes by Nowick. Some version of Espresso is used in EDA tools to simplify a logic equations.
1
R.H. Katz, Contemporary Logic Design. Benjamin/Cummings (1994), pp 85-91.
2
Columbia University CSEE 6861 (2016), accessed June 3, 2020.
Espresso starts with one cell in the (hyperspatial) Karnaugh map and grows a prime implicant by expanding into neighboring cells. Once a prime implicant has been identified the expansion process begins again with a new, uncovered cell. In this way a set of overlapping prime implicants is assembled. It may not be an optimal set, however. Espresso searches for a better covering by shrinking (reducing) some of the prime implicants so that none of them overlap, and expanding them again in different directions to create a different overlapping covering of the map. If this new covering is better (fewer, larger prime implicants) than the first one, it is retained and the reduce-expand step repeats from there (though in such as way as to not repeat old solutions). If not, it goes back and tries again. The quality and efficiency of results depend on the algorithm’s choices of where to start and how to expand and reduce, and Espresso includes various heuristics for generating good results in reasonable time.
