Page 378 - Engineering Digital Design

8.5 MULTIPLE-NUMBER ADDITION AND THE CARRY-SAVE ADDER 349

Fig. 8.12. In fact, the nature of the adder stage to be cascaded in CLA form is immaterial
as long as the MSB module of each stage has G and P outputs to be connected to the CGP
network. In any case combining R-C and CLA technologies reduces hardware requirements
but, of course, does so at the expense of increasing path delay.

8.5 MULTIPLE-NUMBER ADDITION AND THE CARRY-SAVE ADDER

To add more than two binary numbers by the "conventional" methods discussed in Sections
8.3 and 8.4 requires that the addition process be carried out in stages, meaning that k
operands are added in k — 1 two-operand additions, each addition (following the first) being
that of the accumulated sum with a operand. This staged addition operation is relatively
slow since carries are propagated in each stage. However, addition of binary numbers is
not limited to two number addition stages. Actually, many binary numbers can be added
together in ways that reduces the total addition time. One way to accomplish this is to use a
type of "fast" adder called an iterative carry-save (ICS) adder. The algorithm for iterative
CS addition of more than two operands is stated as follows:

Algorithm 8.1: Sum S=*A + B + C + £> + £---by Carry-Save Method
(l)Setmtegers A=*A n _iA n -2-
Ci C 0, etc.
Q
(2) Sum S = A + R + C = Sj_,'Sj_ 2 • • • S?Sj exclusive of all carries-out CJ .
l l 2
(3) Sum S = 5° + D + C] = S,J_ { S n_ 2 • • • S\ S^ exclusive of all carries-out C 0 , but with
carries Cj shifted left by one bit,
2
s
l
(4) Sum S = S + M -f Cj^ S^S*^ ' ' ' tf l exclusive of all carries Cl but with
carries C^ shifted left by one bit,
(5) Continue process until last integer has been added and only two resultant operands
!
remain: pseudosuin S and final CS carries C' '.
(6) End with final sum S = S' + C' = S nS n-i - • • SiS 0 by using either R-C or CLA
addition,
The carry-save process described in Algorithm 8.1 applies to m integer operands and
involves m — 2 CS additions resulting in two operands: a pseudosum S' and the final CS
carries C'. The final step (step 6 in Algorithm 8.1) adds the two operands S' and C' by using
either a R-C adder or a CLA adder. The CS process (steps 1 through 5 in Algorithm 8.1)
avoids the ripple-carry problem of R-C adders, resulting in a savings of addition time. For
R-C adders of the type in Figs. 8.5 and 8.6, a time (m — l)t R- C would be required to add
m integer operands. However, for addition of m integer operands by the CS method, a time
(m — 2)t Cs + tR-c is required, which represents a significant savings of time for m > 3,
since tcs < tR-c for a given number of addition operations. If CLA addition is involved, the
time t R- C can be replaced by tciA with less savings in time between the two methods.
The iterative CS process just described in Algorithm 8. 1 is illustrated in Fig. 8. 15a where
four 4-bit integers, A, B, C, and D, are added. The ICS adder required for this process is
shown in Fig. 8.15b, where use is made of FAs, a HA, and either a R-C adder or a CLA
adder for the final sum operation.