an unsigned 2-bit adder

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
    Thank you for your kindly reply.

    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?

    What about 1+2?
    What about 3+0?

    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
    thank you for your remind. I know your meaning,
    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
    Okay, your table looks fine.

    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
    No answer has given.
    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.
Loading...