Solved

K-Maps and Prime Implicants

Posted on 2008-10-20
14
7,272 Views
Last Modified: 2012-05-05
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
Comment
Question by:Frosty555
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 5
  • 4
  • 4
  • +1
14 Comments
 
LVL 84

Expert Comment

by:ozo
ID: 22764745
0
 
LVL 19

Accepted Solution

by:
BrianGEFF719 earned 250 total points
ID: 22764813
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

by:BrianGEFF719
BrianGEFF719 earned 250 total points
ID: 22764829
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
Industry Leaders: We Want Your Opinion!

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!

 
LVL 31

Assisted Solution

by:moorhouselondon
moorhouselondon earned 250 total points
ID: 22765061
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

by:moorhouselondon
moorhouselondon earned 250 total points
ID: 22765088
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

by:Frosty555
ID: 22770329
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

by:moorhouselondon
moorhouselondon earned 250 total points
ID: 22770428
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

by:moorhouselondon
ID: 22770716
This looks to me like a good explanation:

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

Assisted Solution

by:BrianGEFF719
BrianGEFF719 earned 250 total points
ID: 22773339
>>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

by:Frosty555
ID: 22773587
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

by:moorhouselondon
moorhouselondon earned 250 total points
ID: 22773943
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

by:Frosty555
ID: 22780955
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

by:BrianGEFF719
ID: 22781536
@Frosty555, what school?
0
 
LVL 31

Author Comment

by:Frosty555
ID: 23713912
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

Independent Software Vendors: We Want Your Opinion

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!

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

A Guide to the PMT, FV, IPMT and PPMT Functions In MS Excel we have the PMT, FV, IPMT and PPMT functions, which do a fantastic job for interest rate calculations.  But what if you don't have Excel ? This article is for programmers looking to re…
This article provides a brief introduction to tissue engineering, the process by which organs can be grown artificially. It covers the problems with organ transplants, the tissue engineering process, and the current successes and problems of the tec…
This is a video describing the growing solar energy use in Utah. This is a topic that greatly interests me and so I decided to produce a video about it.
Although Jacob Bernoulli (1654-1705) has been credited as the creator of "Binomial Distribution Table", Gottfried Leibniz (1646-1716) did his dissertation on the subject in 1666; Leibniz you may recall is the co-inventor of "Calculus" and beat Isaac…

691 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question