K-Maps and Prime Implicants

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 Quine-McCluskey Method of simplifying a boolean expression
3) Prime Implicants

I understand WHAT a K-map 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 Quine-McCluskey 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?
LVL 31
Frosty555Asked:
Who is Participating?
I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

BrianGEFF719Commented:
Hi Frosty,

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?

Brian
0

Experts Exchange Solution brought to you by

Your issues matter to us.

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Start your 7-day free trial
BrianGEFF719Commented:
So i'll explain further...

Once you've identified all prime, and essential prime implicants, you need to know extract them from the k-map.

Firstly you need to pull out all essential prime implicants. Do you know how to read the k-map 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 two-level and-or network.

Does that make sense?
0
Cloud Class® Course: Certified Penetration Testing

This CPTE Certified Penetration Testing Engineer course covers everything you need to know about becoming a Certified Penetration Testing Engineer. Career Path: Professional roles include Ethical Hackers, Security Consultants, System Administrators, and Chief Security Officers.

moorhouselondonCommented:
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.

http://en.wikipedia.org/wiki/Quine%E2%80%93McCluskey_algorithm
0
moorhouselondonCommented:
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.
0
Frosty555Author Commented:
Brian - that makes sense. I do understand how to identify what variables are in question on a K-Map. So the implicants *must* be powers of two? So, say, this K-map:

      __ __ __ __
     |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?
0
moorhouselondonCommented:
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.
0
moorhouselondonCommented:
This looks to me like a good explanation:

http://web.cecs.pdx.edu/~mcnames/ECE171/Lectures/Lecture10.html
0
BrianGEFF719Commented:
>>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 k-map

 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.

Make sense?
0
Frosty555Author Commented:
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 Quine-McClusky 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?
0
moorhouselondonCommented:
See my earlier link ID:22765088.  What you do is to work out which combination of the non-essential prime implicants to use using manual rule of thumb.  You just mkake sure that all outputs are "covered" at least once.

Which non-essential PI's you use can depend on practicalities, such as which logic family you are building this with - if you are building with 2-input NAND's for example, you might construct your circuit differently than if you were using 3-input NAND's, due to the intermediate outputs available in the design.  If using 7400 series logic chips (or equivalent) you get 4x 2-input 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 gob-smacked 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.
0
Frosty555Author Commented:
Makes sense, okay thank you everyone!

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.

Thanks for everyone's help.
0
BrianGEFF719Commented:
@Frosty555, what school?
0
Frosty555Author Commented:
Brian - York University

Funny enough, now we've been on strike for the last three months, so only NOW is my final exam coming up, and here I am re-reading this thread :)
0
It's more than this solution.Get answers and train to solve all your tech problems - anytime, anywhere.Try it for free Edge Out The Competitionfor your dream job with proven skills and certifications.Get started today Stand Outas the employee with proven skills.Start learning today for free Move Your Career Forwardwith certification training in the latest technologies.Start your trial today
Math / Science

From novice to tech pro — start learning today.

Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.