Advertisement

On Teaching Fast Adder Designs: Revisiting Ladner & Fischer

  • Guy Even
Chapter
Part of the Lecture Notes in Computer Science book series (LNCS, volume 3895)

Abstract

We present a self-contained and detailed description of the parallel-prefix adder of Ladner and Fischer. Very little background is assumed in digital hardware design. The goal is to understand the rational behind the design of this adder and view the parallel-prefix adder as an outcome of a general method.

Keywords

Clock Cycle Output Port Input Port Input Symbol Combinational Circuit 
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

References

  1. [BrentKung82]
    Brent, R.P., Kung, H.T.: Regular Layout for Parallel Adders. IEEE Trans. Comp. C-31(3), 260–264 (1982), Available online at http://web.comlab.ox.ac.uk/oucl/work/richard.brent/pd/rpb060.pdf Google Scholar
  2. [CLR90]
    Cormen, T.H., Leiserson, C.E., Rivest, R.L.: Introduction to Algorithms. The MIT Press, Cambridge (1990)zbMATHGoogle Scholar
  3. [ErceLang04]
    Ercegovac, M.D., Lang, T.: Digital Arithmetic. Morgan Kaufmann, San Francisco (2004)Google Scholar
  4. [Even79]
    Even, S.: Graph Algorithms. Computer Science Press, Rockville (1979)zbMATHGoogle Scholar
  5. [Even04]
    Even, G.: Lecture Notes in Computer Structure. manuscript (2004)Google Scholar
  6. [EvenLitman91]
    Even, S., Litman, A.: A systematic design and explanation of the Atrubin multiplier. In: Capocelli, R., et al. (eds.) Sequences II, Methods in Communication, Security and Computer Sciences, pp. 189–202. Springer, Heidelberg (1993)Google Scholar
  7. [EvenLitman94]
    Even, S., Litman, A.: On the capabilities of systolic systems. Mathematical Systems Theory 27, 3–28 (1994)zbMATHCrossRefMathSciNetGoogle Scholar
  8. [HopUll79]
    Hopcroft, J.E., Ullman, J.D.: Introduction to automata theory, languages, and computation. Addison Wesley, Reading (1979)zbMATHGoogle Scholar
  9. [Knowles99]
    Knowles, S.: A Family of Adders. In: Proceedings of the 14th IEEE Symposium on Computer Arithmetic, pp. 30–34 (1999) (Note that the figures in the published proceedings are wrong)Google Scholar
  10. [Koren93]
    Koren, I.: Computer Arithmetic Algorithms. Prentice-Hall, Englewood Cliffs (1993)Google Scholar
  11. [Kornerup97]
    Kornerup, P.: Chapter 2 on Radix Integer Addition. manuscript (1997)Google Scholar
  12. [LadnerFischer80]
    Ladner, R., Fischer, M.: Parallel prefix computation. J. Assoc. Comput. Mach. 27, 831–838 (1980)zbMATHMathSciNetGoogle Scholar
  13. [Leighton91]
    Thomson Leighton, F.: Introduction to parallel algorithms and architectures: array, trees, hypercubes. Morgan Kaufmann, San Francisco (1991)Google Scholar
  14. [LeiSaxe81]
    Leiserson, C.E., Saxe, J.B.: Optimizing synchronous systems. Journal of VLSI and Computer Systems 1, 41–67 (1983) (Also appeared in Twenty- Second Annual Symposium on Foundations of Computer Science, pp. 23-36, 1981)zbMATHGoogle Scholar
  15. [LeiSaxe91]
    Leiserson, C.E., Saxe, J.B.: Retiming synchronous circuitry. Algorithmica 6(1), 5–35 (1991)zbMATHCrossRefMathSciNetGoogle Scholar
  16. [MüllerPaul00]
    Müller, S.M., Paul, W.J.: Computer Architecture: complexity and correctness. Springer, Heidelberg (2000)zbMATHGoogle Scholar
  17. [Ofman63]
    Ofman, Y.: On the algorithmic complexity of discrete functions. Sov. Phys. Dokl. 7, 589–591 (1963)MathSciNetGoogle Scholar
  18. [Shiloach76]
    Shiloach, Y.: Linear and planar arrangements of graphs, Ph.D. thesis, Dept. of Applied Mathematics, Weizmann Institute (1976)Google Scholar
  19. [Sklansky60]
    Sklansky, J.: An evaluation of several two-summand binary adders. IRE Trans. on Electronic Computers EC-9, 213–226 (1960)CrossRefMathSciNetGoogle Scholar
  20. [Thompson80]
    Thompson, C.D.: A Complexity Theory For VLSI, PhD Thesis, Carnegie Mellon University (1980)Google Scholar
  21. [WeinSmith58]
    Weinberger, A., Smith, J.L.: A logic for high-speed addition. Nat. Bur. Stand. Circ. 591, 3–12 (1958)Google Scholar
  22. [Zimmerman98]
    Zimmermann, R.: Binary Adder Architectures for Cell-Based VLSI and their Synthesis, PhD thesis, Swiss Federal Institute of Technology (ETH) Zurich, Hartung-Gorre Verlag (1998), Available online at http://www.iis.ee.ethz.ch/~zimmi/

Copyright information

© Springer-Verlag Berlin Heidelberg 2006

Authors and Affiliations

  • Guy Even
    • 1
  1. 1.School of Electrical EngineeringTel-Aviv UniversityIsrael

Personalised recommendations