Full-Adder (3 Gates)

classic Classic list List threaded Threaded
10 messages Options
Reply | Threaded
Open this post in threaded view
|

Full-Adder (3 Gates)

erwinleonardy
I managed to hook up the full-adder gate using 2 Half Adder gates and a very elementary gate. Without this gate I can't get the expected result for {a,b,c} = {1,1,0} and {a,b,c} = {1,1,1}. I know that that is allowed.

My question is: Can it be done with merely 2 Half Adder gates?

Thanks in advance.
Reply | Threaded
Open this post in threaded view
|

Re: Full-Adder (3 Gates)

cadet1620
Administrator
erwinleonardy wrote
Can it [full adder] be done with merely 2 Half Adder gates?
Full adder requires some simple logic in addition to the half adders.

--Mark
Reply | Threaded
Open this post in threaded view
|

Re: Full-Adder (3 Gates)

ouverson
Looking at truth table I see that if a==0 then half-adder, else half-adder not. I have played with many combinations of gates: 1 and 2 half-adders in combination with Mux, DMux and Not with no success.

It seems that I should be able to use 1 half-adder and invert if a==1. Not sure how to wire together an "if else" statement using gates.

I do enjoy "the hunt" so don't want you to give me the answer, but if you could point me in the right direction I'd much appreciate it.
Reply | Threaded
Open this post in threaded view
|

Re: Full-Adder (3 Gates)

WBahn
Administrator
A full adder can be implemented using three half adders.

Just track the math that you do by hand to add three one-bit numbers together under the constraint of only getting to add two one-bit numbers together at any one time. The logic design falls out immediately from those steps.
Reply | Threaded
Open this post in threaded view
|

Re: Full-Adder (3 Gates)

ouverson
As Half-Adders have 2 inputs and 2 outputs I figured (looking at my diagram) that a carry bit will need to be "dropped", as Full-Adder has 3 inputs. I recall Noam and Shimon mentioning this carry bit "dropping off" in the video.

No matter how I wire the 3 Half-Adders, the test fails? I figured that the 1st Half-Adder was where to set carry to true (I also tried false.)

Frankly, I thought that there would be an implementation where there would be 1 or 2 Half-Adders and some way to negate sum and carry, depending on whether a was 0 or 1 - as that was the way the truth table seemed to lead - logically.
Reply | Threaded
Open this post in threaded view
|

Re: Full-Adder (3 Gates)

WBahn
Administrator

Step back to the basics. We tend to overly complicate things when often the answer is staring us in the face by just thinking how we would have added three numbers together in second grade.

You have three one-bit inputs (call them X, Y, and Z) that you want to add together. First add X and Y and then add Z to that result, one digit position at a time. It really is that simple.

You use one half-adder to add X and Y to get the subtotal.

You use one half-adder to add Z to the units digit of the subtotal and the carry to the next digit position.

You use one half-adder to add the carry from the prior operation to the 2's digit of the original subtotal.

Not the most efficient implementation, but the most direct in terms of mapping the logic to the task.
Reply | Threaded
Open this post in threaded view
|

Re: Full-Adder (3 Gates)

ouverson
I got it, thanks to your "take it easy, take it slow" exhortation. I had it an hour ago or so, but had a sum and carry piped wrong.

Thanks much!
Reply | Threaded
Open this post in threaded view
|

Re: Full-Adder (3 Gates)

WBahn
Administrator
This post was updated on .
Don't worry, we'll get you there.

Think about how you add two normal decimal numbers together.

Unfortunately, I don't know how to force a fixed-width font so it's hard to make sure that things will line up properly, but let's say you wanted to add

 45
+37
-------

How would you do it (or, more to the point, how would a second grader do it)?

You add the one's digits -- the 5 and the 7 -- to get 12. You bring down the 2 as the one's digit of the final answer and you carry the 1 from the ten's digit and add it to the other ten's digit values -- the 4 and the 3v-- to get the final value for the ten's digit in the answer (plus possible a carry to the hundred's digit).

You do the same thing in binary, except instead of the digits being the one's, the ten's, the hundred's, etc, they are the one's, the two's, the four's, the eight's, etc.

If you need a refresher, go do a search on positional numbering systems.

Let's take the extreme example of three 1-bit numbers.

1+1+1

I add the first two together to get 10 using a half adder. This is my subtotal (or partial sum). I add the one's digit of the partial sum (which is 0) to the third number (which is 1) using a half adder and I get a result of 01. The one's digit from this IS the one's digit in my final sum. I know have two digits that have a weight of 2, the 1 from the first operation and the 0 from the second. I add those together to get 01. The 1 is the final two's digit and the 0 is the final four's digit. Since the sum of three one bit numbers is always less than four, I can ignore this output because it will always be zero.
 
Reply | Threaded
Open this post in threaded view
|

Re: Full-Adder (3 Gates)

ouverson
Thank you for spelling out the FullAdder. I was able to follow pretty close. One phrase caught me up a tad, "The 1 is the final two's digit and the 0 is the final four's digit"

When I add on paper there is no carry of 0 into the 4s position. My gate implementation has: "carry=false".

Thanks again; I don't know what I'd do without your help. You have a way of helping me think about the problem without giving away the solution/answer.

Thank you!
Reply | Threaded
Open this post in threaded view
|

Re: Full-Adder (3 Gates)

WBahn
Administrator
Thanks. That's the goal -- to help you through the specific issue you are currently having so that YOU can still do the bulk of the work in solving the overall problem. You learn a lot more that way, though it can certainly be more frustrating for everyone involved, especially you.