The Basic Concept
The idea of delaying carry resolution until the end, or saving carries, is due to John von Neumann.
Here is an example of a binary sum:
10111010101011011111000000001101
.
+ 11011110101011011011111011101111
Carry-save arithmetic works by abandoning the binary notation while still working to base 2. It computes the sum digit by digit, as
10111010101011011111000000001101
.
+ 11011110101011011011111011101111
= 21122120202022022122111011102212
The notation is unconventional but the result is still unambiguous. Moreover, given n adders (here, n=32 full adders), the result can be calculated in a single tick of the clock, since each digit result does not depend on any of the others.
If the adder is required to add two numbers and produce a result, carry-save addition is useless, since the result still has to be converted back into binary and this still means that carries have to propagate from right to left. But in large-integer arithmetic, addition is a very rare operation, and adders are mostly used to accumulate partial sums in a multiplication.
Read more about this topic: Carry-save Adder
Famous quotes containing the words basic and/or concept:
“The research on gender and morality shows that women and men looked at the world through very different moral frameworks. Men tend to think in terms of justice or absolute right and wrong, while women define morality through the filter of how relationships will be affected. Given these basic differences, why would men and women suddenly agree about disciplining children?”
—Ron Taffel (20th century)
“Terror is as much a part of the concept of truth as runniness is of the concept of jam. We wouldnt like jam if it didnt, by its very nature, ooze. We wouldnt like truth if it wasnt sticky, if, from time to time, it didnt ooze blood.”
—Jean Baudrillard (b. 1929)