In this paper, we study area-time tradeoffs in VLSI for prefix computation using graph representations of this problem. Since the problem is intimately related to binary addition, the results we obtain lead to the design of area-time efficient VLSI adders. This is a major goal of our work: to design very low latency addition circuitry that is also area efficient. To this end, we present a new graph representation for prefix computation that leads to the design of a fast, area-efficient binary adder. The new graph is a combination of previously known graph representations for prefix computation, and its area is close to known lower bounds on the VLSI area of parallel prefix graphs. Using it, we are able to design VLSI adders having area A = 0(n log n) whose delay time is the lowest possible value, i. e. the fastest possible area-efficient VLSI adder.
|Title of host publication||Computer Arithmetic|
|Subtitle of host publication||Volume I|
|Publisher||World Scientific Publishing Co.|
|Number of pages||8|
|Publication status||Published - 2015 Jan 1|
Bibliographical notePublisher Copyright:
© 1987 by The Institute of Electrical and Electronics Engineers, Inc.
All Science Journal Classification (ASJC) codes
- Computer Science(all)