📖 In this Lesson, we will explore Karnaugh maps, a graphical method used to simplify Boolean algebra expressions. Karnaugh Maps are particularly useful for reducing complex logic circuits into simpler and more manageable forms.
Introduction to Karnaugh Maps
Karnaugh maps, also known as K-Maps, provide a systematic way to simplify Boolean algebra expressions.
They were developed by Maurice Karnaugh in the 1950s as a tool for digital circuit designers.
K-maps are widely used in the field of digital electronics to optimize logic circuits and minimize the number of gates required.
Why Use Karnaugh Maps?
Boolean algebra expressions can become quite complex, especially when dealing with multiple variables.
Simplifying these expressions manually can be time-consuming and cause errors.
Karnaugh maps offer a visual representation that simplifies the process of reducing Boolean expressions.
By using K-maps, we can:
- Quickly visualize the logical relationships between variables.
- Identify patterns and simplify the expression.
- Minimize the number of gates required in a logic circuit.
- Reduce the chances of errors during simplification.
Basics of Karnaugh Maps
Construction of Karnaugh Map
To construct a Karnaugh Map, we need to know the number of variables in the Boolean expression. We take the number of variables as the power of two to find out number of cells needed
So for 2 variables, 2² = 4, The K-Map for this case will have four cells.
The variables are represented as binary digits, and each cell in the map corresponds to a unique combination of variable values.
Example Karnaugh Map
Let's consider a simple example with three variables, A,B and C.
To find the number of combinations/gird size we will use the formula we learned earlier.
For two variables,
2² = 8, will be a grid with 8 squares.
Numbering a Karnaugh Map
Before proceeding any further lets number and mark the variables and all the input combinations relevant to this Karnaugh map.
To start we mark the top rows with the two variables, because there are 4 squares that way.
this numbering corresponds to the variables marked as below,
Finally the 3rd and final variable can be marked on the two rows and its input combinations,
Now we have a fully numbered K-Map ready for filling.
Filling the Karnaugh Map
We have two methods of filling a K-Map,
- Using Truth Table
- Using SOP Method
We will use the truth table method for this example,
To fill the K-Map, we need to refer to the truth table or the given Boolean expression. We assign the output values of the Boolean expression to the corresponding cells in the map.
Each row represents a unique combination of input variables.
Let's consider a Boolean expression Y = A.B.C + A.B.C'.
So lets look at the truth table for this the above expression,
| A | B | C | D |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 |
| 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 0 | 0 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 1 |
| 1 | 1 | 1 | 1 |
📖 Let’s take where the output is high or the SOP instance (where output is 1) in this truth table,
| A | B | C | D |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 |
| 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 0 | 0 |
| 1 | 0 | 1 | 0 |
1 | 1 | 0 | 1 |
1 | 1 | 1 | 1 |
📖 Now we will mark the inputs that correspond with each SOP instance in the table,
- where A = 1, B = 1 and C = 0,
- where A = 1, B = 1 and C = 1,
📖 Fill other squares with zeros as to match with the truth table,
YaY!🥳 now for the fun part.
Grouping the Cells
After filling the K-Map, we look for adjacent cells with the same output value ( 1 ). These cells can be grouped together to simplify the Boolean expression.
The groups can be in the form of rectangles or squares, and they must always be in powers of 2 , should find the largest square possible (8 ,4, 2).
In our example, we have a group of adjacent cells with the output value 1 which can form a group of 2.
Writing the Simplified Expression
The grouped cells represent the simplified terms of the Boolean expression.
Each group will correspond to a term in the simplified expression.
The variables within each group are combined using the logical operator OR, and the groups themselves are combined using the logical operator AND.
📖 When looking at the group we take the non changing variable from row wise or column wise,
In the group marked, the Boolean values of A and B does not change.
But if we check Boolean values for C it does change 0 and 1.
When writing the expression SOP rules should be followed, 1 = A and 0 = A’
As the non changed Boolean values taken for A and B are 1, we take the expression and combine them using OR ,
For our example, we have one group of cells:
Group 1: AB
👉 The simplified expression is obtained by combining the terms with OR and the groups with AND. In this case, the simplified expression is: AB
Here are some other examples so we can further understand various grouping methods and simplification.
Example 1: A’.B’.C + A’.B.C + A.B’.C’ + A.B’.C
- In the above expression there are 3 inputs, so we need a 2^3 = 8, A grid with 8 squares.
- We will use the SOP Method of filling for this example.
SOP Method of filling K-Maps
Take the min-terms and max terms of the given Boolean expression
Now take each group of variables and plot them in the K-Map,
Example: A=0, B=0, C=1
Fill out for each group of variables
Now, group any adjacent terms in power of two (8, 4, 2)
Write the expression as before,
The bottom group C does not change and A does not change,
We take the format as before 1 = A and 0 = A’
C does not change and the value is 1 so C and A does not change and value is 0 so, A’
A does not change and the value is 1 so A and B does not change and value is 0 so, B’
The variables within each group are combined using the logical operator OR, and the groups themselves are combined using the logical operator AND
So, we get A’.C + A.B’
Example 2: A’.B.C’.D’ + A.B.C’.D’ + A’.B.C’D + A.B.C’.D + A’.B.C.D + A’.B.C.D’
-
In the above expression there are 4 inputs, so we need a 2^4 = 16, A grid with 16 squares.
Number the K-Map by dividing 2 variables for each side,
Fill out the K-Map according to the Truth Table or SOP Method.
| A | B | C | D | Z |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 0 | 1 | 0 |
| 0 | 0 | 1 | 0 | 0 |
| 0 | 0 | 1 | 1 | 0 |
| 0 | 1 | 0 | 0 | 1 |
| 0 | 1 | 0 | 1 | 1 |
| 0 | 1 | 1 | 0 | 1 |
| 0 | 1 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 1 | 0 |
| 1 | 0 | 1 | 0 | 0 |
| 1 | 0 | 1 | 1 | 0 |
| 1 | 1 | 0 | 0 | 1 |
| 1 | 1 | 0 | 1 | 1 |
| 1 | 1 | 1 | 0 | 0 |
| 1 | 1 | 1 | 1 | 0 |
| A | B | C | D | Z |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 0 | 1 | 0 |
| 0 | 0 | 1 | 0 | 0 |
| 0 | 0 | 1 | 1 | 0 |
0 | 1 | 0 | 0 | 1 |
0 | 1 | 0 | 1 | 1 |
0 | 1 | 1 | 0 | 1 |
0 | 1 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 1 | 0 |
| 1 | 0 | 1 | 0 | 0 |
| 1 | 0 | 1 | 1 | 0 |
1 | 1 | 0 | 0 | 1 |
1 | 1 | 0 | 1 | 1 |
| 1 | 1 | 1 | 0 | 0 |
| 1 | 1 | 1 | 1 | 0 |
Now take each group of variables and plot them in the K-Map,
Example: A=0, B=1, C=0 and D=0
Fill out the table this way,
Now, group any adjacent terms in power of two (8, 4, 2)
Here there are two groups of 4,
Write the expression as before,
We take the format as before 1 = A and 0 = A’
Check the first group (square group) row wise, B does not change and check it column wise, C does not change,
Here the expression is B.C’
Check the second group row wise, C and D both change and check it column wise, both A and B does not change,
Here the expression is A’.B
The variables within each group are combined using the logical operator OR, and the groups themselves are combined using the logical operator AND
So, we get A’.B + B.C’