MODULE 4

ARITHMETIC
Computer Organization, Fifth Edition
Carl Hamacher, Zvonko Vranesic, Safwat Zaky
 OUTLINE

▪ Numbers - Arithmetic Operations and Characters

▪ Addition and Subtraction of Signed Numbers

▪ Design of Fast Adders

▪ Multiplication of Positive Numbers

▪ Signed Operand Multiplication

▪ Fast Multiplication

▪ Integer Division
Number, Arithmetic Operations, And Characters
▪ We obviously need to represent both positive and negative numbers.
▪ Three systems are used for representing such numbers :
▪ Sign-and-magnitude
▪ 1’s-complement
▪ 2’s-complement

▪ In all three systems, the leftmost bit is 0 for positive numbers and 1 for
negative numbers.

▪ Positive values have identical representations in all systems, but

negative values have different representations.
Number, Arithmetic Operations, And Characters
▪ In the sign-and-magnitude systems, negative values are represented by
changing the most significant bit (b3) from 0 to 1.
Ex: +5 is represented by 0101, and -5 is represented by 1101.
▪ In 1’scomplement representation, negative values are obtained by
complementing each bit of the corresponding positive number.
Ex: The representation for -3 is obtained by complementing each bit in
the vector 0011 to yield 1100.
clearly, the same operation, bit complementing, is done in converting a
negative number to the corresponding positive value. Converting either
way is referred to as forming the 1’s-complement of a given number.
▪ In 2’s-complement system, forming the 2’s-complement of a number is
done by subtracting that number from 2^n.
Hence, the 2’s complement of a number is obtained by adding 1 to the
1’s complement of that number.
Binary, Signed-integer Representations
Assumptions: 4-bit machine word, 16 different values can be represented, Roughly
half are positive, half are negative

B Values represented

Sign and
b3 b2b1b0 magnitude 1's complement 2's complement

0 1 1 1 + 7 +7 + 7
0 1 1 0 + 6 +6 + 6
0 1 0 1 + 5 +5 + 5
0 1 0 0 + 4 +4 + 4
0 0 1 1 + 3 +3 + 3
0 0 1 0 + 2 +2 + 2
0 0 0 1 + 1 + 1 + 1
0 0 0 0 + 0 +0 + 0
1 0 0 0 - 0 -7 - 8
1 0 0 1 - 1 -6 - 7
1 0 1 0 - 2 -5 - 6
1 0 1 1 - 3 -4 - 5
1 1 0 0 - 4 -3 - 4
1 1 0 1 - 5 -2 - 3
1 1 1 0 - 6 - 1 - 2
1 1 1 1 - 7 -0 - 1

Figure 2.1. Binary, signed-integer representations.

▪ +5=0101
▪ -5 =1010
▪ + 1
▪ 1011 that is -3

▪ 0111
▪ 1000
▪ + 1
▪ 1001

▪ 1
▪ 1
▪ 1 0
Sign And Magnitude Representation
-7 +0
-6 1111 0000 +1
1110 0001
-5 +2 +
1101 0010
-4 1100 0011 +3 0 100 = + 4

-3 1011 0100 +4 1 100 = - 4

1010 0101
-2 +5 -
1001 0110
-1 1000 0111 +6
-0 +7

High order bit is sign: 0 = positive (or zero), 1 = negative

Three low order bits is the magnitude: 0 (000) thru 7 (111)
Number range for n bits = +/-2n-1 -1
Two representations for 0
 One’s Complement Representation

-0 +0
-1 1111 0000 +1
1110 0001
-2 +2 +
1101 0010
-3 1100 0011 +3 0 100 = + 4

-4 1011 0100 +4 1 011 = - 4

1010 0101
-5 +5 -
1001 0110
-6 1000 0111 +6
-7 +7

▪ Subtraction implemented by addition & 1's complement

▪ Still two representations of 0! This causes some problems.
▪ Some complexities in addition.
Two’s Complement Representation

-1 +0
-2 1111 0000 +1
1110 0001
-3 +2 +
1101 0010
-4 1100 0011 +3 0 100 = + 4
like 1's comp
except shifted -5 1011 1 100 = - 4
one position
0100 +4
clockwise 1010 0101
-6 +5 -
1001 0110
-7 1000 0111 +6
-8 +7

