In the previous tutorial, all possible Boolean functions between two variables were discussed. In the tutorial – Boolean Algebra, several theorems and postulates were stated that are useful for simplifying a Boolean expression or function. However, simplifying a Boolean expression using theorems and postulates is quite complicated and prone to errors. Therefore, for simplification of Boolean expressions, some map methods have been developed. The most commonly used map method is Karnaugh Map or K-Map.
These methods are based on the fact that each Boolean function has a unique truth table. A Boolean function can be represented by several Boolean expressions, but its truth table will always remain the same. This is due to the fact that a digital circuit will always have fixed outputs or response corresponding to the inputs. Let's first discuss the K-map.
Karnaugh Map –
The Karnaugh map is the most common simplification technique for Boolean expressions. It is based on the following facts –
1) Any Boolean function, however, can be represented in multiple forms or Boolean expressions always have a unique truth table. If two Boolean expressions have the same truth table, they have the same function.
2) Any Boolean function can be represented by sum of products (Minterms) or product of sums (Maxterms).
3) The sum of Minterms or product of Maxterms is reducible by applying several Boolean theorems.
K-map is basically a tabular representation of the truth table. For example, a function of two variables may have the following truth table –
Figure 1: A two-variable K map
K-Map is useful for minimizing Boolean expressions containing up to 5 variables or less. Once the map is constructed, the minimized expression can be deduced by the following process –
1) Insert 1s in the cells corresponding to combinations for which the function value is 1 in the truth table. Then fill in 0s in the remaining cells of the K-map. Each cell on the map represents a Minterm. The Boolean function represented by the map (the map is just a graphical representation of the truth table) is the sum of minterms that can contain one or more Boolean variables as literals.
2) Scan the map for cells with a value of 1 that cannot be combined with any other cells with a value of 1 or form groups with other cells with a value of 1. This means identifying cells with a value of 1 that do not have adjacent cells with a value of 1. These groups represent minterms containing all Boolean variables as literals in the term as part of the Boolean function.
3) Scan the map for cells with a value of 1 that are adjacent only to each other cells with a value of 1 and form groups containing only two cells with a value of 1, but are not part of any group containing four or eight cells with a value of 1. These groups represent minterms containing Boolean variables as literals one less than the maximum number of Boolean variables in the term as part of the function. These groups are called peers.
4) Scan the map for cells with a value of 1 that are adjacent to only three other cells with a value of 1 and form groups containing only four cells with a value of 1, but are not part of any group containing eight cells with a value of 1. These groups represent minterms containing Boolean variables as literals two less than the maximum number of Boolean variables in the term as part of the function. These groups are called quads. In a 2-variable function, quad formation means that the output of the function is 1.
5) Scan the map for cells with a value of 1 that are adjacent to seven other cells with a value of 1 and form groups containing eight cells with a value of 1, but which are not part of any group containing sixteen cells with a value of 1 or greater. These groups represent minterms containing Boolean variables as literals three fewer than the maximum number of Boolean variables in the term as part of the function. These groups are called octets. In a 3-variable function, the formation of the octet means that the function's output is 1.
6) Form all groups of singles, pairs, quadruplets and octets so that there is a minimum number of groups. Pairs, quadruplets and octets can also be formed by combining cells with a value of 1 on opposite edges of the map. As in the following K map for 3-variable Boolean function, m0 and m8 at the corners are forming a pair.
Figure 2: A three-variable K-map
7) Remove any redundant groups.
8) A cell with value 1 without any adjacent cell with value 1 gives a Minterm containing 2, 3, 4, 5 variable terms for 2-variable, 3-variable, 4-variable, 5-variable Boolean function or map K respectively. A pair of cells with value 1 gives a Minterm containing 1, 2, 3, 4 variable terms for 2-variable, 3-variable, 4-variable, and 5-variable Boolean function or K-map respectively. A quadruple of cells with value 1 gives a Minterm containing 1, 2, 3 variable terms for 3-variable, 4-variable and 5-variable Boolean function or K-map respectively. Quad formation for a 2-variable function means it equals 1. An octet of cells with value 1 gives a Minterm containing 2 or 3 variable terms for 4- and 5-variable Boolean function or K-map , respectively. Octet formation for a 3-variable function means it equals 1.
9) If a single cell with value 1 is identified, it represents a Minterm having the Boolean variable as a literal in the term is matched to the value 1 for the respective Boolean variable and/or having the Boolean variable's complement as a literal in the term for was matched to the value 0 for the respective boolean variable. This cell with value 1 will induce a Minterm on the function containing all Boolean variables in complementary or normal form. If a pair is identified, a Boolean variable will be eliminated and a Minterm containing one fewer number of maximum Boolean variables will be induced into the Boolean function. Similarly, a quad leads to the elimination of two Boolean variables in Minterm, and so on. The Boolean variable that has a bit shift within the pair, quadruple or octet is eliminated in the term.
10) The Boolean function is the logical sum of the Minterms generated by all groups. The Boolean function as product of the sum can be generated in a similar way by groups of 0s.
Two-variable K map –
A two-variable K-map has four cells as the maximum number of minterms possible with two Boolean variables is 4 (2^2). There can be a maximum of 16 functions (2^2*2) generated by two boolean variables.
Figure 3: K-Map and Two-Variable Minterms
A function generated by a two-variable K-map is reducible by single cells or pairs of value 1. The formation of a quad in the two-variable K-map means that the function equals 1.
Three-variable K map –
A three-variable K-map has eight cells as the maximum number of minterms possible with three Boolean variables is 8 (2^3). There can be a maximum of 64 functions (2^2*3) generated by three boolean variables.
Figure 4: K-Map and Three-Variable Minterms
A function generated by a three-variable K-map is reducible by single, even, or quadruple-valued cells. The formation of an octet in the three-variable K map means the function equals 1.
Four-variable K-map –
A four-variable K-map has sixteen cells, as the maximum number of minterms possible with four Boolean variables is 16 (2^4). There can be a maximum of 256 functions (2^2*4) generated by four Boolean variables.
Figure 5: Four-variable K-map and minterms
A function generated by a four-variable K-map is reducible by single cells of value 1, pairs, quadruplets, or octets. The formation of 16 single-valued cells in the four-variable K map means the function equals 1.
Five-variable K-map –
A five-variable K-map has thirty-two cells, as the maximum number of minterms possible with five Boolean variables is 32 (2^5). There can be a maximum of 1024 functions (2^2*5) generated by five Boolean variables.
Figure 6: Five-variable K-map and minterms
A function generated by a five-variable K-map is reducible by single cells of value 1, pairs, quadruplets, octets, or group of 16 cells of value 1. The formation of 32 single-valued cells in a K-map of five variables means the function equals 1.
I don't care about combinations –
It is not necessary that all outputs of a Boolean function are always known. In digital circuits, there may be a possibility that for certain combinations the output is 1 or 0. In this case, d, x or Ø is inserted into the K map for the corresponding input combinations. To derive the Boolean expression, 1 or 0 can be assumed in indifferent combinations to deduce a minimum sum of products or product from the sum expression.
Quine-McCluskey Method –
K-map is useful in deducing Boolean expressions involving four Boolean variables or less. Plus, it gets complex. Therefore, another method called the Quine-McCluskey method is used to deduce Boolean expressions involving four or more Boolean variables. The Quine-McCluskey method is a tabular method for deriving the minimum Boolean expression. In the truth table of a Boolean function, the combinations for which the output of the function is 1 can be listed. These combinations can be indexed in ascending order as binary numbers. For example, suppose there is a Boolean function involving four Boolean variables (A, B, C, D) with the following truth table –
Combinations resulting in 1 when indexed in ascending order as binary numbers give the following table for the above case
This Boolean function can be written as follows – Combinations resulting in 1 when indexed in ascending order as binary numbers give the following table for the above case –
F(A, B, C, D) = ∑ (0, 5, 8, 9, 10, 11, 14, 15)
In the first step of Quine-McCluskey method, the minterms are organized into groups by the number of 1s in them as follows –
Any two minterms in adjacent groups like group 0 and 1, group 1 and 2 or group 2 and 3 and so on are now compared and examined for the change in the value of just one Boolean variable. Such minterms are selected as match and tabulated as pairs in the next step with a dash where single boolean variable changed to match as follows –
In the next step, the matches in the adjacent table groups in step 2 are compared and examined for trace to the same variable and change in the value of just one Boolean variable. These matches are selected as courts and tabulated in the following table with a dash where the single Boolean variable has been changed for the match. The pairs in the second table and the minterms in the first table that were not matched in the respective tables are also tabulated in the next table (third table) as follows –
The quadruplets, pairs or singles derived in the third table (removing the redundant ones) are called main implements. In the next step, the main implements are tabulated against the minterms and the minterms included in the respective main implement (quadruple, pair or single) are marked by X with respect to the respective main implement as follows –
In the final table, columns that have a single X are examined and rows that contain that X are identified. The main implements respective to these rows are noted and the terms respective to these main implements are included as sum of products in the Boolean expression by comparing main implements and Boolean variables of the third table. In the third table, the Boolean variable against the selected main implement with dash value is not included, the Boolean variable against the selected main implement with value 1 is included in normal form in the respective term, and the Boolean variable against the selected main implement with value 0 is included in compliment form in the respective term. The main implements selected from the fourth table are called essential implements. For the boolean function above, in the fourth table, all rows are having an X that is unique in at least one column. Therefore, all rows are selected and all core implements are core implements for the Boolean function. From the third table, the Boolean expression for the function can be derived as follows –
F (A, B, C, D) =AB' + AC + B'C'D' + A'BC'D
Now, with the knowledge of K-map and the Quine-McCluskey method, any Boolean function with a given truth table can be easily minimized. In the next tutorial, learn about logical gate implementation of a minimized Boolean expression.
