# Delay Efficient 32-Bit Carry-Skip Adder

Authors: Yu Shen Lin; Damu Radhakrishnan
Journal: VLSI Design
 (2008)

---

## Abstract

The design of a 32-bit carry-skip adder to achieve minimum delay is presented in this paper.
A fast carry look-ahead logic using group generate and group propagate functions is used to speed up the performance of multiple stages of ripple carry adders.
The group generate and group propagate functions are generated in parallel with the carry generation for each block. The optimum block sizes are decided by considering the critical path into account.
The new architecture delivers the sum and carry outputs in lesser unit delays than existing carry-skip adders. The adder is implemented in 0.25μm CMOS technology at 3.3 V. The critical delay for the proposed adder is 3.4 nanoseconds. The simulation results show that the proposed adder is 18% faster than the current fastest carry-skip adder.


---

## Body

## 1. Introduction

The ever-increasing demand for mobile electronic devices requires the use of power-efficient VLSI circuits.  Computations in these devices need to be performed using low-power, area-efficient circuits operating at greater speed.  Addition is the most basic arithmetic
operation; and adder is the most fundamental arithmetic component of the processor.  Depending on the area, delay and power consumption requirements,   several adder implementations, such as ripple carry, carry-skip, carry look-ahead, and carry select, are available in the literature [1, 2]. The ripple-carry adder (RCA) is the simplest adder, but it has the longest delay because every
sum output needs to wait for the carry-in from the previous full-adder cell. It uses O(n) area and a delay of O(n) for an n-bit adder. The carry look-ahead adder has O(logn) delay and uses O(nlogn) area. On the other hand, the
carry-skip adder and carry-select adders have O(√n) delay and useO(n) area [3].In this paper,  we present the design of a low-power adder with less delay while using minimum hardware. The standard carry generate-propagate logic is used to reduce the critical delay of the adder while blocks of RCAs are used for lesser power consumption. In our design, the generate-propagate logic balances the delay and the number of inputs to the skip logic limits the critical path delay.  By applying our design procedure, we speed up the adder by 18% when compared to the current fastest 32-bit adder [4]. In Section 2, we will
discuss the previous work done in the area of high-performance adders. In
Section 3, we present the design of our adder. Section 4 presents the design of a few basic CMOS cells used in the adder. In Section 5, we present the simulation results for our adder and compare it to other fast adders.


## 2. Theoretical Background and Previous Work

The design of a carry-skip adder is based on the classical definition of generate and propagate signals as follows [1, 2]:
(1)pi=Xi⊕Yi,gi=Xi⋅Yi,
where pi is the propagate signal and gi is the generate signal, and Xi and Yi are the input operands to the ith adder cell. The carry out from the ith adder cell is expressed as
(2)Ci+1=gi+piCi,
where Ci is the carry input to the ith cell.Two signals, group generate and group propagate, are also
defined in [1, 2] and are given by
(3)Gj:i=gj+pjgj−1+pjpj−1gj−2+⋯+pjpj−1pj−2⋯pi+1gi,Pj:i=pjpj−1pj−2⋯pi,where Gj:i and Pj:i are group generate and group propagate signals
from ith cell to jth cell, respectively. Then, the expression for carry
out from the whole group is given by
(4)Cj+1=Gj:i+Pj:iCi.Different adder implementations have been developed to optimize various design parameters. Most adder implementations tend to trade off performance and area. One of the
earliest adder implementations of this kind was a regular parallel adder layout
also known as the Brent-Kung adder ’82 [5]. It is a variation of the basic carry   look-ahead  adder .  They emphasized the need for regularity in VLSI circuits to reduce design and implementation costs. They use two types of processor cells: white processor and black processor. The black processor performs the associative
concatenation defined in [5] and the white processor simply transmits the data. The adder delay was calculated in terms of the number of exclusive-or (XOR)
operations performed while treating each XOR delay as one unit time. For an n-bit adder, the Brent-Kung adder has a delay of O(logn) and uses O(nlogn) area.Wei-Thompson’85 [6] proposed
an area-time optimal adder design using three types of adder cells: black
cells, white cells, and driver cells. The black and white cells are quite
similar to the ones used in Brent-Kung adder. They divided the n-bit adder into ascending and descending halves so as to limit the number of bits in the final stage. The
concentration of the maximum number of bits was in the middle of the adder and
was defined as the height of the adder. The algorithm ends up in an unbalanced binary
tree with a delay of O(logn)  consuming an area O(nlogn).The ELM-adder design presented in [7] computes the sum bits in parallel; thereby reducing the number of interconnects. It implements an n-bit adder as a tree of processors to directly compute the sums in O(logn) time. The area used is O(nlogn). The adder design was expressed in terms of standard cells, which do not compute carry for each stage. Instead, partial sums were computed for each stage.Kantabutra’93 [8] presents the design of a one-level carry-skip adder using an approach that is very similar to that of Wei-Thompson. In contrary to Wei-Thompson’s approach, this design ends up in a symmetrical binary tree of adders. The
fan-in to the carry-skip logic increases linearly towards the middle of the
adder. A two-level carry-skip adder is presented in [9], where the whole adder stage is divided into a number of sections, each consisting of a number of RCA blocks of linearly increasing length. These adders reduce the delay at the cost of an increase in area and less regular layout.Nagendra’96 [3] did a survey of various adder designs and concluded that the ELM adder was superior in terms of area, power, delay, and power-delay product. RCA was concluded to have utilized the least power, but has the highest delay due to its carry chain. A variable-width carry-skip adder was shown to be superior to constant-width carry-skip adder, the advantage being greater at higher precisions.A fully static carry-skip adder designed by Chirca’04 [4] achieved lower-power dissipation and higher performance. To reduce delay and power consumption, the adder is divided into variable-sized blocks that balance the inputs to the carry chain. The main principle behind this design was to utilize the lower blocks and make them work in
parallel with higher blocks. This paper is a deviation from the tree approach presented in the ELM adder. A 32-bit adder implementation with a delay of 7 logic levels using carry-skip adders and ripple-carry adders was presented in [4]. This is shown in Figure 1. The logic-level delay defined in the paper is
equivalent to the delay of a complex CMOS gate. Efficient and-or-invert (AOI) and or-and-invert
(OAI) CMOS gates were used to reduce delay and power.Figure 1
The 32-bit adder divided
into 4 blocks [4].The 32-bit adder is divided into 4 adder blocks as shown in Figure1. Carry-select adders were used in the final CS4 block, which significantly increases the hardware. The paper claims that the output will be ready with a delay of 7 logic levels, with the assumption that the critical delay path is the carry propagation path of C32 bit. But a closer examination of the previous block CS18 reveals that the  27th bit of the sum output will be available only after a delay of 9 logic levels.


## 3. New Design for the 32-bit Carry-Skip Adder

The 32-bit carry-skip adder design presented in this paper uses a combination of RCAs together with carry-skip logic (SKIP), carry-generate logic (CG), and group generate-propagate
logic (PG).  The complete adder is divided into a number of variable-width
blocks. Both the carry generation and skip logic use AOI and OAI circuits. The width of each block is limited by the target delay T.Each block is further divided into subblocks. A subblock may contain
additional levels of subblocks in a recursive manner. The lowest-level subblock
is formed by a number of variable width RCAs. The adder structure is described as
follows:(5)Block→〈Block〉*〈Block〉|〈subblock〉|〈RCA〉,〈subblock〉→〈subblock〉*〈subblock〉|〈RCA〉.The 32-bit adder is divided into four blocks. A block diagram of the
first three blocks(A0,A1,andA2) is shown in Figure 2. The first block A0 (LSB) is a full adder by
itself. The carry from the first block C1 is fed into the second block A1 and is also fed into the skip logic. The generate and propagate functions (p,g) are generated separately for each full adder in one unit time, where one unit time is defined as the delay of a complex CMOS gate with at most three transistors connected in series from the output node to any supply rail. In Figure 2, the numbers shown in parenthesis represent the number of unit delays of the signal arrival times at the appropriate signal leads. Since the delay of
a complex CMOS gate is quadratic on its stack height, in our design, the stack
height is limited to 3. This implies that the maximum number of transistors (NMOS or PMOS) in any series connected path is 3. This also restricts the maximum number of inputs to the carry-skip logic to 7. On the other hand, when the generate-propagate outputs are used for group generation and group propagation (3)  outputs, a stack height of 3 in the CMOS
implementation will allow a 4-bit RCA.Figure 2
Block schematics for first three blocks of 32-bit adder.The carry-generation delay from the skip logic is minimized by alternately complementing the carry outputs. Hence, the carry signals generated areC1¯,C4,C14¯, and so forth. For the very first 1-bit block (A0), the carry-generation logic is more important than the sum-generation logic since the overall delay of the adder is
dependent on the carry from this block. Hence, this block is designed by
minimizing the carry out delay as much as possible. The simplest expression of
carry out from the LSB full adder is given by
(6)C1¯=X0Y0+X0C0+Y0C0¯,
where X0 and Y0 are the operand bits and C0 is the input carry. An AOI gate implements this.The blockA1 in Figure 2 is implemented as
a k-bit RCA. For any k-bit RCA, the total number of propagate and
generate (p,g) outputs would be 2 k. These 2 k outputs together with the carry
from the previous block are fed into carry-skip logic to generate the new carry
signal. The fan-in restriction of 7 to the carry-skip logic therefore limits
the number of bits in the RCA to 3. The carry out  C4 from skip logic for block A1 is given by
(7)C4=g3+p3g2+p3p2g1+p3p2p1C1.
Since g’s and p’s can be best implemented in
complementary form, we can rewrite  C4 as
(8)C4=g¯3(p¯3+g¯2)(p¯3+p¯2+g¯1)(p¯3+p¯2+p¯1+C¯1)¯.
By inspection, C4 can be implemented by an or-and-invert (OAI) gate and is available in 2 time units.
The final Sum output S3 from this 3-bit RCA will be available in 4 time units. The sum outputs for this RCA are generated either as Si=pi⊕Ci  or Si=p¯i⊕Ci¯¯   depending on the carry signal value (CiorCi¯). The carry out C2 and C3 are implemented as C2=g1¯⋅(p1¯+C1¯)¯ and C3=g2+p2C2, respectively.Now consider blockA2 in Figure 2. The delay of carry signal arriving at the input of the skip logic is 2 time units. This implies that the group generate-propagate (P,G) logic outputs feeding the skip logic must also be available in 2 time units. Hence, the inputs to the (P,G) logic must be available in 1 time unit. This implies that the inputs to the (P,G) logic must be the propagate and generate
signals of the full adders. Block A2 is divided into three subblocks A2,0,A2,1, and A2,2 (in this case, each subblock is an RCA). The
maximum width of each RCA is limited to 4 bits due to the fan-in restrictions imposed on the (P,G) block. The width of each RCA is also limited by the target
delay T of the 32-bit adder. The width W of the first RCA is given as
(9)W=T−D,
where D is the arrival delay of the carry output from the previous block. The width of all
remaining higher order RCAs in the same block will be 1 bit less because of the delayed arrival times of their carry input by an additional time unit. The carry inputs C8 and C11 to RCAs A2,1 and A2,2 are generated using AOI logic as follows:
(10)C8¯=G7:4+P7:4C4¯,(11)C11¯=G10:8+P10:8G7:4+P10:8P7:4C4¯.For a target delay of 6 time units, the width of the first RCA inA2(A2,0) is 4 bits and the widths of the remaining RCAs (A2,1andA2,2) are each 3 bits. The number of RCAs in A2 is limited to 3 due to the
fan-in restriction of 7 on the skip logic. Each RCA in block A2 also represents a subblock of A2. The carry out C14 from the skip logic is implemented using AOI logic as
(12)C14¯=G13:11+P13:11⋅G10:8+P13:11⋅P10:8⋅G7:4+P13:11⋅P10:8⋅P7:4⋅C4¯.A detailed block diagram of the first three blocks of the 32-bit adder (an expanded view of Figure2) is shown in Figure 3. The three blocks together form a 14-bit adder.Figure 3
Detailed view of the first three blocks of 32-bit adder.Next let us consider the final blockA3 of the 32-bit adder. Block A3 is divided into a number of subblocks. The maximum number of subblocks is again limited to 3 due to the fan-in restrictions on the skip logic. A block diagram of A3 with an expanded view of subblock 0(A3,0) is shown in Figure 4. The subblock 0 is further divided into RCAs. The number of inputs to the CG logic increases, successively, by 2 for each RCA and is limited to a maximum of 7 in any subblock. Hence, the number of RCAs in any subblock is limited either by the number of inputs to the CG block or by the number of inputs to the (P,G) block. Therefore, subblock 0 can accommodate 4 RCAs. The carry input to the skip logic, as well as, to the first RCA (A3,0,0) arrives in 3 time units. The propagate and generate signals (p and g) from each RCA will be available with a delay of 1 time unit. This implies that we can have two levels of (P,G) logic inside the block while satisfying the time delay constraints. Using (9), the width of the first RCA (A3,0,0) is 3 bits, and the widths of the remaining RCAs are 2 bits each. Hence, the total width of subblock 0(A3,0) is 9 bits.Figure 4
Block-3 of 32-bit adder with
an expanded view of sub-block 0.Figure5 shows block A3 with an expanded view of
subblock 1(A3,1).   The number of RCAs in A3,1 is limited to 3 due to the condition stated earlier. The carry input C23 to the first RCA (A3,1,0) of this subblock is given by
(13)C23=G22:14¯(P22:14¯+C14¯)¯.Figure 5
Block-3 of 32-bit
adder with an expanded view of sub-block 1.With an AOI logic implementation,C23 will be available in 4 time
units, thereby limiting the length of the first RCA to 2 bits. The carry inputs C25 and C27 to the remaining RCAs in subblock 1(A3,1)
are also available in 4 time units. Thus, the maximum width of
subblock A3,1 is 6 bits. The carry input C29 to the final subblock 2(A3,2) is given by
(14)C29=G28:23¯(P28:23¯+G22:14¯)(P28:23¯+P22:14¯+C14¯)¯.The maximum width of subblockA3,2 can be calculated as 4 bits. This subblock can accommodate only 2 RCAs due to the fan-in limits of the CG blocks. Hence, the total width of block A3 is 19 bits. By combining the 4 blocks A0,A1,A2, and A3 a 33-bit adder can be implemented. The width of subblock A3,2 can be shortened to 3-bits for a 32-bit adder. The carry out C32 from the skip logic is given by
(15)C32=G31:29(α)(β)(γ)¯,
where, (α)=(P31:29¯+G28:23¯),(β)=(P31:29¯+P28:23¯+G22:14¯),(γ)=(P31:29¯+P28:23¯+P22:14¯+C14¯).An OAI logic implementation generatesC32 in 4 time units. A
detailed block diagram of block A3 is shown in Figure 6. The final breakdown of the 32-bit adder into 4 blocks is shown in Figure
7. A reduction in hardware can be achieved by moving subblock A3,2 from block A3 and placing it as another block A4. This will eliminate 1 carry generate logic (OAI) and 1(P,G) logic.Figure 6
Detailed
scheme for blockA3.Figure 7
The proposed 32-bit
adder.Although our adder has already achieved the 32-bit requirement, we still have room to extend the width further, while keeping the target delay the same. The schemes for the5th and 6th blocks are shown in Figure 8. The fifth block A4 is divided into three subblocks. The subblocks (A4,0,A4,1,andA4,2) have the same structure as block A3. Since the carry fed into the 5th block has 4 unit delays, the maximum width of the first RCA will be 2 bits. The
remaining RCAs will be 1 bit each. Thus, the maximum width for the fifth block
will be 20 bits. The first subblock A4,0 (11 bits) is divided into subblocks of 5, 3, 2, and 1 bit. The subblock A4,1 (6 bits) is divided into 3 subblocks of 3, 2, and 1 bit. Similarly, the final subblock A4,2 (3 bits) is divided into subblocks of
2 and 1 bit. The first 5-bit subblock (A4,0,0) consists of a 2-bit RCA and
3 individual full adders. Individual full adder cells form all other subblocks.
The 6th block A5 is a single bit full adder. Thus, the total width
of the adder becomes 54.Figure 8
The schemes for the fifth and sixth
blocks.Based on the adder design procedure, we can derive a
formula for calculating the maximum number of full adders in every block. The
following notations are used in the derivation.T Target delay of the n-bit adder in time units, N(i) The number of RCAs
in block i, W(i,j) The width of RCA “j” in block i.For any blocki(i≥2), the number of RCAs is defined by
a recursive function N(i). The recursive function is not valid for the blocks A0 and A1, and the values for N(0) and N(1) when used in the recursive function are assumed to be zero
(16)N(i)=∑1ii+N(i−1),N(0)=N(1)=0.
The width of an RCA is defined in terms of the target delay. The width W(i,j) of the RCA“j” in any block“i” is defined as
(17)W(i,j)={min(4,T−i),forj=0,min(4,T−i−1),for1≤j≤N(i)−1,
where min (a,b) is the minimum value among a and b.The carry input to the first RCA of the block can be obtained directly from
the previous carry-skip stage. Hence, the calculation of width for the first block is done differently from the others.The maximum number of full addersFA(i) in block i is given by
(18)FA(i)=∑j=0N(i)−1W(i,j)=∑j=1N(i)−1W(i,j)+W(i,0).Table1 lists the maximum adder size for a given
target delay using our design procedure.Table 1
Maximum size of adders.
Target delay (T)-time
units45678Adder size (n)-bits92254119237


## 4. Design of Basic CMOS Cells

A few basic CMOS cells are used for the design of the adder stage. They
are: AOI, OAI, and FA cells. Three different cells are used for AOI and OAI
(3-input, 5-input, and 7-input). These cells are labeled as AOIn and OAIn,
where n refers to the number of inputs to the cell. The 3-input and 5-input
cells are implemented in a straightforward manner, and are given by the
following Boolean expressions:(19)AOI3:Out=A+B⋅C¯,
where A,B, and C are the inputs for the gate. The 3-input OAI is expressed as
(20)OAI3:Out=A⋅(B+C)¯.
The expressions for 5-input AOI and OAI are given as
(21)AOI5:Out=A+B⋅(C+D⋅E)¯,OAI5:Out=A⋅(B+C⋅(D+E))¯,
where A,B,C,D, and E are the inputs to the cells. When the 7-input AOI and OAI cells are implemented in the above manner, the delay is prohibitive and hence we decided to implement them  as a cascade connection of a number of smaller modules. Their corresponding Boolean expressions are given by
(22)AOI7:Out=A+B⋅C+B⋅D¯+(E+F⋅G)¯¯¯,OAI7:Out=A⋅(B+C)⋅[(B+D)¯⋅(E⋅(F+G)¯]¯¯,
where A,B,C,D,E,F and G are the inputs to the cells. Since we reduce the stack height of
the transistors connected in series from 4 to 3, the 7-input AOI and OAI cells will be speeded up and the propagation delay will be almost the same as the 5-input AOI and OAI. The full adder cell used in our design is the low-energy CMOS adder cell presented in [10].


## 5. Simulation

The adder was implemented using Tanner tools pro 11.03. L-edit was used
to generate the layout and T-spice was used for performing the simulation. The
generic 0.25μm CMOS technology was used with 3.3 volts supply voltage. The
different CMOS cells (AOI, OAI, and FA) were simulated for worst-case delays
and the delays are tabulated in Table 2.   From Table 2, it may be noted that the 5 and 7-input cell delays are comparable to that of the FA, while the 3-input cells have a much
less delay. The average power was measured by feeding 10,000 random vectors at
a frequency of 500 MHz and is also shown in Table 2.Table 2
Cell Characteristics.
Delay (ns)Average power (mw)AOI30.2670.128OAI30.2640.127AOI50.5270.15OAI50.5410.16AOI70.5780.33OAI70.5790.30FA0.6040.34For comparison purposes, we selected two other types of adders. They are
(i) 32-bit carry skip-adder proposed in [4] and (ii) 32-bit multilevel carry-skip
adder proposed in [11]. The first one is referred here as Chirca adder and the second one is referred as Gayles adder. These adders were compared with our
32-bit adder by measuring the critical path delays. To get a more realistic
estimation of the delays involved, we laid out the complete 32-bit adder stages
and performed TSPICE simulation. The simulation was carried out at a frequency
of 100 MHz. The simulation results are shown in Table 3. These results show that our 32-bit adder has the minimum delay of 3.4 nanoseconds while Gayles adder
exhibited a maximum delay of 4.39 nanoseconds. The Chirca adder had a delay of 4.15 nanoseconds.
Thus, our design has a speedup of 18% and 22% compared to those of Chirca and
Gayles adders, respectively. Our 32-bit adder was then extended to a 54-bit
adder with marginal delay increase, and these simulation results are also
included in Table 3. Even this 54-bit adder is found to be faster than the 32-bit Gayles adder.Table 3
Adder comparison for delay, power, and power-delay product.
Delay (ns)Power (mw)PDP (pJ)32-bit adder
(Chirca)4.154.6819.432-bit adder
(Gayles)4.393.2614.3Our adder (32-bit)3.44.214.28Our adder (54-bit)4.38.636.98The power consumption showed a marginal increase of power for our adder compared to
Gayles adder while outperforming Chirca adder. Overall, our 32-bit adder
achieved the lowest power-delay product.


## 6. Conclusions

In this paper, we presented a new
32-bit adder using carry-skip logic. The adder was implemented by dividing the
adder into several blocks. The size of each block is limited by the delay of the
carry-in signal and the final target delay. An algorithm is used to calculate
the maximum size of the adder satisfying the target delay. The delay of a full
adder is used as the unit of measurement in our analysis. The adder has been
implemented by generating the layout with Generic 0.25μm CMOS technology. The
TSPICE simulations carried out at a frequency of 100 MHz and supply voltage of
3.3 V showed a critical path delay of 3.4 nanoseconds. The comparison results show that
our adder is faster than Chirca and Gayles carry-skip adders. Overall our proposed
adder is 18% and 22% faster compared to the Chirca and Gayles adders,
respectively. Furthermore, a 54-bit adder implemented using our approach can
operate almost at the same speed as a 32-bit Chirca adder or Gayles adder. Even
though our adder has a marginal increase in power consumption compared to the
Gayles adder, overall, we achieved the lowest power-delay product.



---

*Source: 218565-2008-04-02.xml*