TABLE OF CONTENTS Another scheme for fast addition that provides a logarithmic speed-up is the conditional sum adder [29]. The principle behind this scheme is to generate two sets of outputs for a given group of operand bits, say, k bits. Each set includes k sum bits and an outgoing carry. One set assumes that the eventual incoming carry will be zero, while the other assumes that it will be one. Once the incoming carry is known, we need only to select the correct set of outputs (out of the two sets) without waiting for the carry to further propagate through the k positions (see Figure 5.3). Clearly, we should not apply this idea to all n operand bits at the beginning of the add operation, since we will then have to wait until the carry propagates through all n positions before making the selection. We need, therefore, to divide the given n bits into smaller groups and apply the above idea to each of them separately. In this way, the serial carry-propagation inside the separate groups can be done in parallel, reducing the overall execution time. These groups can, in turn, be further divided into subgroups, for which the carry-propagation time is even smaller. The outputs of the subgroups are then combined to generate the output of the groups.
A natural division of the n operand bits would be into...
