Rumination # 3 Karnaugh Maps

Hello my fellow seekers of the Boolean light. Tonight's post will be about one of two main methods of simplifying functions, the Karnaugh map. Simplifying a function has the advantage of minimizing costs and the number of gates neccesary for realization of a circuit, these methods will also probably figure predominantly in your tests that might be coming up soon, so without further avail, here they are:

-Karnaugh Map:

http://www.google.com/imgres?hl=en&sa=X&biw=1680&bih=925&tbm=isch&prmd=imvnsab&tbnid=gBrasygvvTvOvM:&imgrefurl=http://www.ee.surrey.ac.uk/Projects/Labview/minimisation/nak.html&docid=Fix7J9LtJAWa4M&imgurl=http://ww 

An n-variable K-map has 2^n cells with each cell corresponding to a
row of an n-variable truth table. They are labeled with the corresponding truth-table row. K-map cells are arranged such that adjacent cells correspond to truth rows that differ in only one bit position (logical adjacency).  Switching functions are mapped (or plotted) by placing the function’s
value (0,1,d) in each cell of the map.


-Simplifying using a K-map:

http://www.tech-faq.com/karnaugh-map.html 

K-map cells that are physically adjacent are also logically adjacent.  Also, cells on an edge of a K-map are logically adjacent to cells on the opposite edge of the map. If two logically adjacent cells both contain logical 1s, the two cells can be combined to eliminate the variable that has value 1 in one cell’s label and value 0 in the other. This is equivalent to the algebraic operation, aP + a'P =P where P is a product term not containing a or a'

-Simplification Guidelines for using K-maps:


 •Each cell of an n-variable K-map has n logically adjacent cells. Cells may be combined in groups of 2,4,8,…,2^k
• A group of cells can be combined only if all cells in the
group have the same value for some set of variables.
• Always combine as many cells in a group as possible.
This will result in the fewest number of literals in the term
that represents the group.
• Make as few groupings as possible to cover all minterms.
This will result in the fewest product terms.
• Always begin with the “loneliest” cells.


-General Terminology
• An implicant is a product term that can cover minterms of a
function.
• A prime implicant is a product term that is not covered by
another implicant of the function.
• An essential prime implicant is a prime implicant that covers
at least one minterm that is not covered by any other prime
implicant.
• A set of implicants is said to be a cover of a function if each
minterm of the function is covered by at least one implicant
in the set.
• A minimal cover is a cover that contains the smallest number
of prime implicants and the smallest number of literals


-Sample simplification.

http://moodle.ucs.louisiana.edu/file.php/12393/chapter_3SP12.pdf 

5  Minterms: {A'B' C, A' BC', A' BC, ABC', ABC}
5  Groups of two minterms:  {A'B, AB, A' C, BC', BC}
1  Group of four minterms:  {B}
Prime implicants:  {A'C, B}
Cover = {A' C, B}
MSOP (Minimum Sum Of Products)  = A' C B


As you can see, this is very simple to do, and with a few problems of practice, you will have no trouble simplifying functions using this method. Tune in next week for the Quine Mckluskey Method of simplification!!