Digital System Design
Lecture 15
Parallel Adders
Parallel Adders
Adders
Addition is a fundamental operation for any digital system,
digital signal processing or control system. A fast and
accurate operation of a digital system is greatly influenced by
the performance of the resident adders.
Adders are also very important component in digital systems
because of their extensive use in other basic digital
operations such as subtraction, multiplication and division.
Hence, improving performance of the digital adder would
greatly advance the execution of binary operations inside a
circuit compromised of such blocks.
Parallel Adders
Basic Adder Unit
The most basic arithmetic operation is the addition of two
binary digits, i.e. bits.
Half Adder
A combinational circuit that adds two bits, according the scheme
outlined below, is called a half adder.
Full Adder
A full adder is one that adds three bits, the third produced from a
previous addition operation. One way of implementing a full
adder is to utilizes two half adders in its implementation.
Parallel Adders
Half Adder
Parallel Adders
Parallel Adders
Full Adder
Parallel Adders
Ripple Carry Adder
The ripple carry adder is constructed by cascading full adders
(FA) blocks in series. One full adder is responsible for the
addition of two binary digits at any stage of the ripple carry.
The carryout of one stage is fed directly to the carry-in of the
next stage.
A number of full adders may be added to the ripple carry
adder or ripple carry adders of different sizes may be
cascaded in order to accommodate binary vector strings of
larger sizes. For an n-bit parallel adder, it requires n
computational elements (FA).
8
Parallel Adders
Parallel Adders
Ripple Carry Adder
One of the most serious drawbacks of this adder is that the
delay increases linearly with the bit length. As mentioned
before, each full adder has to wait for the carry out of the
previous stage to output steady-state result. Therefore even if
the adder has a value at its output terminal, it has to wait for
the propagation of the carry before the output reaches a
correct value.
10
Parallel Adders
11
Parallel Adders
12
Parallel Adders
13
Parallel Adders
14
Parallel Adders
15
Parallel Adders
Carry Lookahead Adder
The size and fan-in of the gates needed to implement the
Carry-Look-ahead adder is usually limited to four . The CLA
has the fastest growing area and power requirements with
respect to the bit size. Speed also will drop with increase in
bit size. So other techniques may be used.
16
Parallel Adders
Carry-Skip Adder
A carry-skip adder consists of a simple ripple carry-adder
with a special speed up carry chain called a skip chain. This
chain defines the distribution of ripple carry blocks, which
compose the skip adder.
Carry Skip Mechanics
The addition of two binary digits at stage i, where i 0, of the
ripple carry adder depends on the carry in, Ci , which in reality
is the carry out, Ci-1, of the previous stage. Therefore, in order
to calculate the sum and the carry out, Ci+1 , of stage i, it is
imperative that the carry in, Ci, be known in advance. It is
interesting to note that in some cases Ci+1 can be calculated
without knowledge of Ci.
17
Parallel Adders
Carry-Skip Adder
Supposing that Ai = Bi, then Pi in equation 1 would become zero
(equation 4). This would make Ci+1 to depend only on the inputs Ai
and Bi, without needing to know the value of Ci.
Therefore, if Equation 4 is true then the carry out, Ci+1, will be one if
Ai = Bi = 1 or zero if Ai = Bi = 0. Hence we can compute the carry
out at any stage of the addition provided equation 4 holds.
18
Parallel Adders
Carry-Skip Adder
Alternatively, given two binary strings of numbers, such as the
example below, it is very likely that we may encounter large chains
of consecutive bits (block 2) where AiBi. In order to deal with
this scenario we must reanalyze equation 3 carefully.
In the case of comparing two bits of opposite value, the carry out
at that particular stage, will simply be equivalent to the carry in.
Hence we can simply propagate the carry to the next stage
without having to wait for the sum to be calculated
19
Parallel Adders
20
Parallel Adders
Carry-Skip Adder
Two strings of binary numbers to be added are divided into blocks
of equal length. In each cell within a block both bits are compared
for un-equivalence. This is done by Exclusive ORing each
individual cell (parallel operation and already present in the full
adder) producing a comparison string. Next the comparison string
is ANDed within itself in a domino fashion. This process ensures
that the comparison of each and all cells was indeed unequal and
we can therefore proceed to propagate the carry to the next
block.
A MUX is responsible for selecting a generated carry or a
propagated (previous) carry with its selection line being the
output of the comparison circuit just described. If for each cell in
the block Ai Bi then we say that a carry can skip over the block
otherwise if Ai = Bi we shall say that the carry must be generated
in the block
21
Parallel Adders
Carry-Select Adder
In carry-select adders both sum and carry bits are calculated
for the two alternatives: input carry 0 and 1. Once the
carry-in is delivered, the correct computation is chosen
(using a MUX) to produce the desired output. Therefore
instead of waiting for the carry-in to calculate the sum, the
sum is correctly output as soon as the carry-in gets there.
In order to enhance its speed performance, the carry-select
adder increases its area requirements.
22
Parallel Adders
23
Parallel Adders
Carry-Select Adder
Carry-select adders can be divided into equal or unequal
sections. For each section, the calculation of two sums is
accomplished using two 4-bit ripple-carry adders. One of
these adders is fed with a 0 as carry-in whereas the other is
fed a 1. Then using a multiplexer, depending on the real
carryout of the previous section, the correct sum is chosen.
Similarly, the carryout of the section is computed twice and
chosen depending of the carryout of the previous section.
24
Parallel Adders
Carry-Select Adder
One section of a larger Carry Select Adder
25
Parallel Adders
Carry Save Adder
In many cases we need to add several operands together, carry save
adders are ideal for this type of addition.
A carry save adder consists of a ladder of stand alone full adders,
and carries out a number of partial additions. Doing additions with
Carry save adder saves time and logic.
26
Parallel Adders
What type of adder is to be used?
Experiments
To be able to compare these adders experiments were conducted
by 2 students ( Jonathan Rajotte and Jessee Rodrigez). They
Synthesized various 16-bit adders. The results obtained from
Xilinx mapping concerning area requirements, operating speed
and power consumption are illustrated in Table 3
Design downloads onto the FPGA boards, using Synopsis, was
performed in accordance with the Xilinx xio_4000e-3 and
xprim_4000e-3 libraries.
27
Parallel Adders
What type of adder is to be used?
Comparing the performance metrics for the 16-bit adders
implemented on Xilinx FPGA board, using Synopsys
synthesis tools, the trade offs become apparent. The ripple
carry adder, the most basic of flavors, is at the one extreme
of this spectrum with the least amount of CLBs but the
highest delay. The carry select adder on the other hand, is at
the opposite corner since it has the lowest delay (half that of
the ripple carrys) but with a larger area required to
compensate for this time gain. Finally, the carry look-ahead is
middle ground. Power dissipation, for this case study, is in
direct proportion to the number of CLBs
28
Parallel Adders
Read :
Section 5.5, 5.6 Digital Design of Signal Processing Systems
by Shoab Ahmed khan
29
Parallel Adders
Best way to learn DSD is to do it!
30
Parallel Adders