▪ Only one representation for 0.

▪ One more negative number than positive number.
Addition And Subtraction – 2’s Complement

4 0100 -4 1100
+3 0011 + (-3) 1101
If carry-in to the high
order bit = 7 0111 -7 11001
carry-out then ignore carry

If carry-in differs from

carry-out then overflow 4 0100 -4 1100
-3 1101 +3 0011
1 10001 -1 1111

Simpler addition scheme makes twos complement the most common

choice for integer number systems within digital systems
Addition/Subtraction of Signed Numbers

xi yi Carry-in c i Sum s i Carry-out c i +1

At the ith stage:
0 0 0 0 0
0 0 1 1 0 Input:
0 1 0 1 0
0 1 1 0 1
ci is the carry-in
1
1
0
0
0
1
1
0
0
1
Output:
1 1 0 0 1 si is the sum
1 1 1 1 1
ci+1 carry-out to
si = xi yi ci + xi yi ci + xi yi ci + xi yi ci = x i  yi  c i
(i+1)st
c i +1 = yi c i + x i ci + x i y i
state
E xample:

X 7 0 1 1 1 Carry-out xi Carry-in
+ Y = +6 = + 00 1 1 1 1 0 0 0 yi
c i+1 ci
Z 13 1 1 0 1 si

Legend for stage i

Addition Logic For A Single Stage- Full Adder

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

ci + 1 Full adder ci
(FA)

s
i

Full Adder (FA): Symbol for the complete circuit

for a single stage of addition.
Binary Addition-subtraction Logic Network

y y y
n- 1 1 0
Add/Sub
control

x x x
n- 1 1 0

c n-bit adder
n c
0

s s s
n- 1 1 0

•Add/sub control = 0, addition.

•Add/sub control = 1, subtraction.
Detecting overflows

• Overflows can only occur when the sign of the two operands is the
same.

• Overflow occurs if the sign of the result is different from the sign of
the operands.

• Recall that the MSB represents the sign.

• xn-1, yn-1, sn-1 represent the sign of operand x, operand y and result
s respectively.
 n-Bit Adder Formation

A 4-bitFull Adder is integrated by cascading four numbers of 1-bit adders

as in figure. When cascaded the Cout of ith goes as Cin of i+1th position
and hence the carry is said to be propagated.

S is the Sum bits, Cout is the final Carry out of the adder.

X and Y are the input numbers. Ci is carry-in if available.

Such cascading can be extended to any number of bits using 1-bit FA or

n-bit FA blocks.
 N-bit Adder
•Cascade n full adder (FA) blocks to form a n-bit adder.
•Carries propagate or ripple through this cascade, n-bit ripple carry
adder.

x y x y x y
n- 1 n- 1 1 1 0 0

c c
n- 1 1
c c
n FA FA FA
0

s s s
n- 1 1 0

Most significant bit Least significant bit

(MSB) position (LSB) position

Carry-in c0 into the LSB position provides a convenient way to

perform subtraction.
This method of Adder expansion is known as Spatial Expansion as the
output of all the n-bits are available at the same time as 1-bit operation,
probably in one clock cycle.

Spatial Expansion is also known as Parallel Adder. The other name for
this method is Ripple Carry adder as the carry is propagated internally.

However, for large n-value, the carry propagation delay for clean and
settled output proportionately increases.

This is a disadvantage of Ripple Carry Adder which is solved by Carry-

Look-Ahead Adder Technique.
 Carry Look Ahead Adder

This is also a spatial expansion and ripple carry type. The Carry Look
Ahead Adder (CLA) uses specialized logic called Carry Look ahead
Logic to compute carries in parallel and hence is faster than Ripple
Carry Adder.

CLA Adder generates two other signals namely Propagate Carry and
Generate Carry which can be used by the next stage for Carry
Calculation.
Propagate Carry Pi = Ai + Bi
i.e when either of the number has '1' in the bit position, the carry is
likely depending on the Ci.

Generate Carry Gi = AiBi

i.e. when both the numbers have '1' in their bit position in which case
carry is sure to be generated.

