Unit - 5

Computer Arithmetic
The four basic arithmetic operations are addition, subtraction, multiplication and division. In
this chapter we develop the various arithmetic algorithms and show the procedure for
implementing them with digital hardware. We consider addition, subtraction,
m u l t i p l i c a t i o n , and division for the following types of data,
1. Fixed-point binary data in signed-magnitude representation
2. Fixed-point binary data in signed-2’s complement represent ation
3. Floating-point binary data
4. Binary-coded decimal (BCD) data

5.1 Addition and Subtraction

There are three ways of representing n e g a t i v e fixed-point binary numbers: signed-
magnitude, signed-l’s complement, or signed-2's complement. Most computers use the
signed-2’s complement representation when performing arithmetic operations with
integers. For floating-point operations, most computers use the signed-magnitude
representation for the mantissa.
5.1.1 Addition and Subtraction with Signed-Magnitude Data

 We designate the magnitude of the two numbers by A and B. When the signed
numbers are added or subtracted, we find that there are eight different conditions to
consider, depending on the sign of the numbers and the operation performed.
 These conditions are listed in the first column of Table 10-1. The other columns in
the table show the actual operation to be performed with magnitude of the numbers.
The last column is needed to prevent a negative zero. In other words, when two
equal numbers are subtracted, the result should be +0 not -0.
 Addition (subtraction) algorithm: when the signs of A and B are identical
(different), add the two magnitudes and attach the sign of A to the result.
 When the signs of A and B are different (identical), compare the magnitudes
and subtract the smaller number from the larger. Choose the sign of the result
to be the same as A if A > B or the complement of the sign of A if A < B. If the
two magnitudes are equal, subtract B from A and make the sign of the result
positive.
 Use the terminology given in bracket for subtraction

Hardware Implementation
 To implement the addition and subtraction operations with hardware, it is first
necessary that the two numbers be stored in registers. Let A and B be two
registers that hold the magnitudes of the numbers, and As and Bs be two
flip-flops that hold the corresponding signs. The result of the operation may
be transferred to a third register or to one of the source register (A).

 Figure 10-1 shows a block diagram of the hardware for implementing the
addition and subtraction operations. It consists of registers A and B and
sign flip-flops As and Bs. Subtraction is done by adding A to the 2's
complement of B. The output carry is transferred to flip-flop E, where it
can be checked to determine the relative magnitudes of the two numbers.
The add-overflow flip-flop AVF holds the overflow bit when A and B are
added. The A register provides other micro operations that may be needed
when we specify the sequence of steps in the algorithm.

 The addition of A plus B is done through the parallel adder. The S (sum)
output of the adder is applied to the input of the A register. The complementer
provides an output of B or the complement of B depending on the state of
the mode control M. The complementer consists of Exclusive-OR gates and
parallel adder consists of Full adder circuits.
 The M signal is also applied to the input carry of the adder. When M = 0,
the output of B is transferred to the adder, the input carry is 0, and the
output of the adder is equal to the sum A + B. When M= 1 , the l's
complement of B is applied to the adder, the input carry is 1, and output S
A + B + 1. This is equal to A plus the 2's complement of B, which is
equivalent to the subtraction A – B.
Hardware Algorithm
The flowchart for the hardware al gori t hm is presented in Fig 10-2. The two signs As
and Bs are compared by an exclusive-OR gate. If the output of the gate is 0, the signs are
identical; if it is 1, signs are different.
For an add operation, identical signs dictate that magnitudes be added.
For a subtract operation, different signs dictate that the magnitudes be added.
The magnitudes are added with a micro operation EA=A + B, where EA is a register that
combines E and A. The value of E is transferred into the add-overflow flip-flop AVF.

The two magnitudes are subtracted if the signs are different for an add operation
or identical for a subtract operation. The magnitudes are subtracted by adding A to the
2's complement of B.

No overflow can occur if the numbers are subtracted, so AVF is cleared to 0. A 1 in E

indicates that A >=B and the number in A is the correct result. If this number is zero,
the sign A, must be made positive to avoid a negative zero. A 0 in E indicates that A <B.
For this case it is necessary to take the 2's complement of the value in A. This operation can
be done with one micro operation A=A+1. However, we assume that the A register has
circuits for micro operations complement and increment, so the 2' s complement is
obtained from these two microoperations.
5.1.2 Addition and Subtraction with Signed-2's Complement Data

The leftmost bit of a binary number represents the sign bit: 0 for positive and 1 for negative.
If the sign bit is 1, the entire number is represented in 2' s complement form Thus + 33 is
represented as 00100001and -33 as 11011111.Note that 11011111is the 2's complement of
00100001, and vice versa
 We name the A register AC (accumulator) and the B register BR. The leftmost bit in
AC and BR represent the sign bits of the numbers.
 The two sign bits are added or subtracted together with the other bits in the
complementer and parallel adder
 The overflow flip-flop V is set to 1 if there is an overflow. The output carry in this
case is discarded.

 The sum is obtained by adding the contents of AC and BR (including their sign bits).
 The overflow bit V is set to 1 if the exclusive-OR of the last two carries is 1, and it is
cleared to 0 otherwise.
 The subtraction operation is accomplished by adding the content of AC to the 2's
complement of BR. Taking the 2's complement of BR has the effect of changing a
positive number to negative, and vice versa.
 An overflow must be checked during this operation because the two numbers added
could have the same sign.
 5.2 Multiplication Algorithms

5.2.1 Hardware Implementation for Signed-Magnitude Data (Binary

Multiplier)

 The multiplier is stored in the Q register and its sign in Qs.

 The sequence counter SC is initially set to a number equal to the number
of bits in the multiplier.
 The counter is decremented by 1 after forming each partial product.
 When the content of the counter reaches zero, the product is formed
and the process stops.
 Initially, the multiplicand is in register B and the multiplier in Q.
 The sum of A and B forms a partial product which is transferred to the
EA register. Both partial product and multiplier are shifted to the right
i.e. EAQ is shifted to the right.
 Least significant bit of A is shifted into the most significant position of
Q, the bit from E is shifted into the most significant position of A, and
0 is shifted into E. After the shift, one bit of the partial product is shifted
into Q, pushing the multiplier bits one position to the right. In this
manner, the rightmost flip-flop in register Q, designated by Qn will
hold the bit of the multiplier, which must be inspected next.
Hardware Algorithm

 Initially, the multiplicand is in B and the multiplier in Q. Their corresponding signs

are in Bs and Qs respectively.
 The signs are compared, and both A and Q are set to correspond to the sign of the
product since a double-length product will be stored in registers A and Q.
 Registers A and E are cleared and the sequence counter SC is set to a number equal
to the number of bits of the multiplier. Since we are considering only magnitude SC
is loaded with n-1.
 After the initialization, the low-order bit of the multiplier in Qn is tested.
 If it is a 1, the multiplicand in B is added to the present partial product in A.
 If it is a 0, nothing is done. Register EAQ is then shifted once to the right to form
the new partial product.
 The sequence counter is decremented by 1 and its new value is checked. If it is not
equal to zero, the process is repeated and a new partial product is formed. The
process stops when SC = 0. Note that the partial product formed in A is shifted into
Q one bit at a time and eventually replaces the multiplier.
  The final product is available in both A and Q with A holding the most significant
bits and Q holding the least significant bits.

Numerical Example for Binary Multiplier

5.2.2 Booth Multiplication Algorithm

Booth algorithm gives a procedure for multiplying binary integers in signed-2' s complement
representation.
As in all multiplication schemes, Booth algorithm requires examination of the
multiplier bits and shifting of the partial product. Prior to the shifting, the multiplicand may
be added to the partial product, subtracted from the partial product, or left unchanged
according to the following rules:

1. The multiplicand is subtracted from the partial product upon first least significant 1 in a
string of l's in the multiplier. (Q Qn+1 = 10)
2. The multiplicand is added to the partial product upon the first 0 in a string of 0's in the
multiplier. (Q Qn+1 = 01)
3. The partial product does not change when the multiplier bit is identical to the previous
multiplier bit. (Qn Qn+1 = 00 or 11)
 We rename registers A, B, and Q as AC, BR, and QR respectively.
 Qn designates the least significant bit of the multiplier in register QR.
 An extra flip-flop Qn+1 is appended to QR to facilitate a double bit inspection of
the multiplier.
 AC and the appended bit Qn+l are initially cleared to 0 and the sequence counter SC
is set to a number n equal to the number of bits in the multiplier.
 The two bits of the multiplier in Qn and Qn+1 are inspected.
 If the two bits are equal to 10, it means that the first 1 in a string of l's has
been encountered. This requires a subtraction of the multiplicand from the
partial product in AC.
 If the two bits are equal to 01, it means that the first 0 in a string of 0's has been
encountered. This requires the addition of the multiplicand to the partial product
in AC.
 When the two bits are equal, the partial product does not change. An overflow
cannot occur because the addition and subtraction of the multiplicand follow each
other.
 The next step is to shift right the partial product and the multiplier (including bit
Qn+1)· This is an arithmetic shift right (ashr) operation which shifts AC and QR to
the right and leaves the sign bit in AC unchanged.
5.2.3 Array Multiplier

 To see how an array multiplier can be implemented with a combinational circuit,

consider the multiplication of two 2-bit numbers as shown in Fig. 10-9. The
multiplicand bits are b1 and b0, the multiplier bits are a1 and a0, and the product is
c3 c2 c1 c0.

 The first partial product is formed by multiplying a0 by b1 b0 . The multiplication of

two bits such as a0 and b0 produces a1 if both bits are 1; otherwise, it produces a
0. This is identical to an AND operation and can be implemented with an AND
gate.

 As shown in the diagram, the first partial product is formed by means of two AND
gates. The second partial product is formed by multiplying a1 by b1 b0 and is shifted
one position to the left. The two partial products are added with two half-adder (HA)
circuits.

 Usually, there are more bits in the partial products and it will be necessary to use
full-adders to produce the sum.

In general, for j multiplier bits and k multiplicand bits we need,

 j*k AND gates
 (j-1) k-bit adders
to produce a product of j+k bits.
As a second example, consider a multiplier circuit that multiplies a binary number of
four bits with a number of three bits. . Let the multiplicand be represented by b1,b2,b3,b4
and the multiplier by a2,a1,a0 Since multiplicand bits k= 4 and multiplier bits j= 3, we need
12 AND gates and two 4-bit adders to produce a product of seven bits. The logic diagram of
the multiplier is shown in Fig. 10-10.
 5.3 DIVISION ALGORITHMS

Hardware Implementation for Signed-Magnitude Data

 The hardware for implementing the division operation is identical to that required for
multiplication.
 Register EAQ is shifted to the left with 0 inserted into Q and the previous value of E
lost.
 The divisor is stored in the B register and the double-length dividend is stored in
registers A and Q.
 The dividend is shifted to the left and the divisor is subtracted by adding its 2' s
complement value.
 The information about the relative magnitude is available in E. If E = 1, it signifies
that A>=B. A quotient bit 1 is inserted into Q. and the partial remainder is shifted
to the left to repeat the process.
 If E = 0, it signifies that A < B so the quotient in Q remains a 0 (inserted during the
shift). The value of B is then added to restore the partial remainder in A to its
previous value.
 The partial remainder is shifted to the left and the process is repeated again until
all five quotient bits are formed. Note that while the partial remainder is shifted
left, the quotient bits are also shifted and after five shifts, the quotient is in Q and
the final remainder is in A.
 The hardware divide algorithm is shown in the flowchart of Fig. 10-13. The
dividend is in A and Q and the divisor in B. The sign of the result is transferred into
Qs to be part of the quotient. A constant is set into the sequence counter SC to
specify the number of bits in the quotient.
 Since we are considering only magnitude SC will consist of n -1 bits.
  A divide-overflow condition is tested by subtracting the divisor in B from half of the
bits of the dividend stored in A.
 If A>=B, the divide-overflow flip-flop DVF is set and the operation is terminated
prematurely.
 If A < B, no divide overflow occurs so the value of the dividend is restored by adding
B to A.

 The division of the magnitudes starts by shifting the dividend in AQ to the left with
the high-order bit shifted into E. If the bit shifted into E is 1, we know that EA> B
because EA consists of a 1 followed by n-1 bits while B consists of only n-1 bits.
In this case, B must be subtracted from EA and 1 inserted into Qn for the quotient bit.

 If the shift-left operation inserts a 0 into E, the divisor is subtracted by adding its 2's
complement value and the carry is transferred into E. If E = 1, it signifies that A >= B;
therefore, Qn is set to 1. If E = 0, it signifies that A < B and the original number is
restored by adding B to A. In the latter case we leave a 0 in Q. (0 was inserted during
the shift).
 This process is repeated again with register A holding the partial remainder. After n -
1 times, the quotient magnitude is formed in register Q and the remainder is found in
register A. The quotient sign is in Qs and the sign of the remainder in As is the same
as the original sign of the dividend.

Divide Overflow

• The division operation may result in a quotient with an overflow.

• This is a problem because the length of the register is finite and will not hold a
number that exceeds the standard length.
• When the dividend is twice as long as the divisor the condition for overflow is stated
as follows:
• A divide overflow condition occurs if the higher order half bits of the dividend
constitute a number greater than or equal to the divisor.
• The divide-overflow condition must be avoided in normal computer operations
because the entire quotient will be too long for the memory unit that has a word length
same as registers.
• Another problem associated with division is a division by zero must be avoided.
• Overflow condition is usually detected when a special flip-flop is set called as divide
overflow flip-flop (DVF).
• In some computers it is the responsibility of the programmer to check if DVF is set
after every division instruction. Then it can be branched to a subroutine to take
corrective measure.
• Divide stop – older computers
• In most computers an interrupt request is provided when DVF is set. Computer will
suspend the current program and branch to a service routine to take a corrective
measure.