Minterms and Sum-of-Products Expressions
Sometimes a problem is easiest to solve first in truth-table form. For example, if you want a function that determines if the majority of three signals is true, it’s simple to create the truth table:
| A | B | C | Most |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 |
| 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 |
| 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | 1 |
| 1 | 1 | 1 | 1 |
But if you want to implement this in switches or gates, you need a Boolean expression, so we need a way to derive a Boolean expression from a truth table. Here is one failsafe way to do that: simply list each input combination for which the function is true. Going down the truth table, this function could be expressed as "The function is true if...
- A is false and B is true and C is true (the fourth row), or
- A is true and B is false and C is true (the 6th row), or
- A is true and B is true and C is false (the 7th row), or
- A is true and B is true and C is true (the last row)."
That can then be directly translated to a Boolean expression: Most = A·B·C+A·B·C+A·B·C+A·B·C.
The various ANDed combinations of the inputs in either complemented or uncomplemented form (e.g. A·B·C) are called minterms. A minterm effectively specifies a single combination of input values (e.g. the situation where A is true, B is false, and C is true). The minterms for which a function is true are called 1-minterms, but if someone just says "minterms of the function" then they mean the 1-minterms. Since each minterm describes a single row of the truth table, ORing the necessary minterms together is essentially saying "The function is true when any of these is true," which directly gives you a Boolean expression for the desired function.
This type of expression is called a canonical sum of products expression. "Sum of products" (SoP) because the AND in the minterms makes them "product" terms (not as in multiplication; as in logical conjunction), and those minterms are "summed" together (logical disjunction) to create the expression. The "canonical" form, sometimes called "standard" form, of a sum-of-products expression is the unsimplified form that uses the minterms directly. (Simplification will be discussed shortly.)
As a shorthand, the minterms can be numbered, and the canonical sum-of-products expression written using the ∑ summation operator. The order of the numbering is determined by interpreting the inputs as bits of a binary number, so if the function above is described as F(A,B,C), then ABC=000 (A·B·C) is minterm 0, ABC=001 (A·B·C) is minterm 1, etc. The function above can be described as F(A,B,C)=∑m(3, 5, 6, 7), where the 'm' denotes a list of minterms.
Karnaugh Maps
Although canonical SoP expressions are simple to derive, they are usually far from optimal. One option for improving them is to try to simplify them algebraically. For example, from the last two terms of Most = A·B·C+A·B·C+A·B·C+A·B·C, A∙B can be pulled out, leaving A∙B∙(C+C), which simplifies to A∙B. Perhaps some further manipulation can be done, but trying to reduce an expression algebraically is tedious, error-prone, and difficult to optimize.
Consider the manipulation just done though -- specifically the step with A∙B∙(C+C). Another way to think about this subexpression is "if A and B are both true, then the expression is true whether C is true or false." In effect, it means that if A and B are true, C doesn't matter -- that's why it could be removed. There is a tool to help find all of these situations where an input doesn't matter: Karnaugh maps.
A Karnaugh map (usually shortened to K-map) is a truth table arranged in a special way: the minterm for every cell differs from its neighbors in exactly one input. For example, A∙B∙C will be adjacent to A∙B∙C, but not to A∙B∙C. This is not the case in all the truth tables we’ve seen so far; for example, A∙B∙C is typically adjacent to A∙B∙C.
Here is an arrangement that works for three inputs. Since each cell must be adjacent to three other cells (one for each of the inputs changing), the K-map must be a 2-dimensional grid. The top table shows the minterm expressions for each cell, and the bottom table is the same arrangement but with a more typical labelling used for K-maps, where the rows and columns are labeled with the input values corresponding to those minterms.
You can confirm that moving from cell to cell changes exactly one input, but note that to complete the arrangement, you have to be able to jump from the left or right edge to the other side. Topologically, this is actually a torus, but we cut and flatten it to make it easier to draw.
Filling in the K-map with the truth table from above confirms that 1-minterms A∙B∙C and A∙B∙C are next to each other. As already discovered, these two minterms can be combined and described with a single, simpler expression, and that relationship is shown on the K-map by graphically grouping them with a circle (or rounded box, or whatever visual grouping method you prefer).
These groups of 1-minterms are called implicants, and the purpose of K-maps is to quickly find all of the implicants.
To find the simplified expression for an implicant, look at which inputs stay the same and which inputs change. The inputs that stay the same are the "as long as these inputs have this value" part of the simplification, and the inputs that change are the "these inputs don't matter" part of the simplification.
A simplified SoP expression can be created by ORing the implicants together, just as the canonical SoP expression came from ORing the 1-minterms together: A∙B (red) + A∙C (blue) + B∙C (green)
There's no problem with implicants overlapping. In this example, when A, B and C are all true, all of the implicants are true, but 1+1+1 is still 1. Using smaller implicants to avoid overlap would just make the expression more complicated for no reason.
Minimal Sum-of-Products
The previous example was straightforward, but sometimes more complicated situations arise when solving K-maps, so there is a procedure to ensure that the resulting SoP expression is optimal. Following this procedure produces a form called minimal sum-of-products because the expression will have as few terms as possible, and each term will be as small as possible.
We will find a minimal SoP expression for this function:
With four inputs, the K-map is a 4x4 grid, but it still has the property that all adjacent cells differ in exactly one input value. Again, to complete the arrangement, the left and right are actually connected, as are the top and bottom.
Consider these two implicants:
Their expressions are A·B·D (on the left) and A·B·D (on the right), but those can be algebraically simplified using the same process as before: essentially saying "as long as A is false and D is true, it doesn't matter what B is." So those two implicants can be combined into a bigger implicant with expression A·D. This is true for any implicants that are the same size and are adjacent on the K-map. Since only equally-sized (and shaped) implicants can be combined, resulting implicants will always be rectangles with dimensions that are powers of 2 (1x2, 2x2, 4x1, etc.).
An implicant that is as simple as possible (graphically, as large as possible on the K-map) is called a prime implicant. Since larger implicants result in fewer and smaller terms in the expression, prime implicants are always desired when deriving minimal SoP expressions.
The first step toward finding a minimal SoP expression is to find all of the prime implicants. Here are all of the prime implicants for this function:
These implicants represent the terms we could use to form an SoP expression for this function, but they might not all be needed -- although there is no problem with using overlapping implicants in general, it could be that some combinations of implicants are completely redundant, so including them all would not be minimal. To decide which implicants to use, the first step is to find the implicants that do need to be included, and those are the prime implicants that cover minterms that no other prime implicant covers.
A prime implicant that covers a minterm that no other prime implicant covers is called an essential prime implicant. Since it is the only option for covering that minterm (if using prime implicants, which was already established as a requirement), it must be included in the expression. There is only one essential prime implicant for this function, B·D, which is essential because it is the only implicant that covers A·B·C·D.
Often, the essential prime implicants cover all of the 1-minterms between them, but sometimes they do not (as is the case here). From this point, the remaining 1-minterms need to be covered by non-essential prime implicants. Larger implicants should be prioritized, since they result in smaller terms in the expression, but a larger implicant is only worth including if it increase the coverage at least as much as other options using smaller implicants.
Following this process with this function results in two equally-minimal expressions, depending on which size-4 non-essential prime implicant is chosen. (It would not be worth including both of them, because the second one would only cover a single additional minterm, whereas two additional minterms can be covered by using size-2 implicants.)
B·D + C·D + A·B·C + A·B·D:
B·D + A·D + B·C·D + A·B·C:
To summarize, the process for finding a minimal sum-of-products expression for a function is:
- Find all prime implicants.
- Select all essential prime implicants.
- Choose non-essential prime implicants to cover remaining 1-minterms.
Product-of-Sums Expressions
Similar to how a single combinatinon of input values can be specified (by a minterm), it is possible to specify all combinations of input values except for one. Consider the expression (in a function of A, B, and C) combinationcanonical sum-of-products expression can be created by describing each case for which a desired function is true, a canonical product-of-sums expression can be created by describing each situation where the desired function is false. Consider the function A+B+C -- this is true for all combinations of A, B, and C except for A=1, B=0, C=1. This is called a maxterm.
Similar to how a function can be described by ORing together all of its 1-minterms, a function can also be described by ANDing together all of its 0-maxterms to produce a product-of-sums expression. It is a bit more mentally-convoluted than SoP, but is effectivly saying "everything except this row and this row and this row."
Consider this function:
| A | B | C | F |
|---|---|---|---|
| 0 | 0 | 0 | 1 |
| 0 | 0 | 1 | 0 |
| 0 | 1 | 0 | 1 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 0 | 1 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 1 |
| 1 | 1 | 1 | 1 |
You could describe this function by saying "if A·B·C is not true, and A·B·C is not true, and A·B·C is not true, then the function is true." By DeMorgan's theorem, each term like A·B·C can be changed to the maxterm form like A+B+C, and so a full canonical product-of-sums (PoS) expression for this function would be (A+B+C) · (A+B+C) · (A+B+C).
Canonical PoS expressions can be summarized by listing the 0-maxterms in a product operator, ∏. The above function can be described as F(A,B,C)=∏M(1,3,5), where the capital M denotes a list of maxterms.
Just like with sum-of-products, a K-map can be used to find situations where the canonical form can be simplified by finding implicants of maxterms. Each implicant describes "everywhere except here," and so ANDing appropriate implicants can describe the full function: (A+C) · (B+C). Note how the inputs show up "inverted" from how they would look in an SoP expression.
Don't-Cares
When designing logic, there can be situations where whether an output is 0 or 1 doesn't matter. For example, maybe a system has a global "enable" signal, and when designing a device within that system, if the enable is inactive then the output of the device doesn't matter because subsequent devices in the system are going to be disabled anyway. Or maybe a particular set of input values can't (or at least shouldn't) happen, and it's not a critical system, so you don't care what value the output(s) have in those situations.
Consider a D-pad on a game controller. It produces four pieces of Boolean information: up, right, down, and left (where '1' will mean 'pressed').
It is possible to press a diagonal as, e.g., a combination of up and right, but it is not possible (without serious force) to input left and right at the same time or up and down at the same time.
Suppose you wanted some logic to indicate that a diagonal is being pressed. In situations where an impossible combination of inputs is present, instead of deciding now whether the output should be 0 or 1, it can instead be specified as a "don't care," which is usually denoted by an 'x' (but sometimes a 'd' or a '-'). The typical reason to do this is because the added flexibility provided by don't care situations can be used to simplify the logic during implementation, as will be seen shortly. The truth table for this "is diagonal pressed?" function would be
| U | R | D | L | Diag |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 0 | 1 | 0 |
| 0 | 0 | 1 | 0 | 0 |
| 0 | 0 | 1 | 1 | 1 |
| 0 | 1 | 0 | 0 | 0 |
| 0 | 1 | 0 | 1 | x |
| 0 | 1 | 1 | 0 | 1 |
| 0 | 1 | 1 | 1 | x |
| 1 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 1 | 1 |
| 1 | 0 | 1 | 0 | x |
| 1 | 0 | 1 | 1 | x |
| 1 | 1 | 0 | 0 | 1 |
| 1 | 1 | 0 | 1 | x |
| 1 | 1 | 1 | 0 | x |
| 1 | 1 | 1 | 1 | x |
When a function is converted to a Boolean expression with a K-map, don't cares can be included in implicants if it is beneficial to do so. The point of a don't care is precisely that you don't care if it is a 1 (included in an implicant of 1s) or a 0 (not included in an implicant of 1s, or included in an implicant of 0s if solving for PoS).
The SoP expression resulting from this K-map would be U·L+U·R+D·L+D·R.
Better yet, derive a PoS expression for this function. Confirm for yourself that the result is (U+D)·(L+R).
Summary
- A minterm is an ANDed combination of all inputs of a function in complemented or uncomplemented form. It specifies a single possible situation of the inputs -- essentially a single row of the truth table.
- All of the 1-minterms of a function can be ORed together to form a canonical sum-of-products expression.
- A canonical sum-of-products expression can be simplified using a tool called a Karnaugh map to create a minimal sum-of-products expression.
- Product-of-sums expressions follow similar logic, but with maxterms -- ORed combinations of inputs that specify every situation of the inputs except one.
- "Don't care" situations in desired logic can be used to simplify the implementation.