The carry formula can be rewritten in terms of Propagate and Generate

carry as Cout = Pi + CiGi.

In a Carry look-ahead adder, the carries are computed in parallel using

carry look-ahead logic, in one gate delay as compared to 2-gate delays
per bit in the case of Ripple carry adder.
 K N-bit Adder

K n-bit numbers can be added by cascading k n-bit adders.

xkn - 1 ykn - 1 x2n - 1 y2n - 1 xn y n xn - 1 y n - 1 x 0 y 0

cn
n-bit n-bit n-bit c
c kn 0
adder adder adder

s s( s s s s
kn - 1 k - 1) n 2n - 1 n n- 1 0

Each n-bit adder forms a block, so this is cascading of blocks.

Carries ripple or propagate through blocks, Blocked Ripple Carry

Adder
In an n-bit parallel adder (ripple-carry adder), there is too much delay in
developing the outputs, so through sn-1and c.

On many occasions this delay is not acceptable; in comparison with the

speed of other processor components and speed of the data transfer
between registers and cache memories.

The delay through a network depends on the integrated circuit

technology used in fabricating the network and on the number of gates
in the paths from inputs to outputs (propagation delay).

The delay through any combinational logic network constructed from

gates in a particular technology is determined by adding up the number
of logic-gate delays along the longest signal propagation path through
the network.
 Design of Fast Adders

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.
 Carry-lookahead Addition

ci +1 = Gi + Pi ci
ci = Gi −1 + Pi −1ci −1
 ci+1 = Gi + Pi (Gi −1 + Pi −1ci −1 )
continuing
 ci+1 = Gi + Pi (Gi −1 + Pi −1 (Gi − 2 + Pi− 2 ci −2 ))
until
ci+1 = Gi + PiGi −1 + Pi Pi−1 Gi −2 + .. + Pi Pi −1 ..P1G0 + Pi Pi −1 ...P0 c 0

•All carries can be obtained 3 gate delays after X, Y and c0 are applied.
-One gate delay for Pi and Gi
-Two gate delays in the AND-OR circuit for ci+1
•All sums can be obtained 1 gate delay after the carries are computed.
•Independent of n, n-bit addition requires only 4 gate delays.
•This is called Carry Lookahead adder.
Carry-lookahead Addition
x y x y x y x y
3 3 2 2 1 1 0 0

c4
c
3
c
2
c
1
.
4-bit
c
B cell B cell B cell B cell 0

carry-lookahead
s
3
s
2
s
1
s
0
adder
G3 P3 G2 P2 G P G P
1 1 0 0

Carry-lookahead logic

xi yi

. .
. c
i
B-cell for a single stage
B cell

G i
P i
si
Carry-lookahead Addition

 Performing n-bit addition in 4 gate delays independent of n is

good only theoretically because of fan-in constraints.

ci+1 = Gi + PiGi −1 + Pi Pi−1 Gi −2 + .. + Pi Pi −1 ..P1G0 + Pi Pi −1 ...P0 c0

 Last AND gate and OR gate require a fan-in of (n+1) for a n-

bit adder.
 For a 4-bit adder (n=4) fan-in of 5 is required.
 Practical limit for most gates.
 In order to add operands longer than 4 bits, we can cascade 4-
bit Carry-Lookahead adders. Cascade of Carry-Lookahead
adders is called Blocked Carry-Lookahead adder.
4-bit Carry-lookahead Adder
4-bit Carry-lookahead Adder
 16 Bit Carry-lookahead Adder
x15-12 y15-12 x11-8 y11-8 x7-4 y7-4 x3-0 y3-0

c 16 4-bit adder
c 12
4-bit adder
c8
4-bit adder
c4
4-bit adder . c0

s15-12 s11-8 s7-4 s3-0

G3I P3I G2 I P 2I G 1I P 1I G 0I P0 I

Carry-lookahead logic

After xi, yi and c0 are applied as inputs:

- Gi and Pi for each stage are available after 1 gate delay.
- PI is available after 2 and GI after 3 gate delays.
- All carries are available after 5 gate delays.
- c16 is available after 5 gate delays.
- s15 which depends on c12 is available after 8 (5+3)gate delays
(Recall that for a 4-bit carry lookahead adder, the last sum bit is
available 3 gate delays after all inputs are available)
 Multiplication Algorithm
