# Homework Help: Quinne-MCCluskey simplification

1. Nov 29, 2005

### electronic engineer

was asked to simplify this logic expression using Quinne-Mccluskey algorithm:

f=ABC'+ACD'+A'B'D+B'CD+A'C'D

need help!

2. Nov 30, 2005

### electronic engineer

I've solved my problem in this way:

1- i have to find prime implicants for minterms

ABC'=110X (where x indicates don't care values which is here D)
ACD'=1X10
A'B'D=00X1
B'CD=X011
A'C'D=0X01

then i've arranged them upstairs according to the number of 1's(just for arrangement):

00x1
0x01
x011
1x10
110x

I found p-implicants by combining pairs of them that can be combined so p-implicants are:

0xx1
x0x1

2- I have to find essential prime implicants as follows:

p-implicants minterms
00x1 0x01 x011 1x10 110x

0xx1 * *
x0x1 * *

the essential p-implicants are those who have single one in the column
so they are: 0xx1, x0x1

3- find the minimal subset of the remaining covering the uncovered with single one in a column, so we have one column that contains that subset and we should select on of the items in that column , let us choose the upper one (0xx1) , note: here's no matter whether to select the upper or the lower one causer they both will give use the same result as follows:

result=A'D+B'D+ A'D (or B'D)

Both will give us according to the property A+A=A :

result=A'D+B'D

I'm not sure yet of my solution there may be some errors, could you check it?!

thank a lot!

3. Nov 30, 2005

### electronic engineer

I've solved my problem in this way:

1- i have to find prime implicants for minterms

ABC'=110X (where x indicates don't care values which is here D)
ACD'=1X10
A'B'D=00X1
B'CD=X011
A'C'D=0X01

then i've arranged them upstairs according to the number of 1's(just for arrangement):

00x1
0x01
x011
1x10
110x

I found p-implicants by combining pairs of them that can be combined so p-implicants are:

0xx1
x0x1

2- I have to find essential prime implicants as follows:

p-implicants minterms
00x1 0x01 x011 1x10 110x

0xx1 * *
x0x1 * *

the essential p-implicants are those who have single one in the column
so they are: 0xx1, x0x1

3- find the minimal subset of the remaining covering the uncovered with single one in a column, so we have one column that contains that subset and we should select on of the items in that column , let us choose the upper one (0xx1) , note: here's no matter whether to select the upper or the lower one causer they both will give use the same result as follows:

result=A'D+B'D+ A'D (or B'D)

Both will give us according to the property A+A=A :

result=A'D+B'D=(A'+B')D

I'm not sure yet of my solution there may be some errors, could you check it?!

thank a lot!

4. Nov 30, 2005

### electronic engineer

Sorry

I've solved my problem in this way:

1- i have to find prime implicants for minterms

ABC'=110X (where x indicates don't care values which is here D)
ACD'=1X10
A'B'D=00X1
B'CD=X011
A'C'D=0X01

then i've arranged them upstairs according to the number of 1's(just for arrangement):

00x1
0x01
x011
1x10
110x

I found p-implicants by combining pairs of them that can be combined so p-implicants are:

0xx1
x0x1

2- I have to find essential prime implicants as follows:

p-implicants minterms
00x1 0x01 x011 1x10 110x

0xx1 * *
x0x1 * *

the essential p-implicants are those who have single one in the column
so they are: 0xx1, x0x1

3- find the minimal subset of the remaining covering the uncovered with single one in a column, so we have one column that contains that subset and we should select on of the items in that column , let us choose the upper one (0xx1) , note: here's no matter whether to select the upper or the lower one causer they both will give use the same result as follows:

result=A'D+B'D+ A'D (or B'D)

Both will give us according to the property A+A=A :

result=A'D+B'D=(A'+B')D

I'm not sure yet of my solution there may be some errors, could you check it?!

thank a lot!

5. Nov 30, 2005

### electronic engineer

Sorry

I've solved my problem in this way:

1- i have to find prime implicants for minterms

ABC'=110X (where x indicates don't care values which is here D)
ACD'=1X10
A'B'D=00X1
B'CD=X011
A'C'D=0X01

