ECES 281 Bill's Recitation Notes Recitation #2, 09/11/00 Overview The only thing I have to go over in this recitation is practice on K-Maps. The rest of the time will be devoted to questions. Note about K-map notation Since I'm going to do these in ASCII, I can't very well circle areas, so what I am going to do is make each K-map space at least two characters wide and the first character will represent the value (1,0,X) and the second will represent the circled group (_ is blank, a lower case letter is for a circle). So for the following two variable K-map: \A B | 0 | 1 | ---|---|---|- 0 | 0_| 1_| ---|---|---|- 1 | 1_| 1_| ------------ Suppose I wanted to circle the right column and the bottom row. I'd do the following: \A B | 0 | 1 | ---|---|-----|- 0 | 0_| 1a | ---|---|-----|- 1 | 1b| 1a,b| -------------- I know that's not the nicest or most elegant way, but I like ASCII, am not particularly fond of HTML and graphics editing, and want everyone to be able to read these files with a minimum of fuss. Everyone should be able to handle ASCII (unless you're not using a computer). 4 variable K-Map example Using the following K-map: \AB CD | 00 | 01 | 11 | 10 | ---|----|----|----|----|- 00 | 1_ | 0_ | 1_ | 1_ | ---|----|----|----|----|- 01 | X_ | 1_ | 0_ | 0_ | ---|----|----|----|----|- 11 | 0_ | 1_ | 0_ | X_ | ---|----|----|----|----|- 10 | 1_ | 1_ | 1_ | X_ | ------------------------ Now, the way which someone who is not remembering everything about K-Maps might do this one is as follows: \AB CD | 00 | 01 | 11 | 10 | ---|----|----|----|----|- 00 | 1a | 0_ | 1b | 1b | ---|----|----|----|----|- 01 | Xa | 1d | 0_ | 0_ | ---|----|----|----|----|- 11 | 0_ | 1d | 0_ | X_ | ---|----|----|----|----|- 10 | 1c | 1c | 1c | Xc | ------------------------ which would result in the following boolean formula: (A'B'C')+(AC'D')+(CD')+(A'BD) which, using only the two input gates which we have been using, will result in 10 gates (plus 4 NOT gates). The following way: \AB CD | 00 | 01 | 11 | 10 | ---|-----|----|-----|-------|- 00 | 1a | 0_ | 1b | 1a,b | ---|-----|----|-----|-------|- 01 | X_ | 1d | 0_ | 0_ | ---|-----|----|-----|-------|- 11 | 0_ | 1d | 0_ | X_ | ---|-----|----|-----|-------|- 10 | 1a,c| 1c | 1b,c| Xa,b,c| ---------------------------- will result in the following formula: (B'D')+(AD')+(CD')+(A'BD) which, using only the two input gates which we have been using, will result in 7 gates (plus one 3 NOT gate). In case it is not appearant why the wrap around is permissable, just consider the numbering scheme. There is nothing magical about 00,01,11,10. There is one important way in which this order goes, but nothing magical about this order. The important fact is that from one to the next, only one varaible changes (including from beginning to end). So there is no reason why you couldn't roll them and use 01,11,10,00; 11,10,00,01; or 10,00,01,11 instead (aside from convention and potentially confusing the person looking at it). There's also nothing magic about that order, you can make it backwards too, as 11,01,00,10. There are more, but they really don't matter. It's just the point that you can wrap around because there is change in only one variable. Now, you may say, who cares, why not just use a 3 or 4 input gate, then it would equalize the number of gates. The reason is that the whole point of K-Maps is optimization, and the lesser number of inputs, the cheaper and faster the gate. In the things that you will be doing in this class and other intro classes, it probably won't matter which you use. For those of you who are EE's (definitely) and CompE's (maybe), you'll need to concern yourself with even savings appearantly this small. For the rest of you, A) it should be a question of style, and B) you may run into test questions only allowing you to use specified gates (type and number), so don't just ignore this. There is also another method of using K-Maps. The form above is to create a sum of products form. You can also use them to create a product of sums form. For this, you would circle the 0's instead of the 1's. See the following: \AB CD | 00 | 01 | 11 | 10 | ---|----|----|----|-----|- 00 | 1_ | 0c | 1_ | 1_ | ---|----|----|----|-----|- 01 | Xb | 1_ | 0a | 0a,b| ---|----|----|----|-----|- 11 | 0b | 1_ | 0a | Xa,b| ---|----|----|----|-----|- 10 | 1_ | 1_ | 1_ | X_ | ------------------------ This would yeild the following formula: (A'+D')(B+D')(A+B'+C+D). First note that there is a one member circle. This is not something that is good to get, but there can be no help for it with this K-Map. Secondly, you might wonder how exactly this is working. What this way of using the K-Map does is look at it backwards. With an OR, anything that was a 1, will remain a 1. With an AND, anything that was a 0, will remain a 0. So, for the sum of products form, we take an OR of AND products, so we create the AND products to cause the groups of 1's and then the OR's will place them all together as the final result. With a product of sums, we take an AND of OR sums, so we must create groups of 0's with the OR's sums, and then the AND's will place them and leave the rest as 1's. So where before we were looking at a circled group and thinking "What AND formula will make all of these 1's?", now we must look at a circled group and think "What OR formula will make everything but these 1's?" It takes some time to get used to, but is actually not really different.