Solved

K-Maps and Prime Implicants

Posted on 2008-10-20
14
7,059 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
  • 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
 
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
Is Your Active Directory as Secure as You Think?

More than 75% of all records are compromised because of the loss or theft of a privileged credential. Experts have been exploring Active Directory infrastructure to identify key threats and establish best practices for keeping data safe. Attend this month’s webinar to learn more.

 
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

Is Your Active Directory as Secure as You Think?

More than 75% of all records are compromised because of the loss or theft of a privileged credential. Experts have been exploring Active Directory infrastructure to identify key threats and establish best practices for keeping data safe. Attend this month’s webinar to learn more.

Question has a verified solution.

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

Suggested Solutions

Title # Comments Views Activity
technology for 'real' windows (not OS) 7 60
coolers to wear for eyes in workplace (8-10 hours of computer starring!) 10 99
Math Stumper 6 47
Triangle - calculating angles 9 62
Complex Numbers are funny things.  Many people have a basic understanding of them, some a more advanced.  The confusion usually arises when that pesky i (or j for Electrical Engineers) appears and understanding the meaning of a square root of a nega…
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.
With Secure Portal Encryption, the recipient is sent a link to their email address directing them to the email laundry delivery page. From there, the recipient will be required to enter a user name and password to enter the page. Once the recipient …

929 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

Need Help in Real-Time?

Connect with top rated Experts

13 Experts available now in Live!

Get 1:1 Help Now