0
\$\begingroup\$

In my little time studying digital systems, it seems that textbooks immediately jump to the fact that we implement adders via serial (i.e. the chaining together of) full adders. It's not a priori clear to me why we do this. In particular, since this is still a combinational circuit, why can't we write out the truth table (obviously, for large numbers we'd let CAD systems do this) and derive an optimized set of logic functions for each sum bit and the final carry out bit? Is this intractable? Is this equivalent to the serial full adder implementation? Any references discussing why we don't do this would be greatly appreciated!

EDIT to the above: I am familiar with lookahead adders and the like. The fact remains that these "begin" with chaining together one-bit adders, admittedly with some slick optimizations. Again, it's not a priori clear to me why we don't implement the "full" n-bit adder with combinational logic optimization techniques.

\$\endgroup\$
5
  • \$\begingroup\$ Google "carry-lookahead adder" and "carry-skip adder". It is commonly done. \$\endgroup\$ Commented Feb 26, 2022 at 15:34
  • \$\begingroup\$ No matter how big the word is, at its heart is a 1-bit adder so, maybe you should look at different ways a 1-bit adder can be implemented or maybe you can show that for (say) a 4 bit adder, a different approach is superior to chaining four regular adders? \$\endgroup\$
    – Andy aka
    Commented Feb 26, 2022 at 15:35
  • \$\begingroup\$ I edited my question to clarify that I am wondering why the heart of all adders (including CLAs) we use is indeed a one-bit adder (if indeed this is equivalent to what would obtain if one used standard combinational logic optimization techniques then it's not at all clear to me why that is). \$\endgroup\$
    – EE18
    Commented Feb 26, 2022 at 15:39
  • 2
    \$\begingroup\$ why can't we write out the truth table (obviously, for large numbers we'd let CAD systems do this) and derive an optimized set of logic functions for each sum bit and the final carry out bit? Do it yourself manually, for 2 bits, 3 bits, 4 bits, maybe 5 bits, and see if there's a general scaling rule for the propagation delays, the amount of logic, and the design time. Edit those findings into your question, or perhaps post an answer to your own question with them. \$\endgroup\$
    – Neil_UK
    Commented Feb 26, 2022 at 15:51
  • \$\begingroup\$ I am only a casual reader of academic papers on digital logic, but I think I see as many papers on adder architecture as on anything else, combined. A search on "optimized adder architecture" or similar will get you papers by the people who are actually impacting what goes into silicon these days. I suggest a search, and some reading, and then if you find something definitive one way or another, post an answer to your question. \$\endgroup\$
    – TimWescott
    Commented Feb 26, 2022 at 15:59

2 Answers 2

0
\$\begingroup\$

For the smallest circuit, the truth table would be best satisfied by the chain of full adders with ripple carry.

Or it could be done by a look-up table (a ROM), which would use vastly more gates and therefore either be slower or a waste of gates or both, for nearly all adder applications. The latter is weighing up the huge number of small counters in logic designs as well as the fewer large CPU ALU adders.

\$\endgroup\$
0
\$\begingroup\$

Adder structure is inherently sequential because of the carry propagation. Think about how we add numbers together. If you have 1001 + 9999, you’ll need to wait for the carry to propagate all the way through from the least significant digits to the most significant digit.

All the look ahead adders are attempting to shorten the carry propagation delay by adding more gates. For example, the Kogge-Stone Adder has logarithmic carry propagation delay instead of the linear delay of a ripple adder.

In fact, this is a big problem when fast counters are required. When you have a large pipeline that runs as fast as the technology would allow you need to count the number of cycles until it is filled. However, a counter comprising an adder cannot propagate as fast. To avoid this we use linear-feedback shift registers. Instead of counting from 0 to 99, they produce a seemingly random sequence of length 100, e.g. 256, 147, 5 etc. However, the propagation delay is one logic gate.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.