then i've arranged them upstairs according to the number of 1's(just for arrangement):

00x1
0x01
x011
1x10
110x

I found p-implicants by combining pairs of them that can be combined so p-implicants are:

0xx1
x0x1

2- I have to find essential prime implicants as follows:

p-implicants minterms
00x1 0x01 x011 1x10 110x

0xx1 * *
x0x1 * *

the essential p-implicants are those who have single one in the column
so they are: 0xx1, x0x1

3- find the minimal subset of the remaining covering the uncovered with single one in a column, so we have one column that contains that subset and we should select on of the items in that column , let us choose the upper one (0xx1) , note: here's no matter whether to select the upper or the lower one causer they both will give use the same result as follows:

result=A'D+B'D+ A'D (or B'D)

Both will give us according to the property A+A=A :

result=A'D+B'D=(A'+B')D

I'm not sure yet of my solution there may be some errors, could you check it?!

thank a lot!

6. Nov 30, 2005

### Staff: Mentor

You're making me dizzy!

7. Nov 30, 2005

### electronic engineer

i'm sorry , but that's i could do (unfortunately )

thanks for interesting!

8. Dec 2, 2005

### matejhowell

How did you get the PI of 0xx1?

9. Dec 2, 2005

### electronic engineer

by combining 00x1 , 0x01 so i got 00x1

10. Dec 2, 2005

### electronic engineer

sorry

sorry ,wrong in spelling (I got 0xx1)

11. Dec 2, 2005

### matejhowell

Almost right

You cannot combine these two. The first term (00x1) does not depend on the variable C. The second term (0x01) does depend on the variable C. A similar argument can be made for the variable B. So, 0xx1 is not a Prime Implicant.
For Quine McCluskey, you can only combine terms that differ in one variable, not including don't cares.
Probably the first step you want to do is list all the minterms. I got (1,3,9,10,11,12,13,14).
I'll add more later. Tell me what you think.

12. Dec 2, 2005

### matejhowell

Are you sure you copied down the problem right? The solution you gave is a minimal one (check it by K-map).

13. Dec 2, 2005

### electronic engineer

you're right about combining , we can't combine minterms that depend on variable(like c) with those who don't depend on C .i know that musn't combine terms including don't cares but all terms here contains don't cares that makes all minterms uncombinable that why i've combined them in that way...

14. Dec 2, 2005

### matejhowell

when is this due?

15. Dec 3, 2005

### electronic engineer

I have about two weeks for this homework to be done! have you got any new thoughts?

could you tell please what are you studying now , how old are you , where are you from... some info about you?!

thanks!

16. Dec 6, 2005

### matejhowell

Hey.

My name is Matthew Howell, I'm living in Pensacola, FL. In a week I will have a bachelor's of computer engineering. I'm 22 I also have dial-up, so that is why my replies are so sparse. But we have time to work. Sorry I can't add more, but I am working out the problem and the next post should be the solution plus work.

17. Dec 6, 2005

### electronic engineer

thanks a lot my friend! we can discuss about other important subjects in electronics later

thanks for your interest , keep in touch!

18. Dec 9, 2005

### matejhowell

1) Determine the minterms. If they are not given, this is best done in a truth table. We need to know all the min terms, because some of the combinations look hidden

F=ABC' + ACD' + A'B'D + B'CD + A'C'D

Code (Text):

_  ABCD|F
-------+-
0  0000|0
1  0001|1 A'B'D, A'C'D
2  0010|0
3  0011|1 A'B'D, B'CD
4  0100|0
5  0101|1 A'C'D
6  0110|0
7  0111|0
8  1000|0
9  1001|0
10 1010|1 ACD'
11 1011|1 B'CD
12 1100|1 ABC'
13 1101|1 ABC'
14 1110|1 ACD'
15 1111|0

This means I have the terms (1, 3, 5, 10, 11, 12, 13, 14).

2) List all minterms, grouped by the number of ones they contain. Make a second column, and put in it all the combinations that can be made for pairs that only differ by one variable, and have the -'s in the same location. Note which ones "graduate" to the next column (by graduate, I mean this term has been used in a subsequent column).

Code (Text):

Ones | Term | ABCD | Grad? |     Terms  | ABCD
-----+------+------+-------+     -------+-----
1    | 1    | 0001 | Yes   |     1, 3   | 00-1
-----+------+------+-------+     1, 5   | 0-01
2    | 3    | 0011 | Yes   |     -------+-----
_    | 5    | 0101 | Yes   |     3, 11  | -011
_    | 10   | 1010 | Yes   |     5, 13  | -101
_    | 12   | 1100 | Yes   |     10, 11 | 101-
-----+------+------+-------+     10, 14 | 1-10
3    | 11   | 1011 | Yes   |     12, 13 | 110-
_    | 13   | 1101 | Yes   |     12, 14 | 11-0
_    | 14   | 1110 | Yes   |

Hmm. Now you will note we cannot go any further. 1,3 is only "eligible" to combine with 12,14 (because their -'s are in the same location), but cannot because they differe in more than one variables (A, B, and D). 1,5 is "eligible" to combine with 10,14, but they can't because of the same problem.

3) You have just listed all of your implicants, and all of the implicants that graduated the furthest are prime implicants (1,3 is a prime implicant, but 1 by itself is not a PI because it was combined with 3). Now we need to find our Essential Prime Implicants and a Minimal Prime Implicant List (I think that is the proper name for it). To do this, we create an EPI map. This is a challenge without a scanner, but I will see what happens :-)

So, to do this, make a table with the PI on the left, and the minterms of the function on the top

Code (Text):

PI's   | 1  3  5  10 11 12 13 14
-------+------------------------
1, 3   | X  X
1, 5   | X     X
3, 11  |    X        X
5, 13  |       X           X
10, 11 |          X  X
10, 14 |          X           X
12, 13 |                X  X
12, 14 |                X     X

Now, all the X's that only appear in one column indicate that this PI (row) is an essential PI. Unfortunately, I have no essential PI in my problem. But say for example, 12,13 and 12,14 were not in my function. This would mean 5,13 is an EPI (to cover 13) and 10,14 is an EPI (to cover 14).

So, the next step, more of a substep, is to choose which PI's to include. This is arbitrary, as long as all minterms are accounted for. Attached to this post is a solution I found.

I marked the PI's I chose with a black horizontal line, and after I chose them, I marked all the redundant minterms that were already taken care of with this PI in a vertical green line.

4) Rewrite the new simplified equation by taking the covering list and converting them to product terms.
Code (Text):

1, 3   ==> 00-1 ==> A'B'D
5, 13  ==> -101 ==> BC'D
10, 11 ==> 101- ==> AB'C
12, 14 ==> 11-0 ==> ABD'

So, F = A'B'D + BC'D + AB'C + ABD'

Sorry it took so long :-( I hope this still helps, and was clear.

#### Attached Files:

• ###### coveringList.gif
File size:
1.8 KB
Views:
90
19. Dec 9, 2005

### electronic engineer

indeed i could understand the steps 1,2 but regarding the last two steps, i'm confused about it ... you said that there's no p-I cause there isn't any column that includes one X all have two x's and we have to find the minimal subset of prime-implicants since that line of your post I didn't understand anything (for example about the 5,13 and 10,14)

anyway , thanks a lot!
hope for more clarifying

best regards!

20. Dec 9, 2005

### matejhowell

Well, not that there are no PI's, but there are no essential PI's. An essential prime implicant is one that covers a min term that no other prime implicant covers. But in this problem, every min term is included in two different prime implicants (1 is in 1,3 and 1,5; 10 is in 10,11 and 10,14). So, since their are no minterms that appear in only one grouping, there are no essential prime implicants.

And, as far as that graph in part 3 goes, those X's were a bad choice of symbol. They are not X in the sense of "don't cares", but only marks, like plotting points. When I write it on paper, I write a dot, or an X, or a squiggle. You could probably look at it like
Code (Text):

PI's   | 1  3  5  10 11 12 13 14
-------+------------------------
1, 3   | *  *
1, 5   | *     *
3, 11  |    *        *
5, 13  |       *           *
10, 11 |          *  *
10, 14 |          *           *
12, 13 |                *  *
12, 14 |                *     *

Does that help any? -- MLH