The Chip Complexity of Binary Arithmetic

The chip complexity of a computation is concerned with the chip area, A, and the time, T, required to perform the computation when implemented on a chip. An area-time product AT α ,for α ≥ 0, is used as a complexity measure. A particular value of α, which is chosen by the user, reflects the relative importance between A and T. This paper derives lower and upper bounds on the area-time complexity for chips that implement binary arithmetic, assuming a model of computation which is intended to approximate, current and anticipated LSI or VLSI technology.

Authors

• Richard P. Brent
• H. T. Kung 0001

Keywords

No keywords are indexed for this paper.