2

Addition and Subtraction

Addition and subtraction are the basic operations in computer arithmetic. Multiplication and division are based on addition and subtraction. Fast adders (subtractors) are desirable not only for speeding up fundamental operations like addition and subtraction in arithmetic operation, but also for accelerating the multiplication and division which involve massive addition and subtraction. We discuss in this chapter the variation of two-operand adders with interest in their time complexity and area complexity. Ripple carry adders, conditional-sum adders, carry-completion adders and carry-lookahead adders will be introduced.

2.1 SINGLE-BIT ADDERS

2.1.1 Logical Devices

The Arithmetic Logic Unit (ALU) design aims to minimize time complexity for achieving high speed, as well as area complexity for cost reduction. In this book we limit our discussion to the logic level design. With a wide variety of logic families rapidly advancing, the electronic implementation is left for further study with trade offs in the density and cost and the speed and power dissipation.

Denote the time complexity as ΔT, and the area complexity as AT. We list in Table 2.1 the ΔT and AT for various logic gates which serve as fundamental units in ALU design. We limit the logic gates to n-input gates where 1 ≤ n ≤ 10. The measure of ΔT is 1Δg which is the propagation delay of a NAND gate or a NOR gate. The measure of AT is Ag which is the area required by one NAND gate or NOR gate.

Table ...

Get Arithmetic and Logic in Computer Systems now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.