Make sure to check the previous blog on Boolean Algebra as that can help a lot to have a deeper understanding. In this blog, we will learn about K-Map Simplification (Karnaugh Map).
The complexity of a logic diagram is directly related to the complexity of the boolean algebraic expression. The truth table implementation is good but the function can be implemented in many different forms when expressed algebraically.
Well, the thing is, you can simplify any boolean expression using basic relations of boolean algebra. But this process sometimes can’t give you the most simplified version of the function because it lacks some specific rules for the prediction of the successive.
The most reliable method to simplify a function is using the map method, commonly known as Karnaugh Map or K-map. K-map can be used for up to six variables. For more variables, you can use the tabular method commonly known as the Quine-McClusky method.
K-Map (Karnaugh Map) Simplification
To simplify using K-Map first we have to know some basic rules on how to draw a k-map for two, three, and four variables. The figure given below will help you to understand that.
a) Two variable Map 
b) Three variable Map 
c) Four variable Map
Rules for K-Map Simplification
- Groups may be horizontal or vertical but never diagonal.
- Groups must contain 1, 2, 4, 8… 2n cells.
- Each group should be as large as possible and the number of groups should be as small as possible.
- Groups may overlap.
- Groups may wrap around the table. The leftmost cell in a row may be grouped with the rightmost cell and the top cell in a column may be grouped with the bottom cell.
- Groups must not contain a zero.
Let us see some examples
We will simplify a boolean function in the first example,
F(A, B, C) = Σ(3, 4, 6, 7)
Theses squares produce 1’s which belong to minterms 3, 4, 6, 7 as recognized by the above figure. So, just circle out the adjacent squares following the rules mentioned above. Now for the horizontal group, we can see that it belongs to BC column-wise and A and A’ row-wise. Column-wise we can not cancel any variable but row-wise, A and A’ cancel each other. So this group can only give us BC.
Now for the remaining two squares, we can see that they belong to B’C’ and BC’ column-wise and A row-wise. As we have canceled in the previous group we can do it column-wise, B’ of B’C’ and B of BC’. These two cancel each other. So we are left with AC’ for this group. So the final output should be like BC + AC’.
F = BC + AC'
In the second example, you will understand all the basic rules and their working. Lets see the following expressions.
F(A, B, C) = Σ(0, 2, 4, 5, 6)
As, you can see there are five minterms present in the expression. The four squares of first and fourth column are adjacent to each other therefore forms a group. In this group B’ and B cancel out each row-wise leaving C’ and A and A’ cancel out each other. So this group simplifies to C’.
The leftover 1 in the second column can be overlapped with the other square to its left so this forms another group. Now in this group C’ and C cancel out each other leaving B’ row-wise and A column-wise. So, this group simplifies to AB’.
So, the simplified function is:
F = C' + AB'
Now there is a question for you all, lets see you can solve it or not.
F(A, B, C, D) = Σ(0, 1, 2, 6, 8, 9, 10)
Try to make your own map simplification… Ans is F = B’D’ + B’C’ + A’CD’.
Product-of-Sum(PoS) K-Map Simplification
The examples which were shown above are derived from Sum-of-Product simplification. The product terms are AND terms denoted by the ORing of these terms. Sometimes it is more convenient to obtain the result in POS form. In POS form, we sum the OR terms and the product denotes the ANDing of these terms.
In simple language, we just have to circle out the 0’s of the K-Map. So where should we put these 0’s? Pretty simple, Just put it in the blank spaces after filling it with 1s.
Let us see this with the help of an example;
F(A, B, C, D) = Σ(0, 1, 2, 5, 8, 9, 10)
First, let’s mark the 1’s in the K-Map. Once we have done that mark all the blank spaces with 0 as shown in the above figure. Now group them(0s) following the rules of the K-Map.
You see, if 1’s are grouped we write it as function F.
F = B'D' + B'C' + A'C'D
But now we are grouping the 0s therefore these should be named as function F’. Therefore the result is:
F' = AB + CD + BD'
Now removing the complement of F’, we will obtain the simplified function in PoS form.
F = (A' + B') (C' + D') (B' + D)
The logic diagram for SoP and PoS simplified expressions are given below.
a) Sum of Products:
F = B’D’ + B’C’ + A’C’D’
b) Product of Sums:
F = (A’ + B’) (C’ + D’) (B’ + D’)
NAND implementation of SoP
The logic diagram of sum-of-products(SoP) can also be implemented with the help of NAND gates. Refer to the figure given below.
NOR implementation of PoS
The logic diagram of product-of-sum(PoS) can also be implemented with the help of NOR gates. Refer to the figure given below.
For more information on Map simplification, click here. Stay tuned for Don’t-Care Conditions.
Don’t Care Conditions
