Carry save adder

From Wikipedia, the free encyclopedia

You have new messages (last change).

A carry-save adder is a type of digital adder, used in computer microarchitecture to compute the sum of three or more n-bit numbers in binary. It differs from other digital adders in that it outputs two numbers of the same dimensions as the inputs, one which is a sequence of partial sum bits and another which is a sequence of carry bits.

The carry-save unit consists of n full adders, each of which computes a single sum and carry bit based solely on the corresponding bits of the three input numbers. Given the three n - bit numbers a, b, and c, it produces a partial sum ps and a shift-carry sc:

ps_i = a_i \oplus b_i \oplus c_i
sc_i = (a_i \cdot b_i) + (a_i \cdot c_i) + (b_i \cdot c_i)

The entire sum can then be computed by:

  1. Shifting the carry sequence sc left by one place.
  2. Appending a 0 to the front (most significant bit) of the partial sum sequence ps.
  3. Using a ripple carry adder to add these two together and produce the resulting n + 1-bit value.

When adding together three or more numbers, using a carry-save adder followed by a ripple carry adder is faster than using two ripple carry adders. This is because a ripple carry adder cannot compute a sum bit without waiting for the previous carry bit to be produced, and thus has a delay equal to that of n full adders. A carry-save adder, however, produces all of its output values in parallel, and thus has the same delay as a single full-adder. Thus the total computation time (in units of full-adder delay time) for a carry-save adder plus a ripple carry adder is n + 1, whereas for two ripple carry adders it would be 2n.

Retrieved from "http://en.wikipedia.org../../../c/a/r/Carry_save_adder.html"