An integer addition can be represented as following:
$A + B = A \oplus B \oplus carry_{vector}$
My question is how to determine the carry vector from $A$ and $B$ (not from the result)?
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
The generation of the carry vector is a recursive process where the results of lower bits factor into the current carry output.
In general:
$$ Carry_{n} = (A_{n} \bullet B_{n}) + ((A_{n} \oplus B_{n}) \bullet Carry_{n-1}) $$ Note the $$ Carry_{n-1} $$ term. The presence of this term means that carry data ripples through the adder chain.
This is the reason that so much effort was devoted in older computer implementation technologies to speeding up this process. This was done by brute force computing the carry for groups of bits in a process called carry look-ahead. Let's see this for two bits:
$$ Carry_{n} = (A_{n} \bullet B_{n}) + ((A_{n} \oplus B_{n}) \bullet ((A_{n-1} \bullet B_{n-1}) + ((A_{n-1} \oplus B_{n-1}) \bullet Carry_{n-2}))) $$
As bits get added, this gets messy in a hurry.
The classic 74181 ALU used this method for the 4 bits handled by the chip and was often paired with the 74182 Carry Look Ahead chip to speed carry propagation by performing the same between up to four chips. If more that 16 bits needed to be processed, another layer of 74182 was employed to speed up carry propagation in the lower layer. Thus an ALU with 16 74181s, 4 74182s, and one top level 74182 could process 64 bits with a delay of roughly 3 times the four bit ALU delay, instead of 16 times.
It is noteworthy though, that there is no easy solution to the problem. Each added bit of look ahead, increases the complexity of the carry generator.
