welcome to lecture 11 where we continue our discussion of carom maps in this lecture we'll learn or begin to learn how to use caral maps to simplify functions and in fact to write them as simply as possible uh I like to give students a um set of guidelines or maybe you might even call it a recipe for how this can be done and so the first step in the recipe is to identify rectangular groupings of one cells these grouping must contain a number of one cells that is a power of two start with the largest groupings and proceed to uh smaller groupings remember to never include a grouping that is entirely contained in another grouping I'm sure that probably doesn't make a lot of sense now uh but in just a few moments as we begin to look at examples I believe it will so after you have identified the groupings and by the way for grouping I'll go ahead and say grouping equals a prime implicant so might as well use the more uh traditional term for that the the these these groupings that we will identify are the prime implicants now after we've identified all these Prime so after we've identified all the prime implicants The Next Step will be to identify all essential one cells now what is an essential one cell an essential one cell is a one cell that is contained in only one prime implicant so after we identify the Prime implicants in step one we uh identify all the essential one step one cells in step two in step three we identify all essential Prime implicants and an essential Prime implicant is simply a prime implicant containing an essential one cell and uh after that the fourth step is um to finish and and find all minimal sums remember that each minimal sum must contain all of the essential Prime implicants then add any other Prime implicants that are needed and and once again I definitely don't understand don't expect you to understand even a single one of these steps at this point but after we've done a number of examples I think that you'll find that this procedure is not too terribly difficult and um will will U be relatively uh easy to do so let's start off with one of the problems in your uh book um we'll look at problem five 3A and um you're supposed to find all minimal sums of products so find all minimal sums of the function F1 of a b c is equal to little m0 plus little M2 plus little M5 plus little M6 so we have minterm zero minterm 2 minterm 5 and minterm six and we want to write that function as uh compactly as possible now keep in mind that um each one of these M terms has all three variables in it so if we wrote out this function now it's not necessary to do this but I just want to make a point here if we wrote out this function in algebraic notation okay each one of these M terms will have a b and c in it so I'll go ahead and write a b c AB C AB C and ABC now m0 well remember 0 is 0 0 0 two is z 0 1 0 5 is 1 Z 1 and 6 is 1 one Z and therefore um this first term corresponding to the0 00 0 Min term is a prime B Prime C Prime for the next one we have a prime b c Prime for the next one a b Prime C and find the ab C Prime so this is the function f in algebraic notation and we uh say that this has 12 literals because we have three variables in each of the four terms and so 12 little literal appearances of the variables and we want to uh now use the Kel map to write that function uh more compactly so let's proceed as usual now we begin by saying that by noting that this is a function of three variables and there for the caral map we'll have two to the 3 power or eight cells so we go ahead and prepare the caral map and we'll put a on the vertical axis and B and C on the horizontal axis and as before we'll remember the correct way to number the different cells we have uh zero and one on the vertical axis and then on the horizontal axis 0 0 0 1 1 one and 1 Z and now the most convenient way to fill in the caral math is to go back up here to the uh decimal notation because we can pick them out real easily the zeroth Min term remember number will be this one and remember how we count we go 0 1 2 3 4 5 6 and 7 so after zero we see we have two 0 1 2 so we need to put a one here then the next one after two is five okay Zer one 2 3 4 5 so we get a one here and six is the last one and uh remember on the bottom row we go four five and then six and seven so six will go over here in this position so there's our caral map and now we're ready to begin uh with these rules that that or the guidelines that were just outlined to see how this goes now we're supposed to remember look for rectangular groupings of one cells now um and we're supposed to start with the the biggest possible groupings well the biggest possible grouping since we have all together eight cells if we had uh all ones here that would be all one big grouping but in fact of our eight cells we don't have eight one cells so there's no way to find a grouping of eight one cells and so now we go down to the next lower power of two remember eight is at 2 to the 3 power no we go down two to the second power what about four well indeed we do have four one cells in this kernel map but they are not in a rectangular grouping and therefore uh we just conclude that we have no groupings of no rectangular groupings of four one cells so now we go down to the next lowest power of two which is two to the first power or two now do we have any rectangular groupings of two one cells and the answer is that we do now I don't expect you to even see them this first time necessarily so I'll show you but uh in subsequent problems I'll give you a chance to look first before I help you but in this case we have the obvious grouping of these two uh one cells and you notice that this is rectangular grouping right here uh it's two adjacent one cells and and we have that these two together form a rectangle now if you look at this you might not see any other groupings but you need to remember as we stressed before the top edge of the caral map is to be thought of as joining the bottom edge of the carnal map and the right edge of the carnal map is must be thought of as joining the left edge of the carnal map so we actually do have another grouping and that is the grouping of this one cell with this one cell that makes another possible grouping of two one cells now let me comment carefully on what we have here notice that this second grouping that we've put down here that we've identified does overlap with the first grouping that we had so you might hesitate and think that it is not allow out however the important thing to note here is that this second grouping is not entirely contained within the first grouping if if you identify a grouping at any point in this process if you identify grouping that is entirely contained within another grouping you don't count it as a grouping it doesn't count as a prime implicant but if it merely overlaps with uh an existing grouping and has some of its on cells inside inside an existing grouping and some outside that consistent that uh pre-existing grouping that's okay and so that's why in this case we can go ahead and uh use this second grouping now um I personally like to keep a list of the Prime implicants that I identify and um uh now we get to the next uh part of this which is a little bit tricky and that is trying to figure out uh what the names are for these Prime implicants let's start with the first one we identified notice that uh that first one recall that it is this uh vertical collection of the uh last two cells here on at the extreme right of the caral map and now we're trying to find out what the name is of this Prime implicant and let me tell you that when you're looking for the name of a prime implicant you should always look for the variables that are constant in the prime implicant any variable that is changing in the prime implicant will not appear in the name the only variables that appear in the name are those that are constants so for instance what I me what do I mean by all that well this Prime implicant here this first one that we identified notice that in the top cell X is a excuse me a is equal to zero and the bottom cell a is equal to 1 since a is changing within that Prime implicant its name will not appear excuse me that variable a a will not appear in the name of this Prime implicant however B and C are both constant they both stay constant B stays constant and equal to one C stays constant and equal to zero and so those two variables will be in the name and since B is equal to 1 and C is equal to 0 this Prime implicant is the prime implicant b c Prime now you don't need to do this but I like to actually when I identify Prime implicants I like to just draw a little picture that helps me remember which prime implicant I've just identified and so uh again you won't find this in the book and it's not necessary for you to do it but I like to do it because it you'll see in this problem it's not too important but in later problems where we have functions with many prime implicants I find it helpful to be able to to look at these little pictures I think you'll see see later what I mean so anyway uh the picture for this first Prime implicant is B this the first Prime implicant is BC Prime and here's the picture for it now let's try to identify the second prime implicant that we had and that was the one that contains uh in fact we can go ahead and draw the picture here the one that contains this one cell and this one cell now you might think for for a moment and ask yourself well what variable is changing and the answer is the variable B notice that in this one cell b is equal to zero and in this one cell b is equal to 1 so since B is changing it will not appear in the name for this Prime implicant however a is constant and equal to zero in these two cells C is constant and equal to zero so the name of this Prime implicant is a Prime C Prime now we look to see One Last Time are there any other Prime implicants with two cells two one cells and uh the answer is no so now we move down to Prime implicants with one cell and now we can't include anything that is entirely contained within a pre-existing Prime impant so for instance uh here is a you know a single one cell but it is already contained within a Prime C Prime so we can't count it likewise this one is this one's actually contained within two existing uh Prime impant so we can't count it and this is counted within the existing Prime implicant BC Prime so we can't count it as a prime implicant however this one cell is not contained within within any pre-existing Prime applicant and therefore we do count it so I'll draw the picture and um just put a circle there corresponding to this and now we need to find the name for that and since uh of course since it's just one cell no variable is changing and therefore all three variables will appear in the name and finally since a is 1 and B is zero and C is one this is a b Prime C so now we have listed all of the Prime implicants in this problem and that concludes uh steps one and two now we we need to figure out which of these Prime implicants are essential Prime implicants and remember an essential Prime implicant is one that contains an essential one cell and what is an essential one cell it is a one cell that is contained with in only one prime implicant so let's go back up to the caral map and we'll put an asteris in every essential one cell that we observe so let's start maybe um with this one at the upper leftand corner and we ask is this one cell an essential one cell and the answer is yes because it is contained only within the prime implicant a Prime C prime it is not contained within any of our Prime implicants and therefore this is an essential one cell Let's uh move over to this one at the upper right hand corner is this one cell essential and the answer this time is no this cell is contained within two of our Prime implicants is contained within BC Prime but it's also contained within a Prime C Prime so this is not an essential one cell now let's go to the next row what about this is this contained within only one prime implant and the answer is yes it's only contained in the prime implicant a b Prime C so this is an essential one cell and finally if we look at the lower right hand corner is this an essential one cell and the answer is again yes it is only contained within BC Prime so this is an essential one cell and now we can uh decide what the essential Prime implants are remember essential prime implicants or prime implicants that contain at least one essential one cell uh our first Prime implicant BC Prime it's the one over here and if we look up at the map yes it does contain uh an essential one cell so BC Prime is an essential Prime implicant uh what about a Prime C Prime well it contains this one cell in the upper leftand corner this essential one cell in the upper leftand corner so it is indeed essential and finally if we check the U prime implicant a b Prime C it contains this essential one cell and therefore it is also essential and so now we're ready to complete this problem now um I'll put minimal sum and then after the word sum I'll put s because some functions have more than one minimum sum that is they have several different ways that are equally compact uh or several different ways of writing them in sum that are equally Compact and some functions have only one minimum sum and we'll see which is the case uh here so we have F uh that was yes F1 of ABC equals now every is it is really crucial to to note that every minimal sum must contain all of the essential Prime implicants just think of the word essential means that they are essential they are absolutely they they must be included and then after you have what's essential you'll add anything else um that you need to add so you'll see what I mean right now so the essential Prime implicants are b c Prime and then or that with a Prime C Prime and or that with a B Prime C now how do we figure out if we need anything else well what we do uh what I like to do is to go up to the carom m now and we check what we have so far BC Prime now we remember right here BC Prime are these two cells on the extreme right side of the caral map so that means that by including BC Prime in my expression I have accounted for those two cells so I'll shade them in now the next one a prime C Prime by including that in my sum I have account wanted for this cell at the upper leftand corner and also the cell over here in the upper right hand corner but it's already shaded so I don't need to shade it again and finally by including a b Prime C remember that's this cell right here so now I have accounted for this cell so now I asked myself are there any more cells that need to be accounted for and the answer is no and and therefore I am done and this is our final answer now sometimes after you have uh written down all the essentials one cell excuse me the essential Prime implicants you'll still have some other cells that need to be accounted for and then we might have several different options but in this case uh when we once we accounted for all the essential Prime implicants there were no more cells that needed to be considered so this is our answer there's only one minimal sum in this case and notice that we do have a significant savings here in our first expression we had 12 literals and in this expression we have 1 2 3 4 5 6 7 literals so um you can think of this in the following way one reason that this is uh a practical thing to do is that if we wanted to do this in Hardware if we wanted to realize it we would need uh four three input uh and Gates and one four input or gate but here we would need just one three input or gate and two two input and Gates and one three input and gate to implement this in Hardware so uh this is one of the reasons that we want to learn this procedure for finding minimal sums and then later minimal products so that's our first example our first complete example of how to use a caral map so now let's move on to another example we have um 5.3 C maybe we should do B first B is a little bit simpler and then we'll go to C so let's go to 5.3 B and in this one we have F2 of d e f is equal to the sum of the end terms 0 one 2 and four and we want to again find all minimal sums now by the way before I go to this problem I would like to suggest that you do one last thing I have simply stated here that this expression that we derived this this expression right here I said that it is a valid expression for F1 which we have up here I strongly encourage you to try to verify that that is true in other words okay here you have a an expression for F1 and up here you have the minterm expansion for F1 you should know now how to take any expression for a function and find the minterm expansion of the function in this case it would be very easy you just need to and the first term with a or a prime and and the second term with b or B Prime and then eliminate any redundancies and you'll get the minterm expansion so I strongly encourage you to try that and to verify that if you do that this expression here will yield back this minterm expansion which prove will prove to you that this uh expression here really is equal to the same function F1 that we started up with up here I again I strongly encourage you to do that but now for um for this uh new problem again if we wished uh we could go ahead and write out this function algebraic form I want to stress that it's not necessary to do that uh unless you want to check your work or unless you just want to really show the viewer uh the savings that is occurring from simplification so uh this is not necessary but uh again I'll show it here so we'll have f 2 of d e f equals and we see that we have four M terms and of course each M term must have all three variables so we'll have d e f d e f d e f and D EF uh 0 is 0 0 0 1 is 0 0 1 2 is 0 1 0 and four is one0 0 so we get the first term is D Prime e Prime fpre D Prime e Prime f d Prime e fime and finally d e Prime fime so as was the case in the previous problem we have 12 literals and let's see how much simplification we'll have this time once again we have a function with eight with three variables and so we'll have a caral mat with 2 to the 3 or eight cells the first variable is D so we'll put that on the vertical axis E and F are the second and third variables so we'll put those on the horizontal axis we'll use our usual way of numbering the kernel map and now once again as was the case before or when we actually want to put the ones in the carnal map it's easiest to go back here to um the decimal notation and to recall again Zer 1 2 3 4 5 6 7 so zero is this first cell one two we don't have three but we do have four and that will be the caral map for the function F2 and now let's go through our steps again once again remember first step is to find the prime implicant okay we have a total of eight cells do we have any groupings of eight one cells certainly not because there are only four one cells present so no groupings of eight one cells this go down to the next power of two which is four do we have any rectangular groupings of four one cells the answer again is No we do have four one cells here but they don't fall in a rectangular grouping now notice uh let me just make sure you understand how they could if this one right here if instead of being right there it were right here in this position or uh well let's say that if this one right here were in this position then this would be a grouping a rectangular grouping of 4 One cells or if this one right here were instead up here then the top the entire top row would be a grouping a rectangular grouping of four one cells but in this case with the distribution of one cell is like this that we see here we don't have a rectangular grouping of four so now we drop down to to the next power of two which is two and now when we're looking for groupings of two one cells we have several options now I'd like to suggest to students and this is this is not hugely important but I suggest to students that when they have a number of options they always start with the option that is the hardest to see so that they don't forget it later and so that's what I'll do now when I look at this kernel map I see that one grouping of two one cells that's sort of tricky to see is this one there are several groupings of two one cells but that one is the one I think is the trick is to see and therefore I'll take it first so I'm going to go ahead and draw my picture and when you do these pictures certainly don't take if you if you even choose to do the pictures as I do don't take much time with them they don't need to be perfect drawings they just need to help you remember uh what prime implicants are where so I'll draw that rough picture and now I need to figure out figure out the name for that Prime implicant and uh I hope that you will see that D is constant in that Prime implicant so it will appear in the name but e is not constant e is equal to zero in this cell on the left and E is equal to one and this cell on the right so e will not appear in the name but f is constant and equal to zero so D is constant and equal to zero f is constant equal to zero so this is D Prime fime and that's our that's uh one prime implicant uh of size two now I don't see any more Prime implicants of size two that are tricky so let's do the ones that are obvious and the first one that's obvious is this one and again notice it is not although it does overlap with a prime applicant we already have is not entirely contained within it so that's okay I'll draw the rough figure for this one and now you might take a moment to see if you can name it yourself and then come back when I uh now try to name it I observe that the value of D is changing it's equal to zero in the top cell and one in the the bottom cell and therefore D will not be part of this Prime implicant however E and F are both constant and fact both are equal to zero so this is e Prime F Prime and now I look at the caral map again and I see that there's another grouping of two one cells and it is this one and again that's not although it does overlap our two previous Prime implicant is not entirely contained within either one and therefore we need to have it and so well we now draw the rough figure for it and let's uh you should now turn off the video for a moment and try to figure out the U name of that Prime applicant well uh as I look at that I see that D is constant and equal to zero so that means that since D is constant it will be in the name and since D is equal Zer to be D Prime I see that e is also constant in those two cells and equal to zero so we'll have e Prime F however is changing is equal to zero in this cell on the left right here and F is equal to 1 in this cell and so so since f is changing it will not appear in the name now having done this I see no more groupings of two one cells and so now I move down to the next level are there any groupings of one one cell well there are certainly one cells there are single one cells but none that are not already contained within one of the prim implicants we've already identified and therefore we're done these three prime implicants that we have identified are the only Prime implicants for this problem so now we need to ask ourselves what are the essential Prime implicants and to find the essential Prime implicant remember that the procedure here is to begin by finding the essential one cells is this one cell essential clearly not because in fact it's contained within all three of our existing Prim impants and remember to be essential a one cell must be contained within only one Prim so this one cell is not essential however this one is so we'll put an as here and this one is essential so we put an asteris here and finally this one is also essential so we put an as risk there now that we've identified the essential one cells we know that the essential Prime implicants are prime implicants that contain an essential one cell so let's ask about the first one is it essential yes because uh it contains this essential one cell here in the upper right hand corner so D Prime fime is essential what about e Prime fime yes it contains this essential one cell so it is essential and what about D Prime e Prime well it contains this essential one cell so it is also essential and now we move as we did before to the minimal sums and uh so we this the the function name here is FS2 we have FS2 of d e f and remember we always start with what is essential so we must put down D Prime F prime or E Prime FP prime or D Prime e Prime and now we want to see if anything else is needed and so let's uh look at what we've accounted for first D Prime fime by including D Prime fime in our minimal sum we've taken care of this one cell and this one C you can see now maybe why the figures are a little convenient to have by including e Prime fime we have looked at uh We've considered these two one cells and by considering D Prime e Prime we have these two one cells and so now we ask the question are there any remaining cells that we've not accounted for and the answer is no and therefore as in the previous case we have only one minimal sum and it is this and in this case you see that there are six literals so we've gone from an expression for F2 containing 12 literals to an expression containing six literals and once again I encourage you to take this expression we've just found find the um minterm expansion for it and you will find that it matches what we have here at the top so this is expression these expressions are equivalent however this is the uh of course a much more compact way of writing the function F2 let's have one more example in this lecture we'll go back to one we were going to do earlier which is 5.3 B excuse me c so in this function in this case we have F3 of r s t is equal to r t prime or RP Prime S Prime or RP Prime s and we notice that that has six literals and our job once again is to find all minimal sums this is a function of three variables so we will have two to the3 power cells in our caral map or eight we'll have r on the vertical axis and S and T on the horizontal axis number this as usual now um this one is just a little bit trickier to fill in because we don't have a minterm expansion here but I believe that we'll be able to do this as long as we're patient so let's look at the first term r t Prime well first of all since we have an R rather than an R Prime we know that we're going to be in the second row of the carinal map because that's where R is equal to 1 and T Prime means that t is equal to zero now T is the if we look up above T is the second number so we're going to get a one here and a one here and notice that if you if you looked at those two cells as a grouping uh you would notice that s is changing so s would not appear in the name but R is constant for those two cells T is constant for those two cells R is constant equal to 1 T is constant equal to zero so indeed the name would be RT T Prime now having seen that I hope that you can fill in the rest of the ones for the rest of the term so I uh encourage you to stop the video now try to fill in the caral mat for the remaining terms and then we'll look at these together okay I hope you had good luck with that and so now let's finish this up RP Prime S Prime since we have RP Prime we know we're on the top row of the caral map and S Prime says s is equal to zero so we have this one and this one notice that R is zero and S is zero but T is changing and so T is not in the name and finally RP Prime s means that we have um R is equal to Z and S is equal to 1 which gives us those two ones right there now we uh now that we have the um caral map for this function we're ready to uh do this problem so as usual the first step is to find the prime implicants we have a problem with uh eight cells so we first ask are there uh any rectangular groupings of eight one cells the answer is certainly no because we only have six one cells present so let's go down now to groupings of four one cells well indeed there are rectangular groupings of four one cells here and uh I I feel very confident you see one for sure and it is the four ones at the top of the carinal map but there is another grouping of four one cells and you need to uh another rectangular grouping of 41 cells and you need to be aware of it so since this a trickier one I'll handle it first we can group together these four one cells excuse me those two one cells with these two one cells if we remember that the right and left edges of the caral map are connected and that will give us a grouping a rectangular grouping of four one cells so that's one that's easy to miss and you want to make sure not to miss it so there it is and now we need to ask ourselves what is the name for this Prime implicant well does it have an r in it no R is equal to zero along for the top two cells and one for the bottom two cells so R is not in the name what about s s is equal to zero for these these two cells and it's equal to one for these two cells so since s is changing it's not in the name either but what about t t is equal to zero for these two cells and T is equal to zero for these two cells so in fact the name of this Prime implicant is simply T Prime and we have one more grouping of four one cells and that's the obvious one here along the top and what will be the name of this well if if you check those four cells along the top you see that s is changing and T is changing but R is constant equal to zero so this is r PR e e e e e e e