Digital logic circuit simplification using Karnaugh Maps.
How to use a visual method to solve boolean algebraic equations and truth tables.
Part 5 of the digital logic design tutorial series.
Playlist: https://www.youtube.com/playlist?list=PLvOlSehNtuHs2LwEdDwTp3n7mxb-MyBbo
Forum: https://www.eevblog.com/forum/blog/eevacademy-digital-design-series-part-5-karnaugh-maps/
00:00 - Part 5 of the digital logic design tutorial series
02:15 - Solving a logic truth table algebraically
04:17 - Verification of result By Inspection
06:27 - Maurice Karnaugh and drawing Karnaugh Maps
07:44 - The magic of Gray Code
08:51 - Mapping from Truth Table to Karnaugh Map
10:20 - The RULES for grouping 1's
14:21 - Solving the Karnaugh Map usign Sum of Products
17:19 - 4x4 Karnaugh Map
20:06 - There is more than one solution
22:23 - Another example with overlapping groups
If you find my videos useful you may consider supporting the EEVblog on Patreon: http://www.patreon.com/eevblog
Web Site: http://www.eevblog.com
Other channels:
EEVblog2: http://www.youtube.com/EEVblog2
EEVdiscover: https://www.youtube.com/eevdiscover
T-Shirts: http://teespring.com/stores/eevblog
#ElectronicsCreators #digitaldesign #EEVacademy

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.

Avatar photo

By YTB

18 thoughts on “Eevacademy digital design series part 5 – karnaugh maps”
  1. Avataaar/Circle Created with python_avatars Lwd400mIJSBAAN says:

    Don't forget Feits, we had to study them in 1977

  2. Avataaar/Circle Created with python_avatars Nikhil Joshi says:

    Sir will you be continuing this series for now cause I'm taking notes and I'm loving your content!!โค๏ธ๐Ÿ˜Ž

  3. Avataaar/Circle Created with python_avatars Arnoud says:

    It sometimes possible to have "don't care" states, marked with *, for instance, if you have a decimal 7-segment display, you have don't cares from A to F. That often helps simplify logic gates a lot. Wikipedia has a paragraph on it. By the way, for a real challenge – try to figure out how NASA engineers were able to use 5 just relays to control the 7 segment display on the Apollo DSKY ๐Ÿ™‚

  4. Avataaar/Circle Created with python_avatars Richard Wells says:

    Is there any non trial-and-error method for simplifying circuits using xor? For example, -A-BR + AB-R (where -A means "not A") simplifies to (A xor R)(B xor R), but the latter is a much simpler circuit (at least it is when using 74-series chips, which is what I'm mostly concerned with).

  5. Avataaar/Circle Created with python_avatars Bert Blankenstein says:

    I learned about Karnaugh mapping in high school, maybe '87. We then went on to implement using NAND gates and also using NOR gates.

  6. Avataaar/Circle Created with python_avatars D M says:

    I learned about merger graphs which is almost an art form. Been a while though.

  7. Avataaar/Circle Created with python_avatars Ross McKenzie says:

    Well that took me back to 1969 at RMIT.

  8. Avataaar/Circle Created with python_avatars vogonjelc says:

    How much does Dave CAD license cost?

  9. Avataaar/Circle Created with python_avatars NiceLights says:

    this made me feel like im 17 again ๐Ÿ™‚ thanks, great presentation

  10. Avataaar/Circle Created with python_avatars Algorithm, Inc. says:

    Great series. Thanks. I love this topic in particular … and suggest a follow up video with the "Quine-McCluskey algorithm." At Georgia Tech in Atlanta in the 1980's, they taught the approach for EE (along with Karnaugh for smaller problems). Caldwell and Fielder at Ga. Tech added to the approach, if I remember correctly (I knew Fielder). In any case, really enjoying the channel … and still chuckling with the moon-landing video. All the best and cheers from sunny Florida, USA – Christopher

  11. Avataaar/Circle Created with python_avatars s8wc3 says:

    Wordsearch puzzles for Engineers

  12. Avataaar/Circle Created with python_avatars Artur says:

    Love to learn these maps and never use them. I usually try to pull my hair when logic in if() statements needs to be simplified

  13. Avataaar/Circle Created with python_avatars nathan russell says:

    DaveCad-very educational.

  14. Avataaar/Circle Created with python_avatars G6EJD - David says:

    My Professor was Douglas Lewin and he taught me as a designer you canโ€™t minimise the logic too far as you have to consider the repair and diagnostics process later in the design life, meaning you had to leave enough for the repair technician to work out whatโ€™s going on. Wise words.

  15. Avataaar/Circle Created with python_avatars Panda says:

    Great job! Using this to study for my digital logic final. Thanks for the video

  16. Avataaar/Circle Created with python_avatars Fazzle says:

    I saw you posting about lower views on launch, but let me tell you this is really useful content. Thanks!

  17. Avataaar/Circle Created with python_avatars R Brown says:

    I remember my digital logic class in college in the 70s. We spent a while on Karnaugh Maps. Last day of that we were given the classic 4-way light switch problem. Basically a room with 4 doors and a light switch at each door. Problem was to design a "simplified" logic circuit to control a single light in the room by turning it on at any switch and then off at any switch. Give it a go and try to simplify via a KM.

    There was one student in the class that managed to get one gate less that the "brute force" logic. Then the prof. asked how long that student spent on the solution and he worked out the cost for that one saved gate. This was our introduction to MSI logic and multiplexers, when the prof. showed how that same logic could be implemented with one 16:1 multiplexer chip.

  18. Avataaar/Circle Created with python_avatars BobC says:

    Good job! The next step is always fun, selecting the actual gates to be used.

    When I was a technician in the US Navy, we often had electronic systems that would last the life of the ship (yes, I even worked on perfectly good systems containing tubes/valves). Meaning we also had boards and racks filled with jellybean TTL logic that needed to evolve rather than be replaced. When a bug was found or a new feature was needed, in the worst case it could mean a expensive re-spin of a decades-old board may be needed. More often, we'd instead be sent a step-by-step procedure to add an extensive series of jumpers, along with updates to the documentation describing the change. The high-level description never matched the gates that were connected. They had to use whatever free gates were available on the board, meaning the ideal change described in the overview had to be transformed to make use of available resources on the boards.

    I saw they used ingenious equivalences. What do you do when you need an AND gate, but have only NOR gates? This was de Morgan's Laws being used sideways, transforming the ideal to make use of the real. This notion lit my brain on fire. "De-optimization" as a vital part of the path for solving a highly constrained engineering problem!

    I loved reverse-engineering the delivered solution to see if I could do better, where "better" had two primary constraints: Don't ruin the timing, and don't use more resources (jumpers and spare gates). Then, when I did find a "better" solution, I'd step back and ask if there were reasons the designers would choose to NOT use my "better" approach. This was where I learned about wire length issues, gate loading issues, gate speed issues, and so on. All the "unpleasant realities" one encounters when implementing an optimal Karnaugh Map solution into an existing system.

    In time I became fairly proficient at this, and it became a hobby for me to dream up new system features, design the optimal solution, then see if the ideal solution could be transformed to permit it to be implemented using the spare resources available on the board. Fun stuff! I also gained a reputation as a savvy troubleshooter, as this "hobby" also encouraged me to go beyond our technical documentation to look at how and why our systems were designed and implemented the way they were.

    The last ship I served on was brand new. In fact, I was on the small team that inspected and tested every inch of it as we signed off on each system as part of the Navy's acceptance process with the shipyard. Despite how new it was, it still contained decades-old technology, largely due to the long lead-times for military system design and procurement, combined with the need to reuse older systems still in production whenever it made sense to do so.

    One brand-new system, the set of digital engineering consoles used to control the propulsion, electrical and auxiliary systems, were still implemented using old jelly-bean logic on small cards plugged into large wire-wrapped backplanes. My ship was among the last 10 of 30 Spruance-class destroyers made. During the run of Spruance-class construction, the Navy created and built the Oliver Hazard Perry-class frigate, which used the same marine gas turbine propulsion system as the Spruance class (with 2 engines instead of 4), but had far newer technology in its engineering consoles.

    When the first Perry frigate arrived at our base, all of us engineering techs went over to compare notes. We were very upset when they wouldn't let us disassemble their consoles. But we did see they had several cool features implemented that our ships lacked. I immediately set myself the task of cloning as many of those features as possible into the spare gates of our consoles. Some were clearly too complex to even consider. Others would need signals or sensors our systems lacked.

    Here's one example: Though our ships shared common propulsion jet turbine engines, their engine control system had been updated, and provided one key signal our systems lacked: An engine flame-out alarm. This signal came from a flame sensor added to a sensor port that was blocked off on our engines. Why? I have no idea why our destroyer engines lacked a flame-out alarm, as it meant we had to vigilantly monitor the engines to see when power was unexpectedly lost. (Note: There was lots of inertia in the system, so a loss of speed wouldn't be noticed until an engine experiencing a flame-out had spun way down.)

    I wanted to see if I could design and implement a "good enough" stand-in for a flame-out alarm using only the signals and spare gates available in our main engineering console. I gave myself a further constraint that I couldn't modify any of the plugin-cards, and could only use signals available at card rear connector, so I could implement the feature using only wire-wrap changes to the card cage backplanes. This would also make the feature easily reversible, in case I messed up.

    I did come up with an approach which I ran past my fellow techs and our supervisors, challenging them to find a flaw. We wanted to test it, but it was ABSOLUTELY illegal to modify critical ship systems in this or any other way. Still, we figured it wouldn't hurt to ask, so we walked the idea up the chain of command. Our Commanding Officer, the Captain of the ship, was very gung-ho, and agreed to implement the feature for one of our 4 engines. He also added the constraint that we must have spares in stock for every card I'd be accessing..

    I implemented the change, and it worked! We now had one engine with a flame-out alarm. So, of course, we used that engine for all our casualty control training and examinations for things like a fuel supply valve being tripped.

    Once the design had proven itself, I fully documented it as a "Benny-Sug" (Beneficial Suggestion) for an engineering change, and sent it up the chain of command all the way to Washington. Being VERY careful, of course, to NOT mention the change had already been implemented, tested and proven.

    I did not receive the reply I was expecting. Our Captain was reprimanded for allowing design changes to critical systems to even be considered, much less supported and forwarded. I was crestfallen when I got the news. However, the CO then said: "You are expressly forbidden to pursue this change any further, in any way whatsoever." Now, you need to know Navy Speak to parse this correctly. It also meant I was not allowed to REMOVE the change! For years we kept performing and passing casualty drills using that engine.

    Looking back, I view that flame-out design as my first true engineering product. My pride in that accomplishment, combined with the Navy's poor reception of it, directly influenced my decision to leave active duty to pursue an engineering degree and a civilian career.

    And it all started with figuring out how the "ideal" modifications were designed and implemented using Karnaugh, de Morgan, some spare gates, and a spool of jumper wire.

Leave a Reply to Panda Cancel reply

Your email address will not be published. Required fields are marked *