Datapath Design

Presented by
Dr. Md. Abir Hossain
Professor
Dept. of ICT
MBSTU
 Fixed-Point Arithmetic

➢ Addition
➢ Subtraction
➢ Multiplication
➢ Division
 Basic Adders

➢Half Adder: Read Yourself

➢Full Adder: Read Yourself

➢Serial Binary Adder: Read Yourself

 Basic Adders

1-bit Full addrer symbol

1-bit Full adder

Ripple Carry Adder/n-bit parallel adder/n-
bit adder

Normally
Cin=0

➢ Formed by connecting n number of 1-bit full adders

➢ Each 1-bit adder stage supplies a carry bit to the stage on its left.
➢ A 1 appearing on the carry in line of a 1-bit adder cause it to
generate a 1 on its carry out line. So, the carry signal propagate
through the adder from right to left.
➢ The maximum signal propagation delay is nd, where d is the delay
of a full-adder stage.
➢ The amount of hardware in ripple carry adder increases linearly with
n.
2’s Complement Adder-Subtracter
 Overflow
➢ When the result of an arithmetic operation exceeds the standard word
size n, overflow occurs.
➢ Example: let n=8 X=11101011=23510 and Y=00101010=4210
Z = X+Y = 11101011 + 0101010 = 00010101 = 2110
with output carry bit Cn-1 = C7 = 1.
actual result of the summation, C7Z = 100010101 = 27710 = 25610 + 2110
➢ The result of an addition simply wraps around when the largest number
2n-1 is exceeds.
➢ For n, the number range for unsigned number is 0 to 2n-1
➢ Overflow is indicated by a flag bit v in operations involving signed
numbers
 Overflow
➢ We can never have overflow on adding a negative and positive
number.

➢ Example: let n=8 X=11101011=-2110 and Y=00101010=+4210

Z = X+Y = 00010101 = 2110 and C7 = 1.
So, Cn-1 = 1 does not indicate overflow.

➢ Overflow in 2’s complement addition can result from adding

1) two positive numbers or
2) two negative numbers.
 Overflow
Case 1: Two numbers are positive.

Let n = 4, 7 + 3 = 0111+0011 = 1010 so, cn-1 = 1

Cn-1 =1 indicates that the magnitude of the sum exceeds the n-1 bits
allocated to it.

Case 2: Two numbers are negative.

Let n=4, -7 = 1001, -3 = 1101

so, 1001+1101 = 10110 so, cn-1 = 0
Cn-1 =0 indicates the overflow.
 Carry-Lookahead Adder
➢ It reduce the time required to form carry signals.

➢ It computes the input carry needed by stage i directly from

carrylike signals obtained from all the preceding stages i-1,
i-2, ….., 0, rather than waiting for normal carries to ripple
slowly from stage to stage.

➢ Adders that use this principle are called carry-lookahead

adders.
 Carry-Lookahead Adder
➢ An n -bit carry-lookahead adder is formed from n stages, each of which
is basically a full adder modified by replacing its carry output line c, by
two auxiliary signals called gi and pi , or generate and propagate, where
➢ Two signals:
generate signal, gi = xiyi
propagate signal, pi = xi + yi
 4-bit Carry-Lookahead Adder

➢ci = xiyi + xici-1 + yici-1

➢ci = gi + pici-1 Though gi = xiyi
➢ci-1 = gi-1 + pi-1ci-2
➢ci = gi + pigi-1 + pipi-1ci-2

ci = gi + pigi-1 + pipi-1ci-2
➢ c0 = g0 + p0cin
c1 = g1 + p1g0 + p1p0cin
c2 = g2 + p2g1 + p2p1g0 + p2p1p0cin
c3 = g3 + p3g2 + p3p2g1 + p3p2p1g0 + p3p2p1p0cin

➢ zi = xi  yi  ci-1 can be written as zi = pi  gi  ci-1

4-bit Carry-Lookahead Adder
 4-bit Carry-Lookahead Adder
