A REGULAR LAYOUT FOR PARALLEL ADDERS

RICHARD P. BRENT AND H. T. KUNG

Abstract

With VLSI architectures, the chip area and design regularity represent a better measure of cost than the conventional gate count. We show that addition of n-bit binary numbers can be performed on a chip with a regular layout in time proportional to log n.

Comments

Only the Abstract is given here. The full paper appeared as [1]. At the time of publication the use of carry-lookahead in VLSI designs was unpopular [3, Section 5.5], but more recently the Brent-Kung design technique has been applied widely in VLSI implementations of adders [4, Section 8.2.6]; also [2, A59–A61].

References

[1] R. P. Brent, and H. T. Kung, “A regular layout for parallel adders”, IEEE Transactions on Computers C–31 (1982), 260–264. MR 83b:68002. Also appeared as Report TR-CS-79-04, Department of Computer Science, ANU; and as Report TR CMU-CS-79-131, Department of Computer Science, Carnegie-Mellon University (June 1979), 16 pp. rpb060.

[2] J. L. Hennessy and D. A. Patterson, Computer Architecture: A Quantitative Approach, Morgan Kaufmann, San Mateo, California, 1990.

[3] C. Mead and L. Conway, Introduction to VLSI Systems, Addison-Wesley, Reading, Mass., 1980.

[4] N. Weste and K. Eshraghian, Principles of CMOS VLSI Design, Addison Wesley, Reading, Mass., 1985.

(Brent) Department of Computer Science, Australian National University, Canberra

(Kung) Department of Computer Science, Carnegie-Mellon University, Pittsburgh, PA 15213

1991 Mathematics Subject Classification. Primary 68Q25; Secondary 65Y05, 65Y10, 65Y20, 68M07. Key words and phrases. Addition, area-time complexity, carry lookahead, circuit design, combinational logic,

models of computation, parallel addition, parallel polynomial evaluation, prefix computation, VLSI. Manuscript received May 12, 1980; revised February 3, 1981 and October 1, 1981. This work was supported in part by the National Science Foundation under Grant MCS78-236-76 and the

Office of Naval Research under Contracts N000014-76-C-0370, NR 044-422 and N00014-80-C-0236, NR 048-659. Copyright \begin{matrix}c \\ ◯ \end{matrix} 1982, IEEE.. Comments \begin{matrix}c \\ ◯ \end{matrix} 1993, R. P. Brent.

rpb060a typeset using AMS-L^{A}TEX.