COMPUTER ARITHMETIC: >The algorithm for the floating-points is slightly more complicated and its implementation requires circuits to add and subtract, and to compare the signs and magnitudes of the numbers.
1. Booth Multiplication Algorithm:
>Booth algorithm gives a procedure for multiplying binary integers in signed-2's complement representation. It operates on the fact that a string of 1's in the multiplier from bit weight 2^k to weight 2^m can be treated as 2^(k+1)-2^m.
>For example:
-Binary number 001110 (+14) has a string of 1's from 2^3 to 2^1 (k=3, m=1). The number can be representation as:
+14 = 2^4-2^1 = 16-2
-Therefore, the multiplication M*14, where M is the multiplicand and 14 the multiplier, can be done as:
M*14 = M*(2^4)-M*(2^1)
-Thus the product can be obtained by shifting the binary multiplicand M four times to the left and subtracting M shifted left once.
>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 accoordint to the rules:
1. The multiplicand is subtracted from the partial product upon encountering the first least significant 1 in a string of 1's in the multiplier.
2. The multiplicand is added to the partial product upon encountering the
first 0 (provided that there was a previous 1) in a string of O’s in the multiplier. 3. The partial product does not change when the multiplier bit is identical to the previous multiplier bit.
>The algorithm works for positive or negative multipliers in 2's complement representation. This is because a negative multiplier ends with a string of 1's and the last operation will be a subtraction of the appropriate weight. For eg: -14 is represented in 2's complement as 110010 and is treated as -2^4+2^2-2^1
HARDWARE:
>(FIG 12)
>Initially the multiplicand is in reigster BR and the multiplier in QR. The sum of registers AC and BR form the partial product. Both partial product and multiplier are shifted to the right.
>Q0 designates the least significant bit of the multiplier in register QR. An extra flip-flop Q(-1) is appended to AR to faciliate a double bit inspection of the multiplier.
>The sequence counter 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.
>The two bits of the mulitplier in Q0 and Q(-1) are inspected:
1. If it is 10 ,it means that the first 1 in a string of 1's has been encounteed. This requires subtraction of the multiplicand from the partial prodcut in AC
2. If the two bits are equal to 01, it means that the first 0 in the string of 0's has been encountered. This requies the addition of the multiplicand to the partial product in AC
3. When the two bits are equal, the partial product does not occur
>The next step is to shift right the partial product and the multiplier. This is an arithmetic shift right operation which shifts AC and QR to the right and leaves the sign bit in AC unchanged.
>The sequence counter is decremented and the computational loop is repetead n times.
>(FIG 13)
2. Array Multiplier:
>Checking the bits of the multiplier one at a time and forming partial products is a sequential operation that requires a sequence of add and shift microoperations. The multiplication of two binary numbers can be done with one microoperation by means of a combinational circuit that forms the product bits all at once. This is a fast way of multiplying two numbers since all it takes is the time for the signals to propagate through the gates that form the multiplication array. However, an array multiplier requires a large number of gates, and for this reason it was not economical until the development of integrated circuits.
3. Division: (works for negatives but i dont know how)
>Division of two fixed-point binary numbers in signed-magnitude representation is done by a process of successive compare, shift and subtract operations.
>Example:
-The divisor B consists of five bits (say 10001) and the dividend A (say 0111000000), of ten bits.
-The five most significant bits of the dividend are compared with the divisor. Since the 5-bit number is smaller than B, we try again by taking the six most significant bits of A and compare this number with B. The 6-bit number is greater than B, so we place a 1 for the quotient bit in the sixth position above the dividend. The divisor is then shifted once to the right and subtracted from the dividend. The difference is called a partial remainder because the divison could have stopped here to obtain a quotient of 1 and a remainder equal to the partial remainder. The process is continued by comparing a partial remainder with the divisor. If the partial remainder is greater than or equal to the divisor, the quotient bit is equal to 1 . The divisor is then shifted right and subtracted from the partial remainder. If the partial remainder is smaller than the divisor, the quotient bit is 0 and no subtraction is needed. The divisor is shifted once to the right in any case.
>Hardware:
-The hardware for implementing the division operation is identical to that required for multiplication and consits of the same components. The dividend is in A and Q and the divisor in B. A constant is set into the sequence counter SC to specify the number of bits in the quotient.
-The dividend, or partial remainder, is shifted to the left, thus leaving the two numbers in the required relative position.
-Subtraction is achieved by adding A to the 2's complement of B. The information about the relative magnitudes is then available from the end-carry.
-If E = 1, it signifies that A >= B, a quotient bit 1 is inserted into Q0 and the partial remainder is shifted to the left to repeat the process.
-If E = 0, it signifies that A < B so that quotient in Q0 remains 0 (inserted during the shift).
Restoring: The value of B is then added to restore the partial remainder in A to its previous value.
Non-restoring: B is not added but instead, the negative difference is shifted left and then B is added.
>A divide-overflow condition occurs if the high-order half bits of the dividend constitute a number greater than or equal to the divisor.
>FIG 14, FIG 15
4. Floating-point Addition:
>Arithmetic operations with floating-point numbers are more complicated than the fixed-point numbers and their execution takes longer and requires more complex hardware.
>Adding or subtracting two numbers requries first an alignment of the radix point since the exponent parts must be made equal before adding or subtracting the mantissas. The alignment is done by shifting one mantissa while its exponent is adjusted until it is equal to the other exponent.
>Example:
.5372400 * 10^2
+.1580000 * 10^(-1)
>The usual alignment procedure is to shift the mantissa that has the smaller exponent to the right by a number of places equal to difference between the exponents. After this is done, the mantissas can be added
.5372400 * 10^2
+.0001580 * 10^2
>After the mantissas are added or subtracted, the result may be unormalized. The normalization procedure ensures that the result is normalized prior to its transfer to memory.
>POST NORMALIZATION:
1. Overflow check: If an overflow occurs when the magnitudes are added, it is transferred into a flip-flop O.
If E = Emax, then OverflowError;
Else:
Right shift AC, E = E+1 then END
2. Normalization check: If AC does not require normalization then END
3. Check for zero: If AC = 0, set E = 0 then END
4. Underflow check: If E > Emin then Left shift AC, E = E-1; Goto 2:
>FIG 16