• The multiplier and multiplicand bits are loaded into two registers Q
and M. A third register A is initially set to zero.

• C is the 1-bit register which holds the carry bit resulting from
addition.
• Now, the control logic reads the bits of the multiplier one at a time.

• If Q0 is 1, the multiplicand is added to the register A and is stored

back in register A with C bit used for carry.

• Then all the bits of CAQ are shifted to the right 1 bit so that C bit goes
to An-1, A0 goes to Qn-1 and Q0 is lost.

• If Q0 is 0, no addition is performed just do the shift.

The process is repeated for each bit of the original multiplier.

• The resulting 2n bit product is contained in the QA register.

Multiplication Algorithm
Multiplication of Positive Numbers

Product of 2 n-bit numbers is at most a 2n-bit number.

Unsigned multiplication can be viewed as addition of shifted
versions of the multiplicand.
Multiplication of Positive Numbers

 We added the partial products at end.

 Alternative would be to add the partial products at each stage.

 Rules to implement multiplication are:

 If the ith bit of the multiplier is 1, shift the multiplicand and add the
shifted multiplicand to the current value of the partial product.

 Hand over the partial product to the next stage.

 Value of the partial product at the start stage is 0.

Multiplication Algorithm
Multiplication of Positive Numbers
Typical multiplication cell

Bit of incoming partial product (PPi)

jth multiplicand bit

ith multiplier bit ith multiplier bit

carry out FA carry in

Bit of outgoing partial product (PP(i+1))

Multiplication of Positive Numbers
Combinatorial array multiplier

Multiplicand

0 m3 0 m2 0 m1 0 m0
(PP0)
q0
0
PP1 p0
q1
0
PP2 p1
q2
0
PP3 p2
q3
0
,
p7 p6 p5 p4 p3

Product is: p7,p6,..p0

Multiplicand is shifted by displacing it through an array of

adders.
Multiplication of Positive Numbers

▪ Combinatorial array multipliers are:

▪ Extremely inefficient.

▪ Have a high gate count for multiplying numbers of practical size

such as 32-bit or 64-bit numbers.

▪ Perform only one function, namely, unsigned integer product.

▪ Improve gate efficiency by using a mixture of combinatorial array

techniques and sequential techniques requiring less combinational
logic.
 Sequential Multiplication
▪ Recall the rule for generating partial products:
▪ If the ith bit of the multiplier is 1, add the appropriately shifted
multiplicand to the current partial product.

▪ Multiplicand has been shifted left when added to the partial product.

▪ However, adding a left-shifted multiplicand to an unshifted partial

product is equivalent to adding an unshifted multiplicand to a right-
shifted partial product.
 Sequential Multiplication
▪ This circuit performs multiplication by using
▪ Single n-bit adder n times to implement the spatial addition performed
by the n rows of ripple-carry adders in array multiplier.
▪ Registers A and Q are shift registers, concatenated as shown, they hold
partial product PPi while multiplier bit qi generates the signal Add/No
add.
▪ This signal causes the multiplexer MUX to select 0 when qi = 0, or to
select the multiplicand M when qi = 1, to be added to PPi to generate
PP(i + 1).
▪ The product is computed in n cycles.
▪ Initially Register A is loaded with PPi as 0s ( n bit 0s).
▪ The Sequential Circuit Multiplier is as shown in Figure.
Sequential Circuit Multiplier

Register A (initially 0)

Shift right

C a a q q
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
 Sequential Multiplication
▪ Step 1: Initially Register A is loaded with PPi as Zero and Register Q
with Multiplier.

▪ Step 2: Check the status of Least Significant bit (LSB) of Register Q.

q0 acts as the selection bit for n bit 2:1 MUX to multiplex either 0 or
Multiplicand. If q0=0 – Zero is Multiplexed else Multiplicand is
multiplexed.

▪ Step 3: The Multiplexed data is added with the content of Register A

(PPi) to generate PP(i+1) and stored back in Register A.

▪ Step 4: Shift the concatenated Register A and Register Q to right by 1

bit position with Carry out of adder entering at MSB of Register A.