➢ It limits n to 4.

➢ Maximum delay is 4d, where d is the average gate delay. It

is independent of number of input n.

➢ The number of gates grows in proportion to n2 as n

increases.

➢ The number of gates in a two level adder of the sum-of-

product type grows exponentially with n, while the number
of gates in a ripple- carry adder grows linearly with n.
 Adder Expansion
➢ If we replace n 1-bit adder stages in the n-bit ripple carry adder
with n k-bit adders, we obtain an nk-bit adder.

16-bit adder composed of 4-bit adders linked by ripple-carry propagation

 Adder Expansion
➢ If we replace n 1-bit adder stages in the n-bit carry look-ahead adder
with n k-bit adders, we obtain an nk-bit adder.

16-bit adder composed of 4-bit adders linked by carry look-ahead

 Multiplication

Multiplicand Y ➢ If multiplicand = n bits and

multiplier = m bits then
Multiplier X = x3x2x1x0
product = n + m bits.

➢ Two rules:
▪ Place a copy of multiplicand
in the proper place if
multiplier bit=1.
Product P = Sum(xj 2j Y)
j=0 to 3
▪ Place 0 in the proper place if
multiplier bit = 0.
Pi+1 := Pi + xj2iY

Add Y for X times

Two`s Complement Multipliers
Two`s Complement Multipliers
Two`s Complement Multipliers
Robertson`s Multiplication Process
 Booth’s Multiplication Algorithm
➢ It employs both addition and subtraction.
➢ It treats positive and negative operands uniformly.
➢ No special actions are required for negative numbers.
➢ It provides faster execution.
➢ Two adjacent bits xixi-1 are examined in each step. If xixi-1
=01, then Y is added to the current partial product Pi.
While if xixi-1 =10, then Y is subtracted from Pi. If xixi-1
=00 or 11, then neither addition or subtraction is
performed.
➢ It reduces the average number of add-subtract steps and
allows faster multipliers to be designed.
➢ It involves more complex circuitry.
Booth`s Multiplication Process
Combinational ALU
Sequential ALU
 Floating point Arithmetic
➢ Floating-point arithmetic can be implemented by two loosely
connected fixed-point datapath circuits, an exponent unit and
a mantissa unit.
➢ The mantissa unit performs all four basic operations on the
mantissas;
➢ A simpler circuit capable of only adding, subtracting, and
comparing exponents suffices for the exponent unit.
➢ Exponent comparison can be done by a comparator or by
subtracting the exponents.
➢ The exponents of the input operands are put in registers El
and E2, which are connected to an adder that computes El +
E2.
➢ The exponent comparison required for addition and
subtraction is made by computing El - E2 and placing it in a
counter register E.
➢ The larger exponent is then determined from the sign of E.
Floating point Arithmetic
 Co-processor

➢ Complicated arithmetic operations like exponentiation and trigonometric functions

are costly to implement in CPU hardware and make the overall operation slow.
➢ Due to this, use an auxiliary processors called arithmetic coprocessors to provide
fast, low-cost hardware implementations of these special functions called
coprocessor.
➢ A coprocessor is a separate instruction-set processor that is closely coupled to
the CPU and whose instructions and registers are direct extensions of the CPU's.
 Co-processor
➢ Instructions intended for the coprocessor are fetched by the CPU, jointly decoded
by the CPU and the coprocessor, and executed by the coprocessor.
➢ The coprocessor is attached to the CPU by several control lines that allow the
activities of the two processors to be coordinated.
➢ To the CPU, the coprocessor is a passive or slave device whose registers can be
read and written into in much the same manner as external memory.
➢ Communication between the CPU and coprocessor to initiate and terminate
execution of coprocessor instructions occurs automatically.
➢ If no coprocessor is actually present, coprocessor instructions can be included in
CPU programs, because if the CPU knows that no coprocessor is present, it can
transfer program control to a predetermined memory location where a software
routine implementing the desired coprocessor instruction is stored.