Computer organization(18CS34)

Module-4
Arithmetic: 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, Floating-point Numbers and Operations.
Textbook 1: Ch 2: 2.1, Ch 6: 6.1 to 6.7

4.1. NUMBERS, ARITHMETIC OPERATIONS AND CHARACTERS

4.1.1. NUMBER REPRESENTATION
•The most natural way to represent a number in a computer system is by a string of bits, called a binary number.
•Consider an n-bit vector
B = bn−1 . . . b1b0 where bi = 0 or 1 for 0 ≤ i ≤ n − 1.
•This vector can represent an unsigned integer value V(B) in the range 0 to 2n −1, where
V(B) = bn−1 × 2n−1 +・ ・ ・+b1 × 21 + b0 × 20

• Numbers can be represented in 3 formats:

1) Sign and magnitude
2) 1's complement
3) 2's complement

• In all three formats, MSB=0 for +ve numbers & MSB=1 for -ve numbers.

 sign-and-magnitude system
• In the sign-and-magnitude system, negative value is obtained by changing the MSB from 0 to 1 of the
corresponding positive value.
For example, +5 is represented by 0101 &
-5 is represented by 1101.
 1's complement
• In 1's complement representation, negative values are obtained by complementing each bit of the
corresponding
positive number.
For example, -3 is obtained by complementing each bit in 0011 to yield 1100.
•In other words, the operation of forming the 1's complement of a given number is equivalent to subtracting
that number from 2 n- 1

 2's complement
•the 2's complement of a number is obtained by adding 1 to the 1's complement of that number
•In other words, the 2's complement system, forming the 2's complement of a number is done by subtracting
that number from 2n.
• The 2's complement system yields the most efficient way to carry out addition and subtraction operations .

EPCET-ISE Page 1
Computer organization(18CS34)

Figure below illustrates all three representations using 4-bit numbers.

Positive values have identical representations in all systems, but negative values have different
representations.

Range
Unsigned integers Signed integers No. representations
for zero
Sign and magnitude 0 - 2n- 1 - (2n-1- 1) to (2n-1 – 1) 2 ( +0 and -0)
1's complement 0 - 2n- 1 - (2n-1- 1) to (2n-1 – 1) 2 ( +0 and -0)
2's complement 0 - 2n- 1 - (2n-1) to (2n-1 – 1) 1 ( +0 )

4.1.2. ADDITION OF POSITIVE NUMBERS

• Consider adding two 1-bit numbers as shown in figure.

• The sum of 1 & 1 requires the 2-bit vector 10 to
represent the value 2.
• We say that sum is 0 and the carry-out is 1

• In order to add multiple-bit numbers,we add bit pairs starting from the low-order (right) end of the bit vectors,
propagating carries toward the high-order (left) end.
•The carry-out from a bit pair becomes the carry-in to the next bit pair to the left.
•The carry-in must be added to a bit pair in generating the sum and carry-out at that position.

EPCET-ISE Page 2
Computer organization(18CS34)

4.1.3. ADDITION & SUBTRACTION OF SIGNED NUMBERS

• To understand 2’s-complement arithmetic, consider addition modulo N
(abbreviated as mod N).

• A helpful graphical device for the description of addition of unsigned integers

mod N is a circle with the values 0 through N − 1 marked along its perimeter,
as shown in Figure (a).

• The computation of (a + b) mod N for any unsigned integers a and b, is,

-locate a and move b units in the clockwise direction to arrive at (a + b) mod N

• If a or b is negative numbers then 1st convert them into 2’s complement and then follow the above procedure.

Eg: N = 16, shown in part (b) of the figure.

The decimal values 0 through 15 are represented by
their 4-bit binary values 0000 through 1111 around
the outside of the circle.

 the operation (7 + 5) mod 16 yields the value 12.

• To perform this operation graphically, locate 7 (0111) on the
outside of the circle and then move 5 units in the clockwise
direction to arrive at the answer 12 (1100).

 The operation ( 7 + (-3) ) mod 16 yields 4

• The 2’s-complement representation for these numbers is
+7  0111 and
-3  1101 (13)
• To add these numbers, locate 0111 on the circle in Figure (b).
• Then move 1101 (13) steps in the clockwise direction to arrive at 0100, which yields the correct answer of +4.
• If we perform this addition by adding bit pairs from right to left, we obtain
0111
+1101
10100
↑
Carry-out

• If we ignore the carry-out from the fourth bit position in this addition, we obtain the correct answer this carry-
out is a natural result of using mod N arithmetic. As we move around the circle in Figure (b), the value next to
1111 would normally be 10000. Instead, we go back to the value 0000.

EPCET-ISE Page 3
Computer organization(18CS34)

• Following are the two rules for addition and subtraction of n-bit signed numbers using the 2's
complement representation system.
1) To add two numbers, add their n-bits and ignore the carry-out signal from the MSB position. The
sum will be algebraically correct value as long as the answer is in the range -2n-1 through +2n-1-1

2) To subtract two numbers X and Y( that is to perform X-Y),take the 2's complement of Y and then
add it to X as in rule 1.Result will be algebraically correct, if it lies in the range (2 n-1) to +(2n-1-1).
• When the result of an arithmetic operation is outside the representable-range, an arithmetic overflow is said
to occur.
• To represent a signed in 2's complement form using a larger number of bits, repeat the sign bit as many
times as needed to the left. This operation is called sign extension.

• In 1's complement representation, the result obtained after an addition operation is not always correct.
• The carry-out(cn) cannot be ignored. If c n=0, the result obtained is correct. If c n=1, then a 1 must be added
to the result to make it correct.

• Figure below shows some examples of addition and subtraction in the 2’s-complement system.

• In all of these 4-bit examples, the

answers fall within the representable
range of −8 through +7.
• When answers do not fall within
the representable range, we say that
arithmetic overflow has occurred.

EPCET-ISE Page 4
Computer organization(18CS34)

4.1.4. OVERFLOW IN INTEGER ARITHMETIC

• When the result of an arithmetic operation is outside the representable-range, an arithmetic overflow is said
to occur.
• For example, when using 4-bit signed numbers, if we try to add the numbers +7 and +4, the output sum
S is 1011, which is the code for -5, an incorrect result.
• An overflow occurs in following 2 cases
1) Overflow can occur only when adding two numbers that have the same sign.
2) The carry-out signal from the sign-bit position is not a sufficient indicator of overflow when
adding signed numbers.

4.1.5. CHARACTER REPRESENTATION

• The most common encoding scheme for characters is ASCII (American Standard Code for Information
Interchange).
• Alphanumeric characters, operators, punctuation symbols, and control characters are represented by 7-bit
codes.
• It is convenient to use an 8-bit byte to represent and store a character.
• The code occupies the low-order seven bits.
• The high-order bit is usually set to 0.

EPCET-ISE Page 5
Computer organization(18CS34)

4.2. ADDITION AND SUBTRACTION OF SIGNED NUMBERS

4.2.1. FULL ADDER
• Figure below shows
i) the truth table for the sum and carry-out functions for
adding equally weighted bits xi and yi in two numbers
X and Y .
ii) logic expressions for these functions,
iii) an example of addition of the 4-bit unsigned numbers
7 and 6.
• Note that each stage of the addition process must
accommodate a carry-in bit.
• Ci -- represent the carry-in to stage i, which is the
same as the carry-out from stage (i − 1).

• The logic expression for si can be

implemented with a 3-input XOR gate

• The carry-out function, ci+1, is implemented

with an AND-OR circuit, as shown.

• A convenient symbol for the complete circuit

for a single stage of addition, called a
full adder (FA), is also shown in the figure.

• A cascaded connection of n full-adder blocks can be used to add two n-bit numbers, as shown in Figure.

• Since the carries must propagate, or ripple,

through this cascade, the configuration is
called a ripple-carry adder.

Delays in n-bit ripple carry addrer:

For Sn-1 is 2(n-1) +1
For Cn is 2n

EPCET-ISE Page 6
Computer organization(18CS34)

• The carry-in, c0, into the least-significant-bit (LSB) position provides a convenient means of adding 1 to a
number. For instance, forming the 2’s-complement of a number involves adding 1 to the 1’s-complement of the
number.

• The carry signals are also

useful for interconnecting k
adders to form an adder
capable of handling input
numbers that are kn bits long,
as shown in Figure.

 overflow
• The n-bit ripple-carry adder. can be used to add 2’s-complement numbers X and Y , where the xn−1 and yn−1
bits are the sign bits.
• The carry-out bit cn is not part of the answer.
• a circuit to detect overflow can be added to the n-bit adder by implementing the logic expression

• It can also be shown that overflow occurs when the carry bits cn and cn−1 are different.
• Therefore, a simpler circuit for detecting overflow can be obtained by implementing the expression cn ⊕ cn−1
with an XOR gate.

4.2.2 Addition/Subtraction Logic Unit

• In order to perform the subtraction operation X − Y on 2’s-complement numbers X and Y , we form the 2’s-
complement of Y and add it to X .
• The logic circuit shown in Figure can be
used to perform either addition or subtraction
based on the value applied to the Add/Sub
input control line.
• Control-line=0 for addition, applying Y
unchanged to one of the adder inputs along
with a carry-in signal, c0= 0.
• Control-line=1 for subtraction the Y number
is 1’s-complemented (that is, bit-
complemented) by the XOR gates
and c0=1 to complete the 2’s-complementation
of Y
• An XOR gate can be added to Figure to
detect the overflow condition cn ⊕cn−1

EPCET-ISE Page 7
Computer organization(18CS34)

4.3. DESIGN OF FAST ADDERS

• Drawback of ripple carry adder: If the adder is used to implement the addition/subtraction, all sum bits are
available in 2n gate delays.
• Two approaches can be used to reduce delay in adders:
i) Use the fastest possible electronic-technology in implementing the ripple-carry logic design
ii) Use an augmented logic-gate network structure

4.3.1. CARRY-LOOKAHEAD ADDITIONS

A fast adder circuit must speed up the generation of the carry signals
• The logic expression for si(sum) and ci+1(carry-out) of stage i are

si= xi ⊕ y i ⊕ ci ------(1)
ci+1=xiyi+xici+yici ------(2)
• Factoring (2) into
ci+1=xiyi + (xi+yi) ci
we can write
ci+1 = Gi + Pi ci where Gi = xiyi and Pi = xi+yi
• The expressions Gi and Pi are called generate and propagate functions.
• If Gi=1, then ci+1=1, independent of the input carry ci. This occurs when both xi and yi are 1.
Propagate function means that an input-carry will produce an output-carry when either xi=1 or
yi=1.
• All Gi and Pi functions can be formed independently and in parallel in one logic-gate delay.
A simpler circuit can be derived if propagate function can be realized as Pi = xi ⊕ yi , which differs from Pi = xi
+ yi only when xi = yi = 1.
But, in this case Gi = 1, so it does not matter whether Pi is 0 or 1.

Then, using a cascade of two 2-input XOR gates to realize the 3-input
XOR function for si , the basic B cell in Figure can be used in each bit
stage.
• Expanding ci in terms of i-1 subscripted variables and substituting into
the ci+1 expression, we obtain
ci+1 = Gi + PiGi−1 + PiPi−1ci−1
Continuing this type of expansion, the final expression for any carry
variable is
ci+1 =Gi + PiGi-1 + PiPi-1Gi-2 .......... +P1G0 + PiPi-1 . . . P0c0

• Conclusion:
Delay through the adder is 3 gate delays for all carry-bits & 4 gate delays for all sum-bits.
Thus the n-bit addition process requires only four gate delays, independent of n.

EPCET-ISE Page 8
Computer organization(18CS34)

• Consider the design of a 4-bit adder.

• The carries can be implemented as
c1=G0 + P0c0
c2=G1 + P1G0 + P1P0c0

c3=G2 + P2G1 + P2P1G0 + P2P1P0c0

c4=G3+ P3G2 + P3P2G1 + P3P2P1G0 + P3P2P1P0c0
• The complete 4-bit adder is shown in Figure below.

• The carries are implemented in the block labeled carry-lookahead logic.

• An adder implemented in this form is called a carry-lookahead adder.
• Delays in n-bit ripple carry addrer:
• For Sn-1 is 2(n-1) +1
• For Cn is 2n

•Thus Delay through the carry look ahead adder, independent of n bits:
• 3 gate delays for all carry bits and
• 4 gate delays for all sum bits.

• In comparison, a 4-bit ripple-carry adder.( delay: Sn-1 is 2(n-1) +1 , Cn is 2n ) requires

• 7 gate delays for s3 and
• 8 gate delays for c4

• Limitation: If we try to extend the carry-look ahead adder for longer operands, we run into a problem
of gate fan-in constraints.
- A fan-in of 5 is required for c4 in the 4-bit adder.
- This is about the limit for practical gates.
- Thus adder design shown in Figure above cannot be extended easily for longer operands.

EPCET-ISE Page 9
Computer organization(18CS34)

HIGHER-LEVEL GENERATE & PROPAGATE FUNCTIONS

 16-BIT ADDER CARRY-LOOKAHEAD ADDER

• 16-bit adder can be built from four 4-bit adder blocks as shown in Figure
• Each of the 4-bit adder block provide new output functions defined as Gk and Pk, where
- k=0 for the first 4-bit block,
- k=1 for the second 4-bit block and so on.
• In the first block,
PI0=P3P2P1P0 &
GI0=G3+P3G2+P3P2G1+P3P2P1G0
• The first-level Gi and Pi functions determine whether bit stage i generates or propagates a carry, and the
second level GIk and PIk functions determine whether block k generates or propagates a carry.
• With these new functions available, it is not necessary to wait for carries to ripple through the 4-bit blocks.
• Carries c4 to c16 is formed by one of the carry-lookahead circuits as
c4 = GI0 + PI0c0
c8 = GI1 + PI1GI0 + PI1PI0cI0
c12 = GI2 + PI2GI1 + PI2PI1GI0 + PI2PI1PI0c0
c16 = GI3 + PI3GI2 + PI3PI2GI1 + PI3PI2PI1GI0 + PI3PI2PI1PI0 c0
Delay :
•The delay in developing the carries produced by the carry-lookahead circuits is two gate delays more than the
delay needed to develop the GIk and PIk functions.
•But the GIk and PIk functions are two gate delays and one gate delay, respectively, after the generation of Gi
and Pi (outputs within single 4-bit adder) .
•Therefore, all carries produced by the carry-lookahead circuits are available 5 gate delays after X , Y , and
c0 are applied as inputs.

EPCET-ISE Page 10
Computer organization(18CS34)

•The carry c15 is generated inside the high-order 4-bit block two gate delays after c12, followed by s15 in one
further gate delay. Therefore, s15 is available after 8 gate delays.
• If a 16-bit adder is built by cascading 4-bit carry-lookahead adder blocks, the delays in developing c16 and
s15 are 9 and 10 gate delays, respectively,

 32-bit adder:
Two 16-bit adder blocks can be cascaded to implement a 32-bit adder. In this configuration, the output c16 from
the low-order block is the carry input to the high-order block.

EPCET-ISE Page 11