▪ Step 5: Go back to Step 2 and repeat the step (2-5) for (n-1) cycle.
Sequential Multiplication

M
1 1 0 1
Initial configuration
0 0 0 0 0 1 0 1 1
C A Q

0 1 1 0 1 1 0 1 1 Add
First cycle
0 0 1 1 0 1 1 0 1 Shift

1 0 0 1 1 1 1 0 1 Add
Second cycle
0 1 0 0 1 1 1 1 0 Shift

0 1 0 0 1 1 1 1 0 No add
Shift Third cycle
0 0 1 0 0 1 1 1 1

1 0 0 0 1 1 1 1 1 Add
Fourth cycle
0 1 0 0 0 1 1 1 1 Shift

Product
Multiplying Negative Numbers
•
This does not work!

• Solution 1
—Convert to positive if required.

—Multiply as above.

—If signs were different, negate answer.

• Solution 2
—Booth’s algorithm.
Signed-operand Multiplication
▪ Considering 2’s-complement signed operands, what will happen to
(-13)(+11) if following the same method of unsigned multiplication?

1 0 0 1 1 ( - 13)
0 1 0 1 1 ( + 11)

1 1 1 1 1 1 0 0 1 1

1 1 1 1 1 0 0 1 1
Sign extension is
shown in red 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.

 Signed-Operand 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.
What is Booth’s algorithm?

Booth's multiplication algorithm is an algorithm which multiplies 2

signed or unsigned integers in 2's complement.

This approach uses fewer additions and subtractions than more

straightforward algorithms.

History
The algorithm was invented by Andrew Donald Booth in 1950 while
doing research on crystallography at Birkbeck College in Bloomsbury,
London.
 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 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
X 1 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

Multiplier
Version of multiplicand
selected by biti
Bit i Bit i -1

0 0 0 xM
0 1 +1 x M
1 0 −1 x M
1 1 0 xM

Booth multiplier recoding table.

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
Fast Multiplication
Bit-pair Recoding of Multipliers

▪ Bit-pair recoding halves the maximum number of summands

(versions of the multiplicand).

Sign extension Implied 0 to right of LSB

1 1 1 0 1 0 0

0 0 −1 +1 −1 0

0 −1 −2

(a) Example of bit-pair recoding derived from Booth recoding

Fast Multiplication
Bit-pair Recoding of Multipliers

Multiplier bit-pair Multiplier bit on the right Multiplicand

i +1 i i −1 selected at position

0 0 0 0 X M
0 0 1 +1 X M
0 1 0 +1 X M
0 1 1 +2 X M
1 0 0 −2 X M
1 0 1 −1 X M
1 1 0 −1 X M
1 1 1 0 X M

(b) Table of multiplicand selection decisions

Fast Multiplication
Bit-pair Recoding of Multipliers

0 1 1 0 1
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 1 1 0 1 ( + 13) 0 0 0 0 0 0
´ 1 1 0 1 0 (- 6) 1 1 1 0 1 1 0 0 1 0 ( - 78)

0 1 1 0 1
0 -1 - 2
1 1 1 1 1 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

Figure 6.15. Multiplication requiring only n/2 summands.

Fast Multiplication
Carry-save Addition of Summands
▪ Ripple carry array

P7 P6 P5 P4 P3 P2 P1 P0
 Fast Multiplication
Carry-save Addition of Summands
▪ Carry-save array

P7 P6 P5 P4 P3 P2 P1 P0
Fast Multiplication
Carry-save Addition of Summands
▪ Consider the addition of many summands, we can:
➢ Group the summands in threes and perform carry-save addition on
each of these groups in parallel to generate a set of S and C vectors
in one full-adder delay.
➢ Group all of the S and C vectors into threes, and perform carry-
save addition on them, generating a further set of S and C vectors
in one more full-adder delay.
➢ Continue with this process until there are only two vectors
remaining.
➢ They can be added in a RCA or CLA to produce the desired
product.
 Fast Multiplication
Carry-save Addition of Summands

1 0 1 1 0 1
(45) M
X 1 1 1 1 1 1
(63) Q
1 0 1 1 0 1
A
1 0 1 1 0 1
B
1 0 1 1 0 1
C
1 0 1 1 0 1
D
1 0 1 1 0 1
E
1 0 1 1 0 1
F
1 0 1 1 0 0 0 1 0 0 1 1
(2,835) Product

Figure 6.17. A multiplication example used to illustrate carry-save addition as shown in Figure 6.18.
 1 0 1 1 0 1
x 1 1 1 1 1 1 M
Q
1 0 1 1 0 1
1 0 1 1 0 1 A
1 0 1 1 0 1 B
1 1 0 0 0 0 1 1 C1
0 0 1 1 1 1 0 0 S1
C
1 0 1 1 0 1
1 0 1 1 0 1 D
1 0 1 1 0 1 E
1 1 0 0 0 0 1 1 F2
0 0 1 1 1 1 0 0 S2
1 1 0 0 0 0 1 1 C1
0 0 1 1 1 1 0 0 S1
1 1 0 0 0 0 1 1 C2
1 1 0 1 0 1 0 0 0 1 1 S3
0 0 0 0 1 0 1 1 0 0 0 S3
0 0 1 1 1 1 0 0 C2
0 1 0 1 1 1 0 1 0 0 1 1 C4
+ 0 1 0 1 0 1 0 0 0 0 0 S4
1 0 1 1 0 0 0 1 0 0 1 1 C
Product
Figure 6.18. The multiplication example from Figure 6.17 performed using carry-save addition.
Integer Division
Manual Division

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

Longhand division examples.

 Integer Division
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.
Integer Division
Circuit Arrangement

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

Figure 6.21. Circuit arrangement for binary division.

 Integer Division
Restoring Division
▪ Shift A and Q left one binary position.
▪ Subtract M from A, and place the answer back in A.
▪ If the sign of A is 1, set q0 to 0 and add M back to A (restore A);
otherwise, set q0 to 1.
▪ Repeat these steps n times.
▪ NOTE:1)No of bits to represent the dividend Q ex 8:1000.
▪ 2)no of bits in A should be one bit >Q if Q=4 then A=5 bits then M=A
bits I,e M=5 BITS.
Restoring Division
Example
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 10 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.
Integer Division
Nonrestoring Division
▪ Avoid the need for restoring A after an unsuccessful subtraction.

▪ Step 1: (Repeat n times)

➢If the sign of A is 0, shift A and Q left one bit position and subtract
M from A; otherwise, shift A and Q left and add M to A.
➢Now, if the sign of A is 0, set q0 to 1; otherwise, set q0 to 0.

▪ Step2: If the sign of A is 1, add M to A

Nonrestoring Division
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 First cycle
Subtract 1 1 1 0 1
Set q 0 1 1 1 1 0 0 0 0 0

Shift 1 1 1 0 0 0 0 0
Add 0 0 0 1 1 Second cycle

Set q 1 1 1 1 1 0 0 0 0
0

Shift 1 1 1 1 0 0 0 0
1 1 1 1 1 Add 0 0 0 1 1 Third cycle
Restore
0 0 0 1 1 Set q 0 0 0 0 1 0 0 0 1
remainder 0
Add 0 0 0 1 0
Remainder Shift 0 0 0 1 0 0 0 1
Subtract 1 1 1 0 1 Fourth cycle
Set q 1 1 1 1 1 0 0 1 0
0

Quotient
A nonrestoring-division example.
 Model Questions
1. Explain with figure the design and working of a 16 bit carry look
ahead adder built from 4 bit adders.
2. Explain booth algorithm. Apply booth algorithm to multiply the
signed numbers +13 x -6 and -13 x +9.
3. Write circuit arrangement for sequential binary multiplier, explain
with example.
4. Differentiate between restoring and non - restoring division. Perform
restoring division for the given binary numbers 1000/11, show all
cycles.
5. Design 4 bit carry look ahead logic and explain how it is faster than 4
bit ripple adder.
6. Multiply 14 x -8 using booth's algorithm.
7. With figure explain circuit arrangements for binary division.
8. Design a logic circuit to perform addition/ subtraction of two 'n' bit
numbers X and Y.
9. How do you design FAST ADDERS? Explain a 4 bit carry
look ahead adder.