In the previous post, you learned about representing boolean functions as canonical sum of product and canonical product of sum; then you can minimize them in to sum of product form or product of sum form by applying boolean algebra rules.
The boolean algebra rules are difficult as the complexity of circuits grow. You cannot do a boolean minimization when there are huge truth table involving several variables. Therefore, Karnaugh maps or K-maps minimize boolean expressions with the help of graphical representations.
What is K-Map?
The Karnaugh map was invented by American physicist Maurice Karnaugh in year 1953. Hence, the name. It is a simple representation of truth table in a matrix form. For boolean minimization, we need two simple operations which are reducing the terms of the function, and eliminating variables from terms if possible.
Two Variable Map Example
Suppose we have two variables – A and B. They perform an AND operations. The truth table will show all possible input combinations as follows.
Each of the cell in the K-map represent a minterm and the two variables are represented along the vertical and horizontal direction. The difference between adjacent cell is always 1 bit – both in vertical and horizontal direction.
Vertically , A’B’ and AB’ has A variable changing from 0 to 1, that is A’ to A. Horizontally, A’B’ and A’B have variable B changing from B’ to B, that is. from 0 to 1.
Grouping Of Cells
Now look at the truth table, there are minterms that gives 1 as the output. These are shown the following figure.
Once you have marked all the cells with output 1, you can group them into 2s, 4s or 8s. If we count only cells with 1 then the function is F = A’B + AB.
To minimize this function simply group the cells and eliminate A which is different vertically and keep B because it same vertically. In other words, vertically, A + A’ = 1. Our solution is B.
Also, If you look at the truth table, the output F column matches column B.
In the next few posts, we will explore more complex form of Karnaugh maps such as 3-variable map, 4-variable map.
