Link to home
Start Free TrialLog in
Avatar of Frosty555
Frosty555Flag for Canada

asked on

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?
Avatar of ozo
ozo
Flag of United States of America image

ASKER CERTIFIED SOLUTION
Avatar of BrianGEFF719
BrianGEFF719
Flag of United States of America image

Link to home
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Start Free Trial
SOLUTION
Link to home
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Start Free Trial
SOLUTION
Link to home
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Start Free Trial
SOLUTION
Link to home
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Start Free Trial
Avatar of Frosty555

ASKER

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?
SOLUTION
Link to home
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Start Free Trial
SOLUTION
Link to home
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Start Free Trial
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?
SOLUTION
Link to home
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Start Free Trial
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.
@Frosty555, what school?
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 :)