~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ UIT2201: Notes on Use of Karnaugh Maps by H. W. Leong (Apr 2002) ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ [last updated: March 2012, that's 10 yrs later, Wow!] Logic Simplification using Karnaugh Maps: ========================================= In the lecture notes, we saw that any logic function can be obtained directly from the truth table. The obvious method is to give the logic function in terms of each row in the truth table for which the output function f is a 1. Each row is the "product" of the input variables (A if the entry is a 1 and ~A if the entry is a 0). Example of Logic Simplification: -------------------------------- ----------- AB | S T ----------- 00 | 1 1 S = ~A*~B + ~A*B + A*~B (5 gates) 01 | 1 1 = ~A*(~B+B) + ~B*(~A+A) 10 | 1 0 = ~A*1 + ~B*1 11 | 0 1 = ~A + ~B (1 gate) ----------- In the above example, the direct method gives us S = ~A*~B + ~A*B + A*~B The above logic function is correct, but it requires 5 gates (AND,OR) to implement, not counting NOT gates. We can simplify it to S = ~A + ~B as shown above and it will take only 1 gate to implement. Applying this simplification process to T, we have: T = ~A*~B + ~A*B + A*B (5 gates) = ~A*(~B+B) + B*(~A+A) = ~A + B (1 gate) The above simplification process can also be applied to functions of more inputs, but it will be tedious. There is better way to do it. 2. Karnaugh Maps ---------------- One technique developed by computer scientists and engineers to help the logic simplification process is to use something called Karnaugh Maps. Karnaugh Maps is a way to represent the entries of the truth table in a special way so that the simplification process is made easy. For two variables, the Karnaugh Map (called K-Map for short) is drawn as shown below. Each cell in the K-Map represents a row in the truth table and is labelled by its corresponding binary code for the input variables. A \B 0 1 +------+------+ 0 | 00 | 01 | Top Row: 00+01=0X Logic Function: ~A | | | Bottom Row: 10+11=1X Logic Function: A +------+------+ Left Column: 00+10=X0 Logic Function: ~B | 10 | 11 | Right Column: 01+11=X1 Logic Function: B 1 | | | ("X" to indicate variable that was "dropped") +------+------+ In the Karnaugh Map above, if we group together the two cells of the top row, namely the ones labelled 00 and 01, it is equivalent to saying ~A~B + ~AB = ~A*(~B+B) = ~A*1 = ~A. Equivalently, we represent that as (00+01)=0X where we use the "X" to indicate that the variable B has "dropped off". Similarly, combining any other two adjacent cells will give us: eg: 10+11=1X or A~B + AB = A 00+10=X0 or ~A~B + A~B = ~B 01+11=X1 or ~AB + AB = B To use K-Maps to aid in logic simplification, we first fill the K-Map: for each row with a 1 in the truth table, we label the corresponding cell in the K-Map with a "Y". Of course, we also label all the cells with a "N" to correspond to those rows in the truth table with a "0". We illustrate for the function T above. \ K-Map for function T A \B 0 1 +------+------+ 0 | 00 | 01 | To simplify, | Y | Y | we can combine 00 and 01 --> 0X (~A) +------+------+ we can combine 01 and 11 --> X1 ( B) | 10 | 11 | So, the function is simplified to 1 | N | Y | T = ~A + B +------+------+ After filling up the K-map, we have completely described the function T (look at all the squares labelled with "Y"'s.) To simplify, we now look for some adjacent cells with a 1 to combine. Thus, we can combine 00 and 01 --> 0X (~A) we can combine 01 and 11 --> X1 ( B) T = ~A + B. The advantage of K-maps is that simplification of the logic circuits or functions can be done by looking for neighbouring squares to combine. This is a lot easier than looking at the boolean functions!! For functions with 3 variables, there are 8 rows in the truth table and also 8 squares in the K-maps. Therefore, it is more complicated. The "unfilled" K-map for 3 variables {A,B,C} is shown below. \ A \BC 00 01 | 11 10 +------+------+------+------+ 0 | 000 | 001 | 011 | 010 | | | | | | +------+------+------+------+ | 100 | 101 | 111 | 110 | 1 | | | | | +------+------+------+------+ Note the special arrangement of the columns for BC that goes "00" "01" "11" "10". This special arrangement is IMPORTANT and necessary so that every two adjacent square differs from one another by EXACTLY one variable only! Also, we consider the last columns to "wrap around" so that the last column is also a neighbour of the first column. Consider the following functions. --------------- ABC | P Q R --------------- 000 | 1 1 1 P = ~A~B~C + ~A~BC + A~B~C + A~BC + ABC (14 gates) 001 | 1 0 1 = ~A~B + A~B + AC 010 | 0 1 0 = ~B + AC (2 gates) 011 | 0 0 1 100 | 1 0 1 Q = 101 | 1 0 1 110 | 0 1 1 111 | 1 0 1 --------------- \ K-map for the function P A \BC 00 01 | 11 10 +------+------+------+------+ 0 | 000 | 001 | 011 | 010 | (a) Group 000 + 001 --> 00x | Y | Y | N | N | 100 + 101 --> 10x +------+------+------+------+ Then 00x + 10x --> x0x --> ~B | 100 | 101 | 111 | 110 | (b)Group 111 + 101 --> 1x1 --> AC 1 | Y | Y | Y | N | +------+------+------+------+ Visual inspection of squares "around" 000 allows us to group the four squares on the left, which correspond to the simplification (a) above. Also for the remaining square 111, we can combine with its neighbour 101 to give simplification (b) above. This visual method of simplification is easier to do. For functions with 4 variables, there are 16 rows in the truth table and also 16 squares in the K-maps. Therefore, we will get a 4x4 K-map, with 2 variable for the rows and 2 variables for the columns. An "unfilled" K-map for 4 variables {A,B,C,D} is shown below. \CD AB \ 00 01 | 11 10 +------+------+------+------+ 00 | 0000 | 0001 | 0011 | 0010 | | | | | | +------+------+------+------+ 01 | 0100 | 0101 | 0111 | 0110 | | | | | | +------+------+------+------+ 11 | 1100 | 1101 | 1111 | 1110 | | | | | | +------+------+------+------+ 10 | 1000 | 1001 | 1011 | 1010 | | | | | | +------+------+------+------+ Again, we notice the "special" arrangement of the rows and the columns. Also every two adjacent squares differs by at most one variable. And we "wrap around" the rows as well as the columns! Eg: the four corner squares are adjacent and can be combined together. In fact, 0000 + 0010 + 1010 + 1000 = x0x0 = ~B~D Actual examples of working with this may be given in tutorials. ------------------------------------------------------------------------ LeongHW, Apr 2002 (for USST01, now UIT2201)