Hi. In previous parts of this digital Logic tutorial design series, we've taken a look at basic, uh, digital logic gates all you need to know about those and uh, digital Boolean logic and De Morgan's theorems. And then we switched over to designing combinatorial logic circuits and we went through all the end. the community laws and the associative laws, distributive laws, and stuff like that.

So I'll link in those videos if you haven't seen it in that video. I promised I'd Show you a way to actually do digital logic reduction not using any algebra at all, but using a visual method called Kano Maps. Let's take a look at it. It's pretty magical.

Let's say we've got our truth tape of our logic function that we want here. Okay, and we've got uh, three inputs here A, B, and C, and we've got one output we'll call X And of course, with three inputs, that gives us a eight different uh, binary states that we can have on the input. So we potentially have eight different output functions here and we can write this as an algebraic expression. Pretty easy.

We can use sum of Products as we learned in the previous video. Sum of Products is we find all of the ones here on our output and then we write that as a product expression because it's a sum of products. Okay, so the product expression here is not a like this because it's a zero and uh one, B is a one. so we just call it B and C is a zero so that is not C like that and we've got more than one one on the output here.

so we have to sum the different products. so we do the products of the other one that we've got here which is A like that and B is a Uh one. So it's just B and C is a zero here. so that is not C like that and that is our expression.

So X equals that. So that's our algebraic logic expression for that function. But we want to simplify this because if you try and Implement that with just discrete Gates you you'll find Yeah, you can do it, but you'll end up with too many gates now. Of course we can solve this algebraically, but who likes solving algebra equations? Yeah, yeah, no, but let's let's do it anyway.

Okay, so this how we find that B is the same here. Okay, so we can take out B as a separate function. Then we've got C is the same either side or sorry not C is the same so we can actually take out that. So it's B and C there so we're left with we'll put a bracket in there like that and we're left with not A and A So it's not A like that.

plus A. Okay, so that is. Uh yeah, this is algebra stuff. It doesn't matter whether you're doing mathematical algebra or digital algebra like this.

The rules are the same. Now this not a plus A Here we can actually, uh, simplify that. No problems whatsoever because not a plus A Is it it. It's always one.

So that gives us B not see and then one like that, right? Or we can put one in Brackets like that. And because this is like and one well like, we could put the dots in there Like some people like putting the dots in there like that you don't have to. you can leave it out. It's implied that it's an and uh function.

So if you and B not C with one, well, that just equals B not C like that. We've simplified this algebraic expression to just be and not C easy. So we can just draw that as an and gate like that and we could go B. And of course C is not like that.

So we need to put an inverter and C like that and that's our output. X and you'll notice that A It doesn't matter what A is. Um, we always get that output function is only dependent upon B and C And if you don't believe me, you can do this by inspection of the the table right? Our outputs one here. Okay, it's when B is B and C is one zero.

B and C here is also one zero and it doesn't matter whether A is a zero or a one. In this case, you get a one. So that's why A does not matter. It's you only rely upon B and C to give you the output X there.

But if we implemented this function up here with Gates, we'd be actually using A because A is in our expression there. So we can actually draw this original function here and see how many gates we've actually saved. So here it is this original algebraic expression. If we just implemented that directly with Gates, we would end it up with two, three input and Gates and or Gates and three inverters like this.

and we have now actually simplified that to a two input and gate and an inverter. And that's the power of not only out your brakes simplification. You can do this via algebraic mathematical methods or you can do it visually using Kano maps that I'm about to show you. but you might have noticed the Keen Eye here might have noticed.

Oh, Dave look all you had to you didn't need this extra inverter in here. You could have actually connected that directly up to there. and if you spotted that. bonus Internet points.

But these sort of circuit simplifications here are the entire point of doing cardo maps and also algebraic. uh, logic like this. An algebraic simplification as well. And this you might think, oh, who designs with discrete logic chips anymore? No one right? Well, no, you do Inside uh, Fpgas and inside uh, the Asic chips and inside processors and things like that.

