In thinking about the propagation delay of a ripplecarry adder, we see that the higherorder bits are "waiting" for their carryins to propagate up from the lowerorder bits. Suppose we split off the highorder bits and create two separate adders: one assuming that the carryin was 0 and the other assuming the carryin was 1. Then when the correct carryin was available from the loworder bits, it could be used to select which highorder sum to use. The diagram below shows this strategy applied to an 8bit adder:
 Compare the latency of the 8bit carryselect adder show above to a regular 8bit ripplecarry adder.
 The logic shown for C_{8} seems a bit odd. One might have expected C_{8} = C_{8,0} + (C_{4}*C_{8,1}). Explain why both implementations are equivalent and suggest why the logic shown above might be prefered. Hint: What can we say about C_{8,1} when C_{8,0}=1?
Solution:
For the loworder 4 bits, the latency is the same for both implementations: T_{PD,4BIT ADDER}. But with the carryselect adder, the remaining latency is the propagation delay of the 4bit 2:1 multiplexer (T_{PD,2:1 MUX}) instead of the longer time it takes for the carry to ripple through another 4 bits of adder (T_{PD,4BIT ADDER}). If we consider an Nbit adder, the latencies are:
T_{PD,NBIT RIPPLE} = 2 * T_{PD,(N/2)BIT RIPPLE}
T_{PD,NBIT CARRYSELECT} = T_{PD,(N/2)BIT RIPPLE} + T_{PD,2:1 MUX}
As N gets large the carryselect adder is almost twice as fast as a ripplecarry adder since the delay through the 2:1 mux is independent of N. The carryselect strategy can be applied recursively to the (N/2)bit ripplecarry adder, and so on, ultimately producing an adder with O(log_{2}N) latency.

If we think about carry generation, it's easy to see that if C_{8,0}=1 then C_{8,1}=1, i.e., if we get a carry with C_{IN}=0, we'll also get a carry when C_{IN}=1. Using this fact we can do a little Boolean algebra:
C8 = C8,0 + (C4 * C8,1)
____
= C8,0*(C8,1 + C8,1) + (C4 * C8,1)
____
= (C8,0 * C8,1) + (C8,0 * C8,1) + (C4 * C8,1)
= (C8,0 * C8,1) + 0 + (C4 * C8,1)
= (C8,0 + C4)*C8,1
In the worst case (the carryin rippling all the way up), C_{8,1} will take a little longer to compute than C_{8,0}, so the logic for C_{8} shown in the diagram will be a little faster since it provides the shorter path to C_{8}.
Articles you may have missed:
{ 0 Reactions ... read them below or write one }
Post a Comment