Arithmetic and Logic in Computer Systems

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 A_T. We list in Table 2.1 the Δ_T and A_T 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 A_T is A_g which is the area required by one NAND gate or NOR gate.

Table ...