Often, one may have a particular circuit behavior in mind but not know what logic gate configuration will achieve the desired result. A Karnaugh maps is a tool that can be used to determine the simplest circuit comprised of AND and OR gates that will produce our desired behavior. Once we have our desired circuit design using AND and OR gates, Boolean algebra can be used to explore alternative circuits that will demonstrate the same behaviors while using other types of logic gates.
There are two types of Karnaugh maps: the Sum-of-Products (SOP) Karnaugh maps and the Product-of-Sums (POS) Karnaugh maps. While we will devote most of our focus to the SOP Karnaugh maps, we will briefly treat POS Karnaugh maps as well.
Because Karnaugh maps assist in the design of a circuit that will demonstrate a particular desired behavior, our procedure begins with specifying our desired behavior in the form of a truth table. For this example, we will use the truth table in Table 7.3.1.
This truth table is then used in constructing a Karnaugh map according to the following steps:
Divide your inputs into two groups. One group will have possible input values listed along the top row and the other group will have possible input values listed down the first column. Each group must contain either one or two inputs. For this example, I will group inputs \(A\) and \(B\) into one group (top row) and input \(C\) into the second group (left column).
For each group of inputs, list the possible combinations of input values in Gray code along their associated row or column of the map. Gray code requires an ordering in which only one input changes values between neighboring elements. So, the \(AB\) grouping will list the possible input value combinations in the following order: 00, 01, 11, 10. The \(C\) group will have entries of 0 and 1.
All other entries in the map will be filled in according to the circuit outputs displayed in Table 7.3.1. For example, the map location representing the intersection between \(AB=01\) and \(C=0\) will contain the value of 1 since the \(ABC=010\) entry of the truth table contains an output value of 1.
Examine the Karnaugh map and draw rectangles around groups of 1s, ensuring that each group contains a number of elements that is equal to an integer power of 2 and ensuring that every 1 that appears in the Karnaugh map is contained in at least one group. This results in the Karnaugh map in Figure 7.3.3.
For each group of 1s, determine which circuit inputs remain constant for all elements in that group. These inputs will be joined together by the AND function with the caveat that an input will be inverted if it remains constant with a value of zero for a given grouping. In our example, the 2x2 grouping has input \(A=0\) as the only input value common to all elements in the group, so this grouping is representative of the Boolean expression \(\overline{A}\text{.}\) The 1x2 grouping has both \(B=1\) and \(C=1\) common to all elements in the group, so this grouping is representative of the Boolean expression \(B\cdot C\text{.}\) The Boolean expression representing the full circuit functionality is then given by joining our AND groups together with ORs, resulting in \(Q=\overline{A} + B\cdot C\text{.}\)
