Adders:Carry Skip Adder.

By -
Carry Skip Adder

In a ripple carry adder, a carry propagates through the i-th FA when xi ≠ yi, i.e., xi ⊕ yi = 1. Henceforth, we denote xi ⊕ yi as pi. A carry propagates through a block of consecutive FAs, when all pi’s in the block are 1. This condition (i.e., all pi’s are 1) is called the carry propagation condition of the block.

A carry skip adder is a ripple carry adder that is partitioned into several blocks of FAs, attaching a carry skip circuit to each block, as shown in Figure 41.8 [9]. A carry skip circuit detects the carry propagation condition of the block and lets the carry from the next lower block bypass the block when the condition holds. In Figure 41.8, carry skip circuits are not attached to the blocks at the most and least significant few positions because the attachment does not speed up the carry propagation much.

In the carry skip circuit included in Figure 41.8, the carry output, Ch+1, from block h that consists of k FAs starting from j-th position is calculated as:

Adders-0487

is the formula for the carry propagation condition of the block, Ch is the carry from the next lower block, and pi’s are calculated in FAs. An example of carry skip circuit is shown in Figure 41.9.

A carry may ripple through FAs in the block where it is generated, bypass the blocks where the carry propagation condition holds, and then, ripple through FAs in the block where the carry propagation condition does not hold. When all blocks are of the same size, k FAs, the worst case occurs when a carry is generated at the least significant position and propagate to the most significant position. The worst

Adders-0488

delay is the sum of the delay for rippling through k – 1 FAs, the delay for bypassing n/k – 2 blocks, and the delay for rippling through k – 1 FAs. In the case that k is a constant independent of n, as well as in the case that k is proportional to n, the delay is proportional to n. We can reduce the worst delay to being proportional to n , by letting k be proportional to n. The amount of hardware for the entire adder is proportional to n in any case.

Applying the principle used to develop the carry skip adder borrowed from the ripple carry adder, we have a two-level carry skip adder from the basic carry skip adder, for further improvements. Recursive application of the principle yields a multi-level carry skip adder [12].

Comments

Post a Comment

Popular posts from this blog

Square wave oscillators and Op-amp square wave oscillator.

By -
Image
Square wave oscillators If Fourier analysis is performed on a square wave it is found that the waveform is composed of many harmonics of the fundamental frequency. This rich harmonic content makes the square wave particularly useful as a quick test of amplifier performance. Examples of possible results are shown. The simplest way to produce a square wave is to make a sine wave oscillator in one of the ways described earlier, then feed the output to some form of squaring circuit such as a Schmitt trigger. This is the method adopted in most commercial sine/square wave generators. There are, however, several circuits for square wave oscillators and a description of the most common follows. Multivibrator Technically the multivibrator is a relaxation oscillator, working on the charging of a capacitor through a resistor. If a negative edge is applied to the circuit in (a), transistor TR 1 turns off the for time taken for the base voltage to return to 0 V. If the voltage step is
Read more

Adders:Carry Look-Ahead Adder.

By -
Image
Carry Look-Ahead Adder As previously stated, the carry, c i +1, produced at the i -th position is calculated as c i +1 = x i · y i ∨ c i ·( x i ⊕ y i ). This means that a carry is generated if both x i and y i are 1, or an incoming carry is propagated if one of x i and y i is 1 and the other is 0. Therefore, letting g i denote x i y i , we have c i +1 = g i ∨ c i p i , where p i = x i ⊕ y i . Here, g i is the formula for the carry generation condition at the i -th position, i.e., when g i is 1, a carry is generated at this position. Substituting g i –1 ∨ p i –1 c i –1 for c i , we get A carry look-ahead adder can be realized according to this expression, as illustrated in Figure 41.10 for the case of four bits [21]. According to this expression, c i +1’s are calculated at all positions in parallel. It is hard to realize an n -bit carry look-ahead adder precisely according to this expression, unless n is small, because maximum fan-in and fan-out restriction is violated at higher
Read more