Solved

# K-Maps and Prime Implicants

Posted on 2008-10-20
7,029 Views
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?
0
Question by:Frosty555
• 5
• 4
• 4
• +1

LVL 84

Expert Comment

0

LVL 19

Accepted Solution

BrianGEFF719 earned 250 total points
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

LVL 19

Assisted Solution

BrianGEFF719 earned 250 total points
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

LVL 31

Assisted Solution

moorhouselondon earned 250 total points
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

LVL 31

Assisted Solution

moorhouselondon earned 250 total points
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

LVL 31

Author Comment

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

LVL 31

Assisted Solution

moorhouselondon earned 250 total points
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

LVL 31

Expert Comment

This looks to me like a good explanation:

http://web.cecs.pdx.edu/~mcnames/ECE171/Lectures/Lecture10.html
0

LVL 19

Assisted Solution

BrianGEFF719 earned 250 total points
>>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

LVL 31

Author Comment

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

LVL 31

Assisted Solution

moorhouselondon earned 250 total points
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

LVL 31

Author Comment

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

LVL 19

Expert Comment

@Frosty555, what school?
0

LVL 31

Author Comment

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

## Featured Post

### Suggested Solutions

Python tuple index error 4 64
Forces on a string 9 54
Graph Function 6 60
Simple Calculation for Value of Availablity 5 64
How to Win a Jar of Candy Corn: A Scientific Approach! I love mathematics. If you love mathematics also, you may enjoy this tip on how to use math to win your own jar of candy corn and to impress your friends. As I said, I love math, but I gu…
Lithium-ion batteries area cornerstone of today's portable electronic devices, and even though they are relied upon heavily, their chemistry and origin are not of common knowledge. This article is about a device on which every smartphone, laptop, an…
It is a freely distributed piece of software for such tasks as photo retouching, image composition and image authoring. It works on many operating systems, in many languages.
This video gives you a great overview about bandwidth monitoring with SNMP and WMI with our network monitoring solution PRTG Network Monitor (https://www.paessler.com/prtg). If you're looking for how to monitor bandwidth using netflow or packet s…