Quinne-MCCluskey simplification

[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!

thanks in advance!

 

[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!
best regrads!

 

[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!
best regrads!

 

[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!
best regrads!

 

[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!
best regrads!

 

[berkeman]

You're making me dizzy!

 

[electronic engineer]

You're making me dizzy!

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

thanks for interesting!

 

[matejhowell]

How did you get the PI of 0xx1?

 

[electronic engineer]

How did you get the PI of 0xx1?

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

anyway , as long you know about this algorithm, could you give me some info or links about it..
thank for reply!

 

[electronic engineer]

sorry

sorry ,wrong in spelling (I got 0xx1)

 

[matejhowell]

Almost right

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

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.

 

[matejhowell]

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

 

[electronic engineer]

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.
I'll add more later. Tell me what you think.

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...

anyway thanks for your support!

need more advices, thanks alot!

 

[matejhowell]

when is this due?

 

[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!

 

[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.

 

[electronic engineer]

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.

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

thanks for your interest , keep in touch!

 

[matejhowell]

Answer

About the problem.

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

_  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).

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

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.

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.

 

[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!

 

[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

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

 

[electronic engineer]

excuse me my friend. I'm still confused about the problem...
could you give me a useful link on internet you depended on to solve my problem ...

please help me!

best regards!