PRESIDENCY UNIVERISTY, BENGALURU, School of Engineering

Computer Organization and Architecture

CSE 2009

Module-3: Arithmetic Unit

Saturday, February 15, 1

2025
 Introduction
• A basic operation in all digital computers is the addition or
subtraction of two numbers.
• In this chapter we discuss about the logic circuits used to
implement arithmetic operations.
• The time needed to perform an addition operation affects
the processor’s performance.
• Multiply and divide operations, which require more
complex circuitry than either addition or subtraction
operations, also affect the performance.
• In this chapter we discuss about some of the techniques
used in modern computers to perform arithmetic
operations at high speed.
• Compared with arithmetic operations, logic operations are
simple to implement using combinational circuits.

2
 Addition And Subtraction Of Two
Numbers
 Consider the addition of two numbers X and Y with n-bits
each.
 Figure shows the logic truth table for adding equally weighted
bits Xi and Yi in two numbers X And Y.
 The figure also shows the logic expressions for these
functions, along with an example of addition of 4-bit unsigned
numbers 7 and 6.
 The logic expression for sum (Si) and the carry out function
(Ci+1) are shown in the figure.

3
4
 Adder
FULL ADDER:
 The circuit which performs the addition of three bits is a Full
Adder.
 It consists of three inputs and two outputs.
INPUTS:
Xi, yi and ci are the three inputs of full adder.
OUTPUTS:
Si and Ci+1 are the two outputs of full adder.
 Block diagram of full adder is shown in the figure.
 A cascaded connection of n full adder blocks can be used to
add two n-bit numbers. Since the carries must propagate or
ripple through this cascade, the configuration is called an n-bit
ripple-carry adder.
 A cascaded connection of K n-bit adders can be used to add k
n-bit numbers.

5
6
7
 Computing the add time (contd..)

x0 y0
Consider 0th stage:
• c1 is available after 2 gate delays.
• s0 is available after 1 gate delay.
c1 FA c0

s0

Sum Carry
yi
c
i
xi
xi
yi si c
c i +1
i
ci
x
i
yi

8
 Computing the add time (contd..)

Cascade of 4 Full Adders, or a 4-bit adder

x0 y0 x0 y0 x0 y0 x0 y0

FA FA FA FA c0
c4 c3 c2 c1

s3 s2 s1 s0

• s0 available after 1 gate delays, c1 available after 2 gate delays.

• s1 available after 3 gate delays, c2 available after 4 gate delays.
• s2 available after 5 gate delays, c3 available after 6 gate delays.
• s3 available after 7 gate delays, c4 available after 8 gate delays.
For an n-bit adder, sn-1 is available after 2n-1 gate delays
cn is available after 2n gate delays.
9
Fast addition (Carry-look Ahead Addition)
Recall the equations:
si  xi  yi  ci
ci 1  xi yi  xi ci  yi ci

Second equation can be written as:

ci 1  xi yi  ( xi  yi )ci

We can write:
ci 1 Gi  Pi ci
where Gi  xi yi and Pi  xi  yi

• Gi is called Generate function and Pi is called Propagate function

• Gi and Pi are computed only from xi and yi and not ci, thus they can
be computed in one gate delay after X and Y are applied to the
inputs of an n-bit adder.
1
0
• The expressions Gi and Pi are called the generate and
propagate functions for stage i.
• Each bit stage contains an
1) AND gate to form Gi,
2) OR gate to form Pi, and
3) three-input XOR gate to form Si.
• A simpler circuit can be designed to generate Gi, Si and Pi

But in this case Gi=1, so it does not matter whether Pi is 0 or 1.

Then using a cascade of two input XOR gates to realize the 3-
input XOR function. the basic cell B can be used in each bit
stage as shown in the figure.

1
1
1
2
i=0
ci 1 Gi  Pi ci
C1=
3GD
i=1

C2=
3GD

1
3
i=2

C3=
3GD

1
4
i=3

C4=
3GD

1
5
 • For example the carries in a four stage carry-look
ahead adder is given as follows.

C1= G0+P0C0

C2=G1+P1C1
= G1+ P1(G0+P0C0)
= G1+P1G0+P1P0C0

C3= G2+P2C2
= G2+P2(G1+P1G0+P1P0C0)
= G2+P2G1+P2P1G0+P2P1P0C0

1
6
 C4= G3+P3C3
= G3+P3(G2+P2G1+P2P1G0+P2P1P0C0)
= G3+P3G2+P3P2G1+P3P2P1G0+P3P2P1P0C0

