written 5.7 years ago by |
A carry-skip adder (also known as a carry-bypass adder) is an adder implementation that improves on the delay of a ripple-carry adder with little effort compared to other adders. The improvement of the worst-case delay is achieved by using several carry-skip adders to form a block-carry-skip adder.
The worst case for a simple one level carry-ripple-adder occurs, when the propagate-condition is true for each digit pair $(a_{i},b_{i})$. Then the carry-in ripples through the n-bit adder and appears as the carry-out after $ \tau_{CRA}(n) = n. \tau _{VA}$.
For each operand input bit pair $(a_{i},b_{i})$ the propagate-conditions $ p_{i}=a_{i}\oplus b_{i}$ are determined using an XOR-Gate. When all propagate-conditions are true, then the carry-in bit $c_{0}$ determines the carry-out bit.
The n-bit-carry-skip adder consists of a n-bit-carry-ripple-chain, a n-input AND-gate and one multiplexer. Each propagate bit $p_{i}$, that is provided by the carry-ripple-chain is connected to the n-input AND-gate. The resulting bit is used as the select bit of a multiplexer that switches either the last carry-bit $c_{n}$ or the carry-in $c_{0}$ to the carry-out signal $c_{{out}}$.
This greatly reduces the latency of the adder through its critical path, since the carry bit for each block can now "skip" over blocks with a group propagate signal set to logic 1 (as opposed to a long ripple-carry chain, which would require the carry to ripple through each bit in the adder). The number of inputs of the AND-gate is equal to the width of the adder. For a large width, this becomes impractical and leads to additional delays, because the AND-gate has to be built as a tree. A good width is achieved, when the sum-logic has the same depth like the n-input AND-gate and the multiplexer.
The critical path of a carry-skip-adder begins at the first full-adder, passes through all adders and ends at the sum-bit $ s_{{n-1}}$. Carry-skip-adders are chained to reduce the overall critical path, since a single n-bit carry-skip-adder has no real speed benefit compared to a n-bit carry-ripple-adder.
$\tau_{CSA}(n) = \tau_{CRA}(n)$
The skip-logic consists of a m-input AND-gate and one multiplexer.
$ T_{{SK}}=T_{{AND}}(m)+T_{{MUX}} $
As the propagate signals are computed in parallel and are early available, the critical path for the skip logic in a carry-skip adder consists only of the delay imposed by the multiplexer (conditional skip).
$T_{{CSK}}=T_{{MUX}}=2D.$