"Binary Adder Architectures for Cell-Based VLSI and their Synthesis"

R. Zimmermann

Abstract
--------

  The addition of two binary numbers is the fundamental and most often used
arithmetic operation on microprocessors, digital signal processors (DSP), and
data-processing application-specific integrated circuits (ASIC). Therefore,
binary adders are crucial building blocks in very large-scale integrated (VLSI)
circuits. Their efficient implementation is not trivial because a costly
carry-propagation operation involving all operand bits has to be performed.

  Many different circuit architectures for binary addition have been proposed
over the last decades, covering a wide range of performance characteristics.
Also, their realization at the transistor level for full-custom circuit
implementations has been addressed intensively. However, the suitability of
adder architectures for cell-based design and hardware synthesis - both
prerequisites for the ever increasing productivity in ASIC design - was hardly
investigated.

  Based on the various speed-up schemes for binary addition, a comprehensive
overview and a qualitative evaluation of the different existing adder
architectures are given in this thesis. In addition, a new multilevel
carry-increment adder architecture is proposed. It is found that the
ripple-carry, the carry-lookahead, and the proposed carry-increment adders show
the best overall performance characteristics for cell-based design.

These three adder architectures, which together cover the entire range of
possible area vs. delay trade-offs, are comprised in the more general prefix
adder architecture reported in the literature. It is shown that this universal
and flexible prefix adder structure also allows the realization of various
customized adders and of adders fulfilling arbitrary timing and area
constraints.

  A non-heuristic algorithm for the synthesis and optimization of prefix adders
is proposed. It allows the runtime-efficient generation of area-optimal adders
for given timing constraints.