What is a K-Map
A K-Map or a Karnaugh map is a mathematical technique in digital electronics that is used for the simplification of logical functions. Every circuit in digital domain is defined by a logical functional equation. If this equation is in its simplest form then the circuit can be synthesized using the minimum amount of hardware. This reduction in hardware leads to many advantages in terms of speed, cost, size, power saving, performance etc and therefore makes the logic simplification technique such as a K-map very important from a designer’s point of view.
The K-Map technique is based on the use of the Boolean identity of A + A’ =1 for logic simplification. A table is mapped containing 2n cells where n are the total number of input variables. Each cell represents a different min term and cells are placed in such a way that adjacent cells vary from each other in terms of only one variable going from true to compliment value or vice-versa.
A K-Map illustrating the placement of cells for four input variables A, B, C, D is shown below:
The min terms for which the output is 1 are filled in to the table and then these 1’s are combined using the rules of adjacency i.e. 1’s are allowed to be combined from top to bottom and left to right. For a combination of 1’s, the terms which are varying from their true value to their compliment value are eliminated while the terms that remain constant in the combination are written as the final Product term. In this way, every combination of 1’s gives a Product term and the addition of these terms gives the minimum sum of Product logical equation for the digital circuit under analysis.
By forming the largest possible group of 1’s and by exhausting all the 1’s in the table, a designer can make sure that the final expression is the most simplified version of the logical function possible. This is not often the case in using Boolean algebra as a reduction technique because of an ever present chance in it of a further simplification possible in the expression to skip the eye of the designer. Mapping therefore is a more reliable and error free reduction technique. Also being a procedure oriented technique, it can easily be implemented in a computer by coding which makes it suitable for complex digital circuitries containing hundreds and thousands of variables that need to be analyzed for logic simplification.