Full Adder Implementation

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

Full Adder Implementation

Sobbity
Greetings, just recently started working on these projects and was wondering what the minimum number of gates for the more "direct" implementation of the Full-Adder would be, without the usage of Half-Adders. I know it's a bit too specific a question but I just want to know if I'm tackling these problems correctly
Reply | Threaded
Open this post in threaded view
|

Re: Full Adder Implementation

ybakos
You could write down a boolean expression that represents your full adder, and use the principles of boolean algebra to simplify the expression. That would yield a different circuit design.
Reply | Threaded
Open this post in threaded view
|

Re: Full Adder Implementation

cadet1620
Administrator
In reply to this post by Sobbity
Sobbity wrote
Greetings, just recently started working on these projects and was wondering what the minimum number of gates for the more "direct" implementation of the Full-Adder would be, without the usage of Half-Adders.
Depends on what a "gate" is and what you're trying to minimize. For instance, the minimum implementation of a half adder is an Xor and an And. Using 2 of these and an Or to combine the carries would get you a 5 gate solution.

For a 2-input Nand only gate count minimization, there is a 4 Nand Xor that you can use. It has internal gates that you can use to generate the carry with just one more Nand, so that would be be 9 gates.

For speed optimization you need to know what type of IC you are designing for. Different IC families can implement logic in more efficient ways then 2-input Nand gates only.  TTL for instance can implement N-input Nand for no extra delay and very little extra silicon. It's perfect for sum of products implementations. Calling Not a 1-input Nand gate, you can build a full adder with 12 Nand gates that has only 2 gate delays for carry and 3 gate delays for sum.

For CMOS, there are many optimization tricks that involve non-traditional logic like transmission gates and bi-directional pass transistors. I've seen a 14 transistor design.

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

Re: Full Adder Implementation

Sobbity
Thank you very much for such a detailed response.

cadet1620 wrote
Depends on what a "gate" is and what you're trying to minimize. For instance, the minimum implementation of a half adder is an Xor and an And. Using 2 of these and an Or to combine the carries would get you a 5 gate solution.
I guess my main issue here is I haven't yet fully grasped exactly what I can do with Boolean algebra and the best way to simply an expression. I had no problem reaching the two HalfAdders + one Or solution as I had been following the book linearly (Which has proved to be fantastic thus far). Then, when going for the more direct approach, I arrived to a 5 gate implementation such as you say but I would say it was purely chance and fooling around in whatever direction seemed right, with no certainty.

I can do the algebra individually for both the sum and carry bits, but that yields me a 7 gate implementation since I cannot combine the AB+BC+AC result for the carry function with the sum's, or can I?

I've been going through this book step by step but beyond that I've got zero knowledge of what the appropriate way to express these questions is, so I apologize in advance if what I say isn't too clear. Also in regards to the rest of your post, it is very informative! For now though, the only thing I want to optimize is my comprehension, haha. Thanks again
Reply | Threaded
Open this post in threaded view
|

Re: Full Adder Implementation

cadet1620
Administrator
Sobbity wrote
I guess my main issue here is I haven't yet fully grasped exactly what I can do with Boolean algebra and the best way to simply an expression.
Like normal algebra, Boolean algebra is most useful to prove or disprove a solution that you have already come up with by other means.  There are rules and guidelines for simplifying equations as in normal algebra, but they only get you so far.

A good tool for simplifying canonical representations into sum-of-product solutions is Karnaugh Maps. There are several posts about them on the forum.
 I had no problem reaching the two HalfAdders + one Or solution as I had been following the book linearly (Which has proved to be fantastic thus far). Then, when going for the more direct approach, I arrived to a 5 gate implementation such as you say but I would say it was purely chance and fooling around in whatever direction seemed right, with no certainty.
Intuition and experience will help. General problem solving techniques like working from both ends of the problem are useful, too.
For now though, the only thing I want to optimize is my comprehension, haha. Thanks again
That's one of my life goals too! One is never too old to learn.

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

Re: Full Adder Implementation

Sobbity
I can't tell you how many of my doubts have been dispelled thanks to you guys' posts on this forum. Very much appreciated