1
7
 Pi and Gi:
All Pi and Gi are available after one gate delay.

Ci+1:
All carries are available after three gate delays.

Sum:
After a further XOR gate delay, all sum bits are
available. So after four gate delays all sums are
available.

1
8
• An adder implemented in this form is called a carry-
look ahead adder.
• Delay through the adder is 3 gate delays for all carry
bits and 4 gate delays for all sum bits.
• In comparison 4-bit ripple carry adder requires 7
gate delays for all sums and 8 gate delays for all
carries.

1
9
MULTIPLICATION
1. Signed-operand Multiplication using Sign-Extension Method

2. BOOTH’S Algorithm
Sequential Circuit Multiplier

Register A (initially 0)

Shift right

a a q q
C n - 1 0 n- 1 0

Multiplier Q
Add/Noadd
control

n-bit
Adder
MUX Control
sequencer

0 0

m m
n - 1 0

Multiplicand M
 Signed-operand Multiplication(Sign Extension Method)
• Considering 2’s-complement signed operands, what will happen to
(-13)(+11) if following the same method of unsigned multiplication?

(-13) Multiplicand 1 0 0 1 1 (5 bits)

X
(+11) Multiplier 0 1 0 1 1 (5 bits)

1 1 1 1 1 1 0 0 1 1

1 1 1 1 1 0 0 1 1
Sign extension is
shown in blue 0 0 0 0 0 0 0 0

1 1 1 0 0 1 1

0 0 0 0 0 0

1 1 0 1 1 1 0 0 0 1 ( - 143)
Sign extension of negative multiplicand.
MULTIPLICATION
BOOTH’S Algorithm
Signed Multiplication

• For a negative multiplier, a straightforward solution

is to form the 2’s-complement of both the multiplier
and the multiplicand and proceed as in the case of
a positive multiplier.
• This is possible because complementation of both
operands does not change the value or the sign of
the product.
• A technique that works equally well for both
negative and positive multipliers – Booth algorithm.
 Booth Algorithm

• Consider in a multiplication, the multiplier is positive

0011110, how many appropriately shifted versions of
the multiplicand are added in a standard procedure?

0 1 0 1 1 0 1
0 0 +1 +1 + 1+1 0
0 0 0 0 0 0 0
0 1 0 1 1 0 1
0 1 0 1 1 0 1
0 1 0 1 1 0 1
0 1 0 1 1 0 1
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 1 0 1 0 1 0 0 0 1 1 0
Booth Algorithm

• Since 0011110 = 0100000 – 0000010, if we use the

expression to the right, what will happen?

0 1 0 1 1 0 1
0 +1 0 0 0 - 1 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0
2's complement of
1 1 1 1 1 1 1 0 1 0 0 1 1
the multiplicand
0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 1 0 1 1 0 1
0 0 0 0 0 0 0 0
0 0 0 1 0 1 0 1 0 0 0 1 1 0
 BOOTH’S Algorithm

• The booth algorithm generates the 2n-bit product and treats both
positive and negative 2’s complement n-bit operands uniformly.
• In general, in the booth scheme, -1 times the shifted multiplicand is
selected when moving from 0 to 1, and +1 times the multiplicand is
selected when moving from 1 to 0.
Example:
Recode the multiplier 101100 for Booth’s algorithm?

Multiplier: 1 0 1 1 0 0 0
Recoded Multiplier: -1 +1 0 -1 0 0
Saturday, February 15, 2
2 025
7
Booth Algorithm

Multiplier
V ersion of multiplicand
selected by biti
Bit i Bit i -1

0 0 0 XM
0 1 + 1 XM
1 0  1 XM
1 1 0 XM

Booth multiplier recoding table.

 Booth Algorithm

• In general, in the Booth scheme, -1 times the shifted

multiplicand is selected when moving from 0 to 1, and +1
times the shifted multiplicand is selected when moving from 1
to 0, as the multiplier is scanned from right to left.
0 0 1 0 1 1 0 0 1 1 1 0 1 0 1 1 0 0

0 +1 -1 +1 0 - 1 0 +1 0 0 - 1 +1 - 1 + 1 0 - 1 0 0

Booth recoding of a multiplier.

Booth Algorithm

0 1 1 0 1 ( + 13) 0 1 1 0 1
X1 1 0 1 0 (- 6) 0 - 1 +1 - 1 0
0 0 0 0 0 0 0 0 0 0
1 1 1 1 1 0 0 1 1
0 0 0 0 1 1 0 1
1 1 1 0 0 1 1
0 0 0 0 0 0
1 1 1 0 1 1 0 0 1 0 ( - 78)

Booth multiplication with a negative multiplier.

Booth Algorithm

• Best case – a long string of 1’s (skipping over 1s)

• Worst case – 0’s and 1’s are alternating
0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
Worst-case
multiplier
+1 - 1 +1 - 1 +1 - 1 +1 - 1 +1 - 1 +1 - 1 +1 - 1 +1 - 1

1 1 0 0 0 1 0 1 1 0 1 1 1 1 0 0
Ordinary
multiplier
0 -1 0 0 +1 - 1 +1 0 - 1 +1 0 0 0 -1 0 0

0 0 0 0 1 1 1 1 1 0 0 0 0 1 1 1
Good
multiplier
0 0 0 +1 0 0 0 0 -1 0 0 0 +1 0 0 -1
 BOOTH’S Algorithm
(+45) Multiplicand 0 1 0 1 1 0 1 (7 bits)
X
(+30) Multiplier 0 0 1 1 1 1 0 (7 bits)

Booth Recoded Multiplier 0 1 0 0 0 -1 0 (7 bits)

0 0 0 0 0 0 0 0 0 0 0 0 0 0

1 1 1 1 1 1 1 0 1 0 0 1 1

0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0

0 0 0 1 0 1 1 0 1

0 0 0 0 0 0 0 0

0 0 0 1 0 1 0 1 0 0 0 1 1 0 ( + 1350 )
 Saturday, February 15, 2
3 025
3
 Saturday, February 15, 2
3 025
4
Integer Division
Restoring Division Algorithm
Manual Division

21 10101
13 274 1101 100010010
26 1101
14 10000
13 1101
1 1110
1101
1

Longhand division examples.

Longhand Division Steps

• Position the divisor appropriately with respect to

the dividend and performs a subtraction.
• If the remainder is zero or positive, a quotient bit of
1 is determined, the remainder is extended by
another bit of the dividend, the divisor is
repositioned, and another subtraction is performed.
• If the remainder is negative, a quotient bit of 0 is
determined, the dividend is restored by adding
back the divisor, and the divisor is repositioned for
another subtraction.
Circuit Arrangement for binary division

Shift left

an an-1 a0 qn-1 q0
Dividend Q
A Quotient
Setting

N+1 bit Add/Subtract

adder
Control
Sequencer

0 mn-1 m0

Divisor M
 Restoring
Division
• Figure in the previous slide shows a logic circuit arrangement that
implements restoring division.
• An n-bit positive divisor is loaded into register M.
• An n-bit positive dividend is loaded into register Q at the start of
the operation.
• Register A is set to 0.
• After the division is complete,

n-bit Quotient  Register Q

Remainder  Register A

• The extra bit position at the end of both A and M accommodates

the sign bit during subtractions.

Saturday, February 15, 2

3 025
9
 Restoring Division
Algorithm
The following algorithm performs the restoring division:

Do the following ‘n’ times:

1. Shift A and Q left one binary position.
2. Subtract M from A, and place the answer back in A.
3. If the sign of A is 1, set Q0 to 0 and add M back to
A(that is, restore A); otherwise set Q0 to 1.

Figure 6.22 shows a 4-bit example as it would be

processed by the circuit in the figure 6.21

Saturday, February 15, 2

4 025
0
 Restoring Division Algorithm
Flowchart

4
1
 Examples

Initially 0 0 0 0 0 1 0 0 0
0 0 0 1 1
Shift 0 0 0 0 1 0 0 0
Subtract 1 1 1 0 1 First cycle
Set q0 1 1 1 1 0
Restore 1 1
0 0 0 0 1 0 0 0 0
1 0 Shift 0 0 0 1 0 0 0 0
1 1 1 0 0 0 Subtract 1 1 1 0 1
1 1 Set q0 1 1 1 1 1 Second cycle
Restore 1 1
1 0 0 0 0 1 0 0 0 0 0
Shift 0 0 1 0 0 0 0 0
Subtract 1 1 1 0 1
Set q0 0 0 0 0 1 Third cycle

Shift 0 0 0 1 0 0 0 0 1
Subtract 1 1 1 0 1 0 0 1
Set q0 1 1 1 1 1 Fourth cycle
Restore 1 1
0 0 0 1 0 0 0 1 0

Remainder Quotient
Figure 6.22. A restoring-division example.
 End of Module 3

Saturday, February 15, 43

2025