Discussion in 'Homework Help' started by chak6787, Apr 28, 2012.

1. chak6787 Thread Starter New Member

Mar 8, 2012
7
0
A1 and A0 represent one 2-bit input while B1 and B0 represent another input. The adder has three output bits (S2, S1, and S0).

A1 A0
+) B1 B0
S2 S1 S0

Question:
Using K-map, derive the simplest Boolean expression for the three output bits.

2. crutschow Expert

Mar 14, 2008
13,016
3,235
Do you know how to do a K-map?

3. WBahn Moderator

Mar 31, 2012
17,748
4,796
What's your question? You have given us the problem that you are supposed to solve, but have not indicated what you have done to try to solve it or what you are having trouble understanding or what help you requesting in order to accomplish that. What kind of response are you expecting?

4. WBahn Moderator

Mar 31, 2012
17,748
4,796
I always want to scream when I see something like this. What, pray tell, defines "the simplest Boolean expression"? How do you compare two Boolean expressions and decide which is "simpler"?

Which is simpler:

Y(A,B,C,D) = AB+CD

or

Y(A,B,C,D) = ((AB)'(CD)')'

The first looks cleaner because of how we chose to represent the operations, but the second requires a third fewer transistors (in basic CMOS), has half the propagation delay, and can be implemented with a single quad NAND gate chip instead of requiring two different SSI chips.

So which is "simpler"?

It's one of my pet peeves when instructors and, especially, authors of textbooks ask for answers to qualitative questions and completely ignore to establish the metrics by which quality is to be assessed. It's a huge disservice to students.

To be fair, I don't know that the author of this problem didn't establish what "simplest" means in this context, but I'd be willing to bet that they didn't.

Also, to be fair, I can't say that I have never done anything similar, but I believe I do it for less often now and that I try to make clear either what the metrics are or that I am open to any 'reasonable' metric the student wishes to establish, subject to the caveat that I am the ultimate arbiter of what is and what is not reasonable. Doing it that way makes it harder to grade, but I think gets the student to think about and make decisions regarding issues that are not black and white and also how to make qualitative assessments quantitative.

5. chak6787 Thread Starter New Member

Mar 8, 2012
7
0

A1 A0
+) B1 B0
S2 S1 S0

First, let the A1 = A, A0 = B, B1 = C, B0 = D, S2 = X, S1 = Y, and S0 = Z
Then, I had using the truth table to construct the output.
Finally, I got the the following:
X = ABD+AC+BCD
Y = A EX-OR C
Z = B EX-OR D
but, i don't know that is the x simplest?

6. WBahn Moderator

Mar 31, 2012
17,748
4,796
Before asking if you have the simplest answer, be sure to establish that you have a correct answer.

For example, using your equations, does 1+1 equal 2?

BTW: You are close.

7. chak6787 Thread Starter New Member

Mar 8, 2012
7
0
um... i got some mistake,
Y should be ((A ex-or C)B'D') + ((A ex-or C)' BD))
after that, let E = (a ex-or c)
Y = EB'D' + E'BD
then... i don't know how to simple it
I think that it can be more simpler.

8. WBahn Moderator

Mar 31, 2012
17,748
4,796
The exclusive-OR operation is generally written as XOR or xor, not ex-or.

Are you sure your new expression for Y is correct?

You need to develop both the habit and the ability to check your own work. As a practicing engineer, there will generally not be anyone to check your work for you; they are paying you to solve a problem because they can't. And, yes, we fully realize that you are in the learning stages of becoming an engineer, which is why we work with you in a way that, hopefully, forces you to move in the right direction.

9. chak6787 Thread Starter New Member

Mar 8, 2012
7
0
a + b = a + a'b
we need to simplify the function as less gate can be used.
but i still want to know the correct answer.

10. WBahn Moderator

Mar 31, 2012
17,748
4,796
Now I don't know your meaning.

It's true that a+a'b = a+b, but that is not the issue here (or at least not the issue I am trying to point out).

For:

AB + CD = XYZ

What SHOULD Y be if AB = 10 (i.e., 2) and CD = 01 (i.e., 1)?

What WILL it be using your equations?

You might consider posting the truth table that you are working with.

11. chak6787 Thread Starter New Member

Mar 8, 2012
7
0
A b c d x y z
0 0 0 0 0 0 0
0 0 0 1 0 0 1
0 0 1 0 0 1 0
0 0 1 1 0 1 1
0 1 0 0 0 0 1
0 1 0 1 0 1 0
0 1 1 0 0 1 1
0 1 1 1 1 0 0
1 0 0 0 0 1 0
1 0 0 1 0 1 1
1 0 1 0 1 0 0
1 0 1 1 1 0 1
1 1 0 0 0 1 1
1 1 0 1 1 0 0
1 1 1 0 1 0 1
1 1 1 1 1 1 0

12. WBahn Moderator

Mar 31, 2012
17,748
4,796

I am reformatting your table but not changing any of the content:

 AB CD XYZ E = A xor C F = EB'D' G = E'BD Y = F+G 00 00 000 00 01 001 00 10 010 00 11 011 01 00 001 01 01 010 01 10 011 01 11 100 10 00 010 10 01 011 10 10 100 10 11 101 11 00 011 11 01 100 11 10 101 11 11 110

Now go through and add the E (A xor C), the two terms in your expression for Y and the resulting Y from your equation and see if it produces the correct result for each row.

13. WBahn Moderator

Mar 31, 2012
17,748
4,796
Did you hit "Post" too soon? This is the same table as before (and the table is correct).

14. chak6787 Thread Starter New Member

Mar 8, 2012
7
0
Is Y = ((A xor C)(B' + D')) + (BD ( A xor C)')
let E = (A xor C)

is the answer equal E(B' + D') + BDE'?
simplest?

15. WBahn Moderator

Mar 31, 2012
17,748
4,796
You should be able to check this for yourself. Fill in the table I provided for you (except use your new equation).

Does your equation produce the correct result for each row?

16. chak6787 Thread Starter New Member

Mar 8, 2012
7
0
3+1? 11 + 01 = 100(2) = 4(10)
X = 1, Y = 0, Z = 0
Then, check it in truth table:
Y = ((A xor C)(B' + D')) + (BD ( A xor C)')
Y = ((1 xor 0)(1' + 1')) + (11 ( 1 xor 0)')
Y = ((1)(0))+(11(1)')
Y = 0 + (110)
Y = 0 + 0
Y = 0
it is correct.
But, can i write a more simpler answer?

17. WBahn Moderator

Mar 31, 2012
17,748
4,796
I agree that your equations are now correct and we can move on to the "simplest" part of the problem.

We now run straight into the issue I talked about near the beginning of the thread. What makes one solution "simpler" than another? There are several reasonable metrics and they are far from consistent with each other. I have no idea what the author of this particular problem had in mind when they wrote it.

If the point of the exercise is to work with K-maps, the frequently they just want the fewest terms and the fewest inputs for each term. They want to see if you can use the map to remove unnecessary elements from terms, not whether you can identify XOR gates or the fasted propagation leveraging NAND/NOR over AND/OR. But if point is to come up with the lowest delay logic, then these issues are back on the table.

For X

X = ABD + AC + BCD

I would argue that

X = [(AC)'(ABD)'(CBD)']'

Is considerably 'simpler', but I am using a metric of fewest transistors and/or smallest delay.

Aesthetically, you could argue that

X = AC + (A+C)BD

is 'simpler' and perhaps conveys the conceptual logic more clearly.

Similarly, for Y

Y = ((A xor C)(B' + D')) + (BD ( A xor C)')

I would argue that

Y = (A xor C) xor (BD)

Looks simpler, but in terms of a concise written expression, but

Y = (A xor C) xnor (BD)'

is, requires fewer transistors and is at least as fast. While

Y = [(A'B'C)'(A'BD')'(A'BC'D)'(ABCD)'(AC'D')'(AB'C)']'

is the fastest (but probably can't be considered 'simplest' in any reasonable way).

chak6787 likes this.