18-01-2013, 02:40 PM
A Carry Skip Adder with Logic Level Optimization
A Carry Skip Adder.pdf (Size: 180.37 KB / Downloads: 223)
Abstract
Addition is the most commonly used arithmetic operation that it often is the speedlimiting
element. Therefore, careful optimization of the adder is of the utmost
importance. This optimization can be done either in the logic or circuit level way.
Circuit optimizations manipulate transistor sizes and circuit topology to optimize the
speed. On the other hand, logic-level optimization tries to rearrange the Boolean
equations so that a faster or smaller even less power consumption circuit is obtained.
We here take the Carry Skip Adder for our example and provide a short summary of the
basic definition of the adder circuit as well as consider optimization processes,
especially high performance.
Introduction
Several adder implementations, including ripple carry, Manchester carry chain, carry
skip, carry look-ahead, carry select, conditional sum, and various parallel prefix adders
are available to satisfy different area, delay, and power requirements. With many studies,
ripple carry and Manchester carry chain adders are the simplest, but slowest adders with
O(n) area and O(n) delay, where n is the operand size in bits. Carry look-ahead,
conditional sum, and parallel prefix adders have O(n·log(n)) area and O(log(n)) delay,
but typically suffer from irregular layout. On the other hand, carry skip adder, which has
O(n) area and O(√n) delay provides a good compromise in terms of area and delay,
along with a simple and regular layout. Carry skip adders also dissipate less power than
other adders due to their low transistor counts and short wire lengths.
CarrySkip Adder
A ripple-carry adder, as mentioned above, is the simplest so that it is easy to design
but is only practical for the implementation of additions with a relatively small word
length because the linear dependence of the adder speed on the number of bits makes
the usage of the ripple-carry adder rather impractical; since the carry bit “ripple” from
one stage to the other, the delay through the circuit depends on the number of logic
stages that must be traversed and is a function of the applied input signals.
As in a ripple-carry adder, every full adder cell has to wait for the incoming carry
before an outgoing carry can be generated. This dependency can be eliminated by
introducing an additional bypass (skip) to speed up the operation of the adder. An
incoming carry Ci,0=1 propagates through complete adder chain and causes an outgoing
carry C0,3=1 under the conditions that all propagation signals are 1. This information can
be used to speed up the operation of the adder, as shown Fig 2. When BP = P0P1P3P4 = 1,
the incoming carry is forwarded immediately to the next block through the bypass and if
it is not the case, the carry is obtained via the normal route.
Variable Block-Sizes Carry skip adder
Although the carry-skip adder works faster than a ripple carry adder, upon closer
inspection, we notice that if all the skip blocks are of the same size, the latter blocks will
finish switching quickly and then sit idle for a while waiting for the carry signal to pass
through all the bypass multiplexors. For example, in the diagram of a 32-bit carry-skip
adder below, bits the carry-out for bits 4-7 will be ready at the same time as the carryout
for bits 0-3. This second block will wait while the first multiplexor does its job.
Therefore, logic optimization is crucial.
The optimization for the carry skip adder can be done by varying bypass group sizes.
In other word, to speed up the circuit, we could vary the size of the skip block.
Intuitively, we should then be able to reduce the size of the first skip block and make
each subsequent block increasingly larger. Because the critical path includes the last
skip block, we must also start to taper down the size of each block as we approach the
end.
Conclusion
Generally, Carry skip adder is a fast adder compared to ripple carry adder when
addition a large number of bits; carry skip adder has O(√n) delay provides a good
compromise in terms of delay, along with a simple and regular layout. But it has still
some drawbacks; it is still linear fashion although it is significantly improved in
performance (the ripple adder is actually faster for small values of N) and the overhead
of the extra bypass multiplexer makes the carry skip adder less interesting.
For better performance, several studies have also been performed to reduce the
delay of carry-skip adders. 1) Techniques select variable block sizes to minimize the
delay of adders that use a single level of carry skip logic. 2) Techniques allow multiple
levels of skip logic, which further reduces delay at the cost of an increase in area and
less regular layout.