You don't want to be implementing this many gates if you can get away with just this, because not only do you have the extra Gates and the extra silicon, you also have the extra R propagation delay. time to get every every stage of gate you go through increases your propagation delay. That slows down your the maximum frequency of your chip like your latest Intel processor or whatever it is. So you definitely want to be simplifying logic.

so there is still a huge place for learning this sort of stuff. So this clever dude called Maurice Carno he figured out in the 1960s I think that you can actually, uh, do this visually this simplification visually without any algebraic skills whatsoever. Alright, so what we're going to do now is we're going to draw a table that has the same number of squares as elements in our true table. So we've got three inputs for our truth table.

So that's eight inputs over here. So we need a map of eight inputs like this and I'll put a line there and you can draw this in any orientation. It could be uh, like two across by four down, four across by two down. It doesn't actually matter.

And now we're going to map our input variables on here. So a B on 1C Once again, they could be. It doesn't matter what orientation could be A and C and B and C, it doesn't matter as long as you map the correct information over here to the correct part of the Kano map here and this is called a Kano map. So because of our inputs okay, we need our C can be a zero or a one just like over in our true table and our A and B can be a zero and a one.

And then we just uh. number these differently. like this for all of the possible States Now if you had a Keen Eye you would have noticed something that you might think I got wrong. but I didn't and this is a key part of Kano Maps I Number these zero, zero, zero, one, one one and then one zero.

huh? That's not how you count in binary. That's right, we're counting in Gray code and this is one of the tricks to A A How a Kano Map works to actually simplify the Boolean uh expression. and you don't. Technically, you don't have to do it in Gray code order like this.

But if you don't, the Cardinal map technically still works. But you won't get the most optimized simplified solution. So I'll show you a bigger 4x4 Kano map in a minute. But Kano Maps can be.

Uh, basically they can be like two by four. Like this, they can even be two by two. But what's the point? They can be eight by eight. 16 by 16.

Etc. But once they get too big, then you start going well. Okay, it's a bit unwieldy to do this kind of thing on paper and you might let you know you might let a computer or simulator do it for you. But anyway, so what we do now is transfer all of these output data and map them into here.

Um, so A B and C is Zero Zero zero. So A B and C is zero. Zero zero. So we've got a zero here.

So that means we're going to put a zero in there like that. but I won't bore you all the details. I'll go through and uh, map all of these eight uh lines from our true table over to here and there it is there. And trust me, you can go and check for yourself that this truth table equals this Kano map.

And this is one of the areas where you might potentially make a mistake if you're doing Kano Maps You don't map it over correctly. you just didn't double check. So if you're not familiar with the concept of gray code, it's not something that I'll particularly go into here. I might do a separate video on it, but a gray code is where only one bit changes at a time.

So from zero zero to zero one and from 0 1 to 1 1 Like this because if we went one zero, then we would have had this one changing and this one changing as well. And that's not how gray code Works Gray code works by only One bit changing at a time. And this has uh, advantages in things like uh, mechanical, uh, contactors. So if you've got like multiple wipes on a big mechanical switch and you're trying to decode the position of a switch, you would typically use gray code to prevent like multiple race conditions and stuff like that.

There's some other reasons you might use gray code as well, but in this particular case, only one bit changes at a time and that's going to really help us with our Kano map optimization and you'll see. Over here we have some rules. It's not as bad as it looks once you've done these. Kano Maps Once or twice, it's easy peasy, lemon squeezy.

Okay, but the whole idea of Cardo Maps is that we want to group together our ones inside the Kano map like this. Now this is a really simple car. Note: We've only I only happened to have two ones, so what we can do is we group our ones together like this. Okay, now you can only group ones in groups of two, in groups of four, groups of eight or sixteen.

Etc You can't do threes. so if we had like a one here like this, we can't group three ones like that. it doesn't work you. You would have to group the two ones like that and then the two ones again like this.

like I just showed Rule number two here is the groups can overlap. You can overlap them as many and in any order that you are like. Now the third rule is is that everyone must be grouped. So if you've got like a one over here on its Lonesome then you would have to just group it as just on its own as a one and we'll see why.

That's not very advantageous later. But you have to group all of your ones in Kano Maps You ignore all zeros you just completely ignoring because we're dealing with sums of products so zeros aren't. You know you just ignore them at all. The whole idea is to group ones.

You'll see why in a minute. Fourth rule here is you can only group vertically like this. Or if this was a one, you could group two horizontally like that. Or if you had a bigger Kano map with like four of them like this, you could group all four like that so horizontally vertically but also wrap in.

Now here's one of the magical bits of Kano maps you can imagine. You can fold this Kano map over into a three-dimensional shape. You can either do it into a cylinder like top to bottom so that this wraps around to this, or this side wraps around to this side for example. Or you can actually wrap the whole thing into what looks like a Taurus Um, you don't have to visualize it that much.

it's not that important, but the fact is, you could wrap them. So if we actually had a one here and a one here, we could actually group them like this. You actually draw it like that. Now, the fifth rule here is that you want to use the largest groups possible.

Okay, so if you see a group of four ones together, don't just do like. You know if the if this was a one and this was a one, don't do two separate groups of one like that because it'll work. it'll still work. Your logic will still come out correct, but it won't be the most optimized solution the way you get the most optimized solution like we saw here.

Just like over here, we want the most optimized solution like this, and we do that by grouping together the largest number of ones. It won't go into details about how mathematically how this works because that's like really cool, quite complicated. you can go down the rabbit hole, but Kano Maps are brilliant. They work if you group them into the largest possible groups of one, but you've got a map.

Make sure what everyone is in a group, even if it's even if this is a one and it's on, its Lonesome You have to account for it and you want to, of course use the least number of groups because every time you do a circle like this, every time you group ones that actually will end up being a plus term like B C something like this. So let's say we had like three groups of ones in there. Like that, we would. Actually, this is not probably correct.

I'm just drawing random letters, but we would actually have three product terms in there if we have three circles. So each circle is a product term and then this is the sum of products. So it's sum plus sum of a product like this. Got it? So you want to minimize your number of groups.

otherwise your expression ends up being bigger than it needs to be, but it'll still be correct. Effect: You can Goof up Carno maps and do it non-optimally but you'll just end up with a bigger expression not optimized. Don't want that? Whole idea is optimization. Now here's how we solve our Cardo map.

As I said, this is a very simple one. It's only got that one grouped term, that one product term. So X here is going to be equal to just one term. So the first thing you need to learn about Acano Maps is grouping ones together in the most optimized way possible.

The second and final part of solving a Kano map is uh to find which inputs are dependent. What this means is that we've grouped these two ones. Okay, now we solve each. Loop each group in, uh, separately.

Okay, each product term. So which of these inputs A, B and C is it dependent upon? Well, it's dependent upon? C because it's C doesn't change at all. Okay, but A and B these have different values. so you look for the input.

Put that doesn't change. Remember the one that doesn't change and is it A A goes from a zero to a one here. Well, that changes. It's not dependent on A, but it is dependent on B.

Because B is a one and a one. And likewise, C hasn't changed and B hasn't changed. So Bingo We've only got our two inputs. so our B input is a one.

So we write down B like that and then it's and you can put the dot in here or not, it doesn't matter. Some people like to have it just to, you know, for Saturday's sake. but it means and and C but C is a zero so you go not C like that. Aha, you notice something that is exactly the same as that.

Bingo We've solved this equation up here that was complex Before we've solved it visually using Kano maps and because we've only got one summed one Circle in there one group in there's only one product term and it's B and not C Easy Peasy I told you I can't I'm absolutely brilliant. You don't have to solve any algebraic equations at all, and even though this is quite a simple one, they can actually get quite complex. The bigger you know it gets so and you can easily make a mistake doing this. And granted, you can make mistakes doing car No Maps too.

There's two ways to make a mistake in Kano Maps One is mapping from there to there and the other one is then mapping your groupings like this down to your sum of products terms. Plus, you know CD or whatever it is down here. but I love Kano Maps I Just love the elegant Simplicity of this. And if you do kind of maps right, using the gray code like I said here and also in your map, it or and you figure out all the ones, the largest number of ones like the largest groups, and you and the least number of groups, you will always always end up with the most optimized algebraic solution for your truth table.

Brilliant, huh? Let's just run through another example. Uh, in this case, we've got four terms: I haven't redrawn a true table here. But anyway, we would have 16 elements down here because we'd have a B, C, and D here. Okay, once again, we've got our gray code along here and our gray code down here like this: As I said, it doesn't have to be gray code, but if you don't use gray code, you don't get the optimized solution.

So how can we group the ones here? Well, we can't do three like this unfortunately. Um, so the obvious one is one one one one one one one one one one one. so let's solve this. Okay, X equals now because we've got four uh, grouped terms here, we know we're going to have four products.

So it'll be product one plus product two plus product three plus product four. So we're going to have four products with the sum of those in our X term. Okay, so let's start with this group up here. It doesn't matter which order you do them in the logic expression comes out.

it'll The products will be in different order, but that doesn't matter for your logical expression. Still exactly the same. Okay, so you'll note. Well, let's go right because it's vertical like this.

It means that A and B could change. but which one is not changing? Well, A is not changing. Okay, so we know that it's dependent upon A. Our output is dependent upon the one that does not change here.

So B's change you from a zero to a one. So B gets eliminated from the equation. But C and D here because it's a vertical grouping like that. C and D don't change at all.

So, but C is a zero so it's not C and then D is a one up here. so it's D like that. So we've finished our first Uh product term. so it's a sum of products.

So uh, plus here let's work on this one here. which does A and B no A and B doesn't change. but A is a zero so that's A not A and B Because B is a one and then which one doesn't change out A C and D here C is the one that doesn't change and because it's a one, it has to get included. But D changes from a one to a zero in this group.

so it gets eliminated from our equation. So that's our second product term. So we go. Plus, let's do this one down here.

Um, the A doesn't change, B changes so it gets eliminated. Uh, and this one here. A C is a one and D is a zero. So it goes like that.

And our last group in down here: A doesn't change. so it's A and it's not. B Because B is a zero there. Um, and S not C like that.

Bingo. So there is our optimized expression. This is as optimized as it gets for this particular table, but there is more than one way to solve this. We won't simplify it any further, but we can actually really group these in different ways.

So instead of grouping these like this, let's let's group them slightly differently. Okay, you, we we could group for example, this one here. with this one down here. Remember, we can do the wrapping thing.

We can group that one with this one over here like this. and then we could group these two like that. So what equation do we end up with down here? Well, let's do This one up the top here. Uh, okay.

so A and it wraps around like like this: Okay, it looks like B is not changing. Okay, between there and there, B's are zero. So we've got not B A changes so it gets eliminated and then C and D not C like that and D and I'll go through the rest of them. Uh, let's do this one here.

not A B and uh, D like that. Okay, so it's slightly uh, changed this one over here. B doesn't change and C doesn't change and D doesn't change. but it's A not because it's a zero.

And last of all, this one down here. and here we've got A like that and not B and uh looks like not D like that. I think I've got that correct. You can trouble double check that uh down below.

but these two expressions are absolutely identical, even though they've got different terms in them. It just depends on how you group these ones. But you notice that all that both of these Expressions have four product terms like this and they've both got the same number of inputs. They've got three, three, three, three, three, three like that.

Etc So neither of those is, uh, reducing the number of gates that you need to actually, uh, produce this logic output that's a whole idea of Kano Maps We're minimizing the number, minimizing the size of our Boolean expression. which means the number of sums like this, and also the number of terms inside each. Art Product Like that as well, but they're both the same. They're just organized differently.

But these, if you implement the logic gates with these, it'll be exactly the same. Another quick example of a 4x4 I won't go on to an 8x8, but it works exactly the same way. I've just, uh, once again, it doesn't match. uh, this truth table over here.

so just ignore that uh, true couple by hand over. it doesn't work that way. So what is the largest group that we can actually make here? Well, obviously it's a four by four Bingo And if we had like an if these two were ones like this, we couldn't group six of them. Remember, it's got to be a multiple, a single, or a multiple of Uh twos.

but we could actually have um, two groups of four overlaid, overlapped like that. But let's go back to the original here now. we've got two ones lying out here. like this one.

We can actually group the two ones overlapping like that. But remember, we, every single one must be grouped in here. So this one. we can't go diagonally like that.

You can't do it. You can't wrap around to either of the sides or anything so that one's out there on its Lonesome and you'll see the penalty that we pay for that. There's nothing we can do about it like we can't do anything that's just. um, you'll see what happens.

So let's take our group of four like this: which one, uh, A and B Which one doesn't change? Which is it dependent upon? X equals B like that and x equals D. So it's just B and D. Plus, because we've got three groupings, we're going to have three sum terms here. So let's do this one down here.

Like this: which one is depend upon. It's dependent upon A like that and uh, C and D A C D like that. And then we've got to do. or we've got to do the sum again.

Now this one over here on its own. Here's the penalty we pay for only grouping the one like this: A and B it's got. so A and B is dependent upon that because A and B doesn't change, but they're both knots. and then C and D.

So C is a one and D is a zero like that. So there's our final term that is our optimized term like that. and you'll notice that we've got two here. three here, and four.

um, product terms in there like that, and that was related to how many ones we circled. You notice that because we group four together like this, we eliminated two of the terms. so we only end up with two dependent terms. This one here is only a group of two, so we ended up with three dependent terms there.

That's why we ended up with three terms in our uh product there and this one out on its Lonesome. The penalty we pay is that you have to group in four terms like that. so you need extra and Gates you need a four input and gate, a four input and gate, a three input and gate, and a two input and gate like this. This is why you want to maximize the number of ones like that because if you can group eight ones.

But let's assume it was our lucky day and we had eight ones like this. Okay, so we can group our eight ones like that. Whoa. And but we've also got four ones like this, but we've also got four.

instead of just doing those two that. That would have covered it. But you remember, we want to use the largest groups possible so we can group another group of four like that. Okay, so let's actually solve that one.

You'll see that with a massive group of eight like that the term C and D get eliminated entirely because both of them change in there. Okay, so C and D is eliminated. and because, uh, we've got a basically a group of like a a two group. like that.

it's a similar to a vertical group of two. Like that it means that only a is the only one that doesn't change. So our term is just not a like that or which is a plus. That's what all means.

And we've got this term in here like this. Exactly the same as before. that's A B and A D and then we go or and then we've got uh, this one here which is uh, C and D doesn't change. So C D and um, A is completely eliminated because we did that.

So that is our final expression. Like that: we've got a lower number of input terms here. Um, because like the most we have is a two input and gate for example. and that's just a one.

I don't even need an and gate there eliminated entirely because we had a group of eight. Magic. So that's Kano maps for you I Love them. They're so easy you don't have to learn.

uh, you know, solving algebraic equations like this, you can just do it as long as you've got like this sounds like a lot of rules, but it's not. Just do it. Do a few examples once or twice and you know it's a really, uh, trivial stuff. really.

There's only two steps. One is mapping that to that, which is pretty easy unless you like goof it up. Copying across it's easy. You've got to know your gray code.

Okay, like this. but as I explained, you don't actually have to do that I could do this. One zero like that and then one one like that and one zero here and one one down there. Um, it'd still work.

You can still use Kano maps to solve. You'll just end up with potentially more terms like this. In fact, we can swap these rows willy-nilly right. We can have these in any any order.

As I said, this could be C and A and this could be D and B here. and you can just swap them around until the cows come home. But there's only one way that will give you the optimized solution. and that's to use the gray code encoding.

With one bit changing at a time, you can go into the complex math of why that's the case. but the gray code is the key to the optimization. It'll still work without it. But yeah, you'll just get extra terms in.

you know, using more gates. not always use more gates. Last thing we want in the world is more gates anyway. I Hope you enjoyed that.

Look at Kano map. So really great I Love I've always loved Kano Maps I Just love the elegant Simplicity of it. It was brilliant how it it just as long as you do the maximum number of groups in here, you'll always end up with the most optimized algebraic solution possible and hence the least number of gates. Fantastic! Anyway, hope you found that interesting and found it useful.

If you did, please give it a big thumbs up. As always discussed down below, catch you next time tomorrow Foreign.