I"m trying to understand a few topics in the subject of Digital Logic Design, and Boolean Logic.
1) Karnaugh maps, in 2, 3 or 4 variables.
2) The QuineMcCluskey Method of simplifying a boolean expression
3) Prime Implicants
I understand WHAT a Kmap is and how to express a boolean expression as one, but what to do from there in order to simplify it is beyond me.
I understand the notion of the QuineMcCluskey method of simplying a boolean expression but I don't actually know how to do it
And I don't even know what a prime implicant is, although I get the feeling it is something that I have already have experienced, just don't know it yet.
Anyone feel like explaining a bit? Or link me to some good articles I can study?
First you must understand that each 1 in the karnaugh map represents a minterm.
An implicant is an group of 1's in a multiple of two. For example two adjacent ones is an implicant, 4 adjacent ones, or 8 adjacent ones is an implacant.
Now, a prime implicant is any implicant that isn't covered by another implicant.
And finally an essential prime implicant is a prime implicant that has atleast one 1 that isn't covered by another prime implicant, and hence is essential. Does that make sense?
Once you've identified all prime, and essential prime implicants, you need to know extract them from the kmap.
Firstly you need to pull out all essential prime implicants. Do you know how to read the kmap to determine which variables they correspond to?
Once you've pulled out the essential prime implicants you need to now determine if any regular prime implicants need to be included, you can determine this by seeing which 1's are left that weren't included in any essential prime implicants. You would include that implicant, and you're done.
After you've done that, you'll have a minimized twolevel andor network.
Does that make sense?
0
We value your feedback.
Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!
McCluskey is simply an algorithm that minimises logic expressions in a form that can be readily run by a computer. From what I remember it is sometimes the case that there can be more than one solution to a problem. McCluskey presents you with the choices and you have to decide which to use.
In Step 2 of my link, the lines with asterisks are Essential Prime Implicants  these are essential elements required for the solution. The other two rows are not essential, but you do need either one or the other.
You could use both  a computer solution would be to use both, the extra effort in deciding which to use is not worth it.
Brian  that makes sense. I do understand how to identify what variables are in question on a KMap. So the implicants *must* be powers of two? So, say, this Kmap:
__ __ __ __
X X X
 X X
 X

There's a group of four in the middle, and then two singletons hanging off the end.
You wouldn't call it a group of three at the top, and then a two and a single?
You would do the group of four, then a double then another double. If you were implementing this using logic gates it takes more logic to define a single X than it does XX. It doesn't matter that you have overlap.
>>ou wouldn't call it a group of three at the top, and then a two and a single?
Three isn't a power of two! So it would be a group of two on the top left, a group of four in the middle, and a group of two at the bottom, all essential.
The only case when you will have a single implicant such as just 1, is when it's surrounded by zeros: Suppose you have an n variable kmap
0 0 0
0 1 0
0 0 0
This represents an implicant that will require n variables. It will be required as the whole minterm.
Ah I see, because if it's nearby another group, you might as well use that to your advantage! Makes sense.
Okay, one more question regarding the QuineMcClusky algorithm:
You start by identifying minterms in the equation, organizing them by how many "1"s are in each minterm, and then you combine them into "Size 2" minterms. Then combine those into "Size 4" minterms etc. until you cannot combine anymore. You're left with prime implicants.
Then you arrange them into a table with the original minterms across the top, and the newly simplified prime implicants on the left, marking an X for each minterm that each prime implicant uses. At this point you can identify essential prime implicants because those will be ones where there is only one X in a particular columng  e.g. the minterm is defined by only one prime implicant.
Now.... you're supposed to do some kind of magic to combine essential prime implicants with other prime implicants in this table. Wikipedia doesn't explain that much, how does that work?
See my earlier link ID:22765088. What you do is to work out which combination of the nonessential prime implicants to use using manual rule of thumb. You just mkake sure that all outputs are "covered" at least once.
Which nonessential PI's you use can depend on practicalities, such as which logic family you are building this with  if you are building with 2input NAND's for example, you might construct your circuit differently than if you were using 3input NAND's, due to the intermediate outputs available in the design. If using 7400 series logic chips (or equivalent) you get 4x 2input NAND gates on a chip  the design is generally more practical if it minimises actual chip count than how many gates are actually used. Having developed circuits using the original SN7400 TTL series logic myself, you would be gobsmacked to hear the amount of current these devices consume  particularly the spikes generated when switching states.
If power consumption and cost of chips were secondary objectives to making absolutely certain that the circuit worked, then you would include all Entries generated by Step 2  this is the way that an "end to end" computer designer would build things.
moorhouselondon  I wish I was learning this for actual practical purposes :) It was actually in preparation for my digital logic midterm which was this morning. And I think I did well. But you've given me some good insights.