In digital electronics, simplifying Boolean expressions of many digital circuits is very difficult and consumes more time. So, to reduce the complexity of simplifying Boolean expressions, a method called Karnaugh Map is used. It was introduced by Maurice Karnaugh, a telecommunication engineer at Bell Labs in 1953.
The Boolean expressions with 2, 3, 4, and 5 variables can be minimized using the karnaugh map without using any Boolean algebra. It reduces the components or logic gates and inputs required for the given expression. Mostly simplification of logic function is done using karnaugh map only. This article will let you know how to simplify the Boolean expression using Karnaugh maps with some solved examples.
What is the Karnaugh Map?
The Karnaugh Map is defined as the graphical or pictorial representation of Boolean expressions with an array consists of 2^n cells arranged in a grid format. It is simply referred to as K-map or 2D truth table. It is used to reduce the complexity of solving 2, 3, 4, and 5 variable Boolean expressions of the digital circuits. There are two forms of K-maps such as SOP (sum of products) and POS (product of sum).
If the given Boolean expressions are in SOP form (minterms), then the array of K-map is represented with the binary value ‘1’. Similarly, if the given expression is in POS form (max terms), then the array of K-map is represented with ‘1’. After finding minterms and max terms, the expression can be reduced by making groups. The karnaugh map gives detailed information better than the truth table.
- For the 2 variable Boolean functions, it requires 4 numbers cells, which are arranged in a rectangular grid. Since 2^n = 2^2 = 4 cells.
- Similarly, for 3 variable karnaugh maps, it requires 8 numbers cells.
- For 4 variable karnaugh maps, it requires 16 cells.
- For 5 variable karnaugh maps, it requires two 4 variable karnaugh maps with 16 cells each.
K-map Rules
The karnaugh map rules are discussed below.
- The complex Boolean expressions can be simplified by following the karnaugh map rules as given below.
- Based on the number of variables present in the given Boolean expression, select the corresponding karnaugh map. That is, it might be either 2 variable k-map or 3 variable k-map or 4 variable k-map or 5 variable k-map.
- Determine the type of given Boolean expression. It might be in the form of SOP (minterms) or POS (max terms).
- If the given equation is in SOP form, then the cells of the respective k-map minterms are placed with binary value ‘1’.
- If the given equation is in POS form, then the cells of the respective K-map max terms are placed with binary value ‘0’.
- Now, the grouping of the maximum number of variables is done with the power of 2 like 2, 4, 8, etc. Grouping of variables could be horizontal and vertical, but not in diagonal. Grouping if variables can overlap to obtain the simplified equation. In groping of variables in large size, ‘Don’t care’ conditions are used to replace the empty cell based on the grouping of adjacent variables. They might be either 0 or 1.
- From the obtained groups, the minimized Boolean expression is determined. That means product terms are found and added up to convert them into SOP form.
Karnaugh Map 5 Variables
The karnaugh map with 5 variables contains 32 cells (2^n = 2^5 = 32). To construct 5 variable k-maps, two 4 variable k-maps are required. The 5 variable k-map is shown in the below figure.
From the above figure, we observe that the karnaugh map with 5 variables ABCD is drawn with two 4 variable karnaugh maps. Each 4 variable K-map contains 16 cells (2^n= 2^4 = 16). The two 4- variable K-map is drawn at 2 conditions. That is one for A=0 and A=1.
At A= 0, the 5 variable K-map is converted into 4 variable K-map.
For example, the cell of the upper left corner is B’C’D’E’ with binary value ‘0000’.
Karnaugh Map 4 Variables / 4×4 Karnaugh Map
The 4 variable karnaugh map or 4×4 karnaugh map is represented with an array of 16 cells. The binary values A and B are represented in the left side corner and the binary values of C and D are represented across the top.
When the binary value of A and B at the left side of the same row is combined with the binary value of C and D at the top of the same column, then the value of the cell of an array is obtained. The representation of karnaugh map 4 variables is shown below.
For example, the cell of the upper left corner is represented with A’B’C’D’ with the binary value of 0000. Similarly, the cell of the lower-left corner is represented with AB’C’D’ with binary value 1000.
If A=0, then the 4 variable karnaugh map is converted into 3 variable karnaugh map.
There are 16 possible minterms for the 4 variable k-maps, which are given in the below truth table.
How to use Karnaugh Map?
The karnaugh maps were developed with the help of Venn diagrams to reduce the logic functions very easily and quickly. So, that the number of logic gates and inputs can be reduced by simplifying the logic functions when compared to Boolean algebra.
The components required for the logic can be eliminated and saves cost. That means, the simplified logic function contains the lowest number of logic gates with inputs per gate.
Most of the logic simplification is done by using karnaugh maps rather than using Boolean algebra.
The karnaugh maps are simply referred to as K-maps, which are the systematic way of computing Boolean expressions.
It helps to determine the Product Of Sum (POS) and Sum Of Products (SOP) expressions, which are called minimum expressions.
K-maps is similar to the truth table with all the possible inputs and their corresponding output variables. But the values of the K-maps are represented in the cells of an array, where each cell of an array contains the input variable.
The Karnaugh map is used for logic expressions that contain 2, 3, 4, and 5 variables. The number of cells of the K-map is equal to the total number of input variable combinations.
An array of K-map contains 2^n cells in the grid format, where ‘n’ represents the number of input variables in the given Boolean expression that is to be simplified. By taking the truth table method as a reference, each cell in the K-map is represented as a single row of the truth table and the cell is shown as a square.
For example, when the number of input variables = 3, then the number of cells required for a K-map = 2^3 = 8. Similarly, for 4 input variables, the number of cells would be 2^4. The grid of the K-map should be filled with 0’s and 1′ to form corresponding SOP and POS expressions. Solving of K-map is done by making groups, which contain either 1’s or 0’s.
The karnaugh map method is very fast and more efficient to convert the truth table of Boolean expression into simplified SOP and POS form.
All the rows of the K-map are represented by square cells, which are represented as either minterm or maxterm.
The given Boolean expression can be converted into K-map by using two forms. They are,
- Un-optimized Form: If the number input variable combinations of the given function are ‘1’, then the simplified K-map gives standard SOP form (minterms). It converts the number of 1’s into minterms (product terms)
- Similarly, if the number of input variable combinations of the given Boolean function is ‘0’, then the simplified K-map gives standard POS form (max terms)
- Optimized Form: It reduces the number of minterms and max terms of the SOP and POS forms.
Now, let’s have a look at 2 variable karnaugh maps in detail.
A 2 variable contains 4 variables (2^n = 2^2 = 4) represented in 4 cells. The structure of the 2- variable karnaugh map is shown below.
From the above figure, only the grouping of 4 adjacent minterms is possible. The possible variable combinations by grouping 2 adjacent minterms are (m0, m1), (m2, m3), (m0, m2), and (m1, m3).
Karnaugh Map Solved Examples
Example 1: Simplify the given 4 variable Boolean using the karnaugh map.
F(A, B, C, D) = ∑(0, 2, 5, 7, 8, 10, 13, 15)
By using a 4- variable karnaugh map, the cells of the given function are represented with 1’s.
After representation, make the groupings to find the simplified equation.
The simplified equation of the given Boolean function is BD + B’D’
Example 2: Find the simplified Boolean equation for the given 3 variable function
F(A, B, C) = π(0, 3, 6, 7)
For the given function, 3 variable k-map is used which contains 8 cells which are arranged in a rectangular array as shown below.
From the above-solved k-map, we found 3 groups. They are A’B’C’, BC, ABC’. These three product minterms are added to get the final expression in SOP form.
The final expression is F = A’B’C’+BC+ABC’
Example 3: Consider a Boolean expression of F= AB’ + A’B + A’B’, which is to be simplified by using a 2-variable K-map.
Firstly, draw the truth table for the given equation. The truth table is given below.
A | B | F |
0 | 0 | 1 |
0 | 1 | 1 |
1 | 0 | 1 |
1 | 1 | 0 |
The output terms are represented with 1 in the corresponding cells because the given equation is in SOP form (minterms).
Draw the K-map as shown below.
From the above K-map, 2 groups are created by following the grouping rules. One group is formed by combining ( A’B’ ) and (AB’) terms and the other group is formed by combining (A’B) and (A’B’) terms. Here the lowest left cell is used in both groups.
Now determine the minimized equation by reducing the grouping variables.
By taking the common terms from the two groups, the conjunction of the minimized equation will be
A’+B’.
The same process is followed for 3, 4, and 5 variable karnaugh maps.
Thus, this is all about an overview of Karnaugh maps– definition, rules, use, 5 variable K-map, 4 variable or 4×4 K-map, and some solved examples. By using karnaugh maps, BCD (binary coded decimal) code can be converted into Gray code very easily and quickly. The truth table of the equation can be converted into K-map very easily and quickly. Here is a question for you, “What are the advantages of Karnaugh Maps? “