Google
 
Site navigation: [ Home | Theory | Java | About ]

Karnaugh Maps

4.2.4 simplifying -
Alternative approach

 

 

 

 

If you followed closely the algebraic stuff you would probably spot that the first two terms simplify to not A and the last two to B. Since we can repeat the middle term, we get the solution not A + B.

 

 

 

In the horizontal, B is eliminated because it is both a zero and a one within the pairing.

not A is left because the row is A = 0

The vertical pair work in a similar way.

 

 

 

This special type of binary sequence is known as a Grey code.

 

Oops - this is a three - variable map and Grey is mis-spelt.

Apart from that the diagram is perfect.

 

 

 

 

Sharp observers, such as yourself, will notice that this is the car alarm system again.

Therefore we are not surprised to see it simplify to the same expression.

Next we see how these expressions can be converted to circuits using logic gates.

 

A Karnaugh map is a visual representation of an algebraic expression which allows us to easily spot the patterns we were looking for above, using algebra. They can typically use 2, 3 or 4 variables - but since the IB Guide limits truth tables to 3 inputs we need not consider 4-variable K-maps.

This first example shows a K-map with two variables:

On the map, we try to find pairs of 1's that are horizontal or vertical (we have one of each pair in the above map).

K map with adjacent pairs of ones circled

When the map is expanded to 3 variables, then one edge has 2 of them and they are given in the sequence 00 01 11 and 10 (or any other sequence where only 1 bit changes at a time) - not the more usual binary "counting" sequence.

three-variable K-Map

We can also pair by "wrapping around" the edges of the map - effectively the k-map is on a cylinder.

Back to top

related: [ Topic 4 home | previous:algebra | next: circuits ]

K-map is an abbreviation for Karnaugh map (you probably spotted that already).

 

Here is a link to a site about K-maps and one of my all time favourite computer books.

(Click on the images for greyscale versions if you need them).


 
The site is partly financed by advertising revenue, partly by online teaching activities and partly by donations. If you or your organisation feel these resouces have been useful to you, please consider a donation, $9.95 is suggested. Please report any issues with the site, such as broken links, via the feedback page, thanks.

Questions or problems related to this web site should be addressed to Richard Jones who asserts his right to be identified as the author and owner of these materials - unless otherwise indicated. Please feel free to use the material presented here and to create links to it for non-commercial purposes; an acknowledgement of the source is required by the Creative Commons licence. Use of materials from this site is conditional upon your having read the additional terms of use on the about page and the Creative Commons Licence. View privacy policy.

Creative Commons License


This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 2.5 License. © 2001 - 2009 Richard Jones, PO BOX 246, Cambridge, New Zealand;
This page was last modified: October 28, 2013