Computer Architecture # 03 : Arithmetic: HIGH PERFORMANCE ADDITION (13)

3.5.1 HIGH PERFORMANCE ADDITION

The ripple-carry adder that we reviewed in Section 3.2.2  may introduce too much delay into a system. The longest path through the adder is from the inputs of the least significant full adder to the outputs of the most significant full adder.

The process of summing the inputs at each bit position is relatively fast (a small two-level circuit suffices) but the carry propagation takes a long time to work its way through the circuit. In fact, the propagation time is proportional to the number of bits in the operands. This is unfortunate, since more significant figures in an addition translates to more time to perform the addition.

Computer Architecture # 03 : Arithmetic:HIGH PERFORMANCE ARITHMETIC (12)

3.5 HIGH PERFORMANCE ARITHMETIC
For many applications, the speed of arithmetic operations are the bottleneck to performance. Most supercomputers, such as the Cray, the Tera, and the Intel Hypercube are considered “super” because they excel at performing fixed and floating point arithmetic. In this section we discuss a number of ways to improve the speed of addition, subtraction, multiplication, and division.

Computer Architecture # 03 : Arithmetic:FLOATING POINT MULTIPLICATION AND DIVISION (12)

3.4.2 FLOATING POINT MULTIPLICATION AND DIVISION

Floating point multiplication and division are performed in a manner similar to floating point addition and subtraction, except that the sign, exponent, and fraction of the result can be computed separately. If the operands have the same sign, then the sign of the result is positive. Unlike signs produce a negative result. The exponent of the result before normalization is obtained by adding the exponents of the source operands for multiplication, or by subtracting the divisor exponent from the dividend exponent for division. The fractions are multiplied or divided according to the operation, followed by normalization.

Computer Architecture # 03 : Arithmetic: FLOATING POINT ADDITION AND SUBTRACTION (10)

3.4.1 FLOATING POINT ADDITION AND SUBTRACTION
Floating point arithmetic differs from integer arithmetic in that exponents must be handled as well as the magnitudes of the operands. As in ordinary base 10 arithmetic using scientific notation, the exponents of the operands must be made equal for addition and subtraction. The fractions are then added or subtracted as appropriate, and the result is normalized. 
This process of adjusting the fractional part, and also rounding the result can lead to a loss of precision in the result. Consider the unsigned floating point addition (.101 × 2³ + .111 × 2⁴) in which the fractions have three significant digits. We start by adjusting the smaller exponent to be equal to the larger exponent, and adjusting the fraction accordingly.

Computer Architecture # 03 : Arithmetic: FLOATING POINT ARITHMETIC (10)

 3.4 Floating Point Arithmetic
Arithmetic operations on floating point numbers can be carried out using the fixed point arithmetic operations described in the previous sections, with attention given to maintaining aspects of the floating point representation. In the sections that follow, we explore floating point arithmetic in base 2 and base 10, keeping the requirements of the floating point representation in mind.

Computer Architecture # 03 :Arithmetic : SIGNED MULTIPLICATION AND DIVISION (9)

3.3.3 SIGNED MULTIPLICATION AND DIVISION

If we apply the multiplication and division methods described in the previous sections to signed integers, then we will run into some trouble. Consider multiplying −1 by +1 using four-bit words, as shown in the left side of Figure 3-16.

 The eight-bit equivalent of +15 is produced instead of −1. What went wrong is that the sign bit did not get extended to the left of the result. This is not a problem for a positive result because the high order bits default to 0, producing the correct sign bit 0.

Computer Architecture # 03 :Arithmetic : UNSIGNED DIVISION (8)

3.3.2 UNSIGNED DIVISION

In longhand binary division, we must successively attempt to subtract the divisor from the dividend, using the fewest number of bits in the dividend as we can.

Figure 3-13 illustrates this point by showing that (11)2 does not “fit” in 0 or 01, but does fit in 011 as indicated by the pattern 001 that starts the quotient.

Computer-based division of binary integers can be handled similar to the way that binary integer multiplication is carried out, but with the complication that the only way to tell if the dividend does not “fit” is to actually do the subtraction and test if the remainder is negative. If the remainder is negative then the subtraction must be “backed out” by adding the divisor back in, as described below. 

Computer Architecture # 03 :Arithmetic : UNSIGNED MULTIPLICATION (7)

3.3.1 UNSIGNED MULTIPLICATION

Multiplication of unsigned binary integers is handled similar to the way it is carried out by hand for decimal numbers. Figure 3-10 illustrates the multiplication process for two unsigned binary integers. Each bit of the multiplier determines whether or not the multiplicand, shifted left according to the position of the multiplier bit, is added into the product. When two unsigned n-bit numbers are

multiplied, the result can be as large as 2n bits. For the example shown in Figure 3-10, the multiplication of two four-bit operands results in an eight-bit product.

Computer Architecture # 03 :Arithmetic : FIXED POINT MULTIPLICATION AND DIVISION (6)

3.3 Fixed Point Multiplication and Division

Multiplication and division of fixed point numbers can be accomplished with addition, subtraction, and shift operations. The sections that follow describe methods for performing multiplication and division of fixed point numbers in both unsigned and signed forms using these basic operations. We will first cover unsigned multiplication and division, and then we will cover signed multiplication and division.

Computer Architecture # 03 : Arithmetic: ONE’S COMPLEMENT ADDITION AND SUBTRACTION (5)

3.2.3 ONE’S COMPLEMENT ADDITION AND SUBTRACTION

Although it is not heavily used in mainstream computing anymore, the one’s complement representation was used in early computers. 
One’s complement addition is handled somewhat differently from two’s complement addition: the carry out of the leftmost position is not discarded, but is added back into the least significant position of the integer portion as shown in  Figure 3-7. 
This is known as an end-around carry

Computer Architecture # 03 : Arithmetic: HARDWARE IMPLEMENTATION OF ADDERS AND SUBTRACTORS

3.2.2 HARDWARE IMPLEMENTATION OF ADDERS AND SUBTRACTORS

Up until now we have focused on algorithms for addition and subtraction. Now we will take a look at implementations of simple adders and subtractors.

Ripple-Carry Addition and Ripple-Borrow Subtraction

In Appendix A, a design of a four-bit ripple-carry adder is explored. The adder is modeled after the way that we normally perform decimal addition by hand, by summing digits in one column at a time while moving from right to left. In this section, we review the ripple-carry adder, and then take a look at a ripple-borrow subtractor. We then combine the two into a single addition/subtraction unit.

Computer Architecture # 03 : Arithmetic: TWO’S COMPLEMENT ADDITION AND SUBTRACTION (3)

3.2.1 TWO’S COMPLEMENT ADDITION AND SUBTRACTION

In this section, we look at the addition of signed two’s complement numbers. As we explore the addition of signed numbers, we also implicitly cover subtraction as well, as a result of the arithmetic principle:

a - b = a + (−b).

We can negate a number by complementing it (and adding 1, for two’s complement), and so we can perform subtraction by complementing and adding. This results in a savings of hardware because it avoids the need for a hardware subtractor. We will cover this topic in more detail later.  We will need to modify the interpretation that we place on the results of addition when we add two’s complement numbers.

Computer Architecture # 03 : Arithmetic: FIXED POINT ADDITION AND SUBTRACTION (2)

3.2 FIXED POINT ADDITION AND SUBTRACTION
The addition of binary numbers and the concept of overflow were briefly discussed in Chapter 2. Here, we cover addition and subtraction of both signed and unsigned fixed point numbers in detail. Since the two’s complement representation of integers is almost universal in today’s computers, we will focus primarily on two’s complement operations. We will briefly cover operations on 1’s complement and BCD numbers, which have a foundational significance for other areas of computing, such as networking (for 1’s complement addition) and hand-held calculators (for BCD arithmetic.)

Computer Architecture # 03 : Arithmetic: OVERVIEW (1)

3.1 OVERVIEW
In the previous chapter we explored a few ways that numbers can be represented in a digital computer, but we only briefly touched upon arithmetic operations that can be performed on those numbers. In this chapter we cover four basic arithmetic operations: addition, subtraction, multiplication, and division. We begin by describing how these four operations can be performed on fixed point numbers, and continue with a description of how these four operations can be performed on floating point numbers. 

Computer Architecture # 02 : Data Representation: CHARACTER CODE (17)

2.5 CHARACTER CODE
Unlike real numbers, which have an infinite range, there is only a finite number of characters. An entire character set can be represented with a small number of bits per character. Three of the most common character representations, ASCII, EBCDIC, and Unicode, are described here.


2.5.1 THE ASCII CHARACTER SET
The American Standard Code for Information Interchange (ASCII) is summarized in Figure 2-13, using hexadecimal indices.

Computer Architecture # 02 : Data Representation: CASE STUDY: PATRIOT MISSILE DEFENSE FAILURE CAUSED BY LOSS OF PRECISION (16)

2.4 Case Study: Patriot Missile Defense Failure Caused by Loss of Precision
During the 1991-1992 Operation Desert Storm conflict between Coalition forces and Iraq, the Coalition used a military base in Dhahran, Saudi Arabia that was protected by six U.S. Patriot Missile batteries. The Patriot system was originally designed to be mobile and to operate for only a few hours in order to avoid detection.
The Patriot system tracks and intercepts certain types of objects, such as cruise missiles or Scud ballistic missiles, one of which hit a U.S. Army barracks at Dhahran on February 5, 1991, killing 28 Americans. The Patriot system failed to track and intercept the incoming Scud due to a loss of precision in converting integers to a floating point number representation.

Computer Architecture # 02 : Data Representation: THE IEEE 754 FLOATING POINT STANDARD (15)

2.3.5 THE IEEE 754 FLOATING POINT STANDARD

There are many ways to represent floating point numbers, a few of which we have already explored. Each representation has its own characteristics in terms of range, precision, and the number of representable numbers. In an effort to improve software portability and ensure uniform accuracy of floating point calculations, the IEEE 754 floating point standard for binary numbers was developed (IEEE, 1985). 

There are a few entrenched product lines that predate the standard that do not use it, such as the IBM/370, the DEC VAX, and the Cray line, but virtually all new architectures generally provide some level of IEEE 754 support.

Computer Architecture # 02 : Data Representation : ERROR IN FLOATING POINT REPRESENTATIONS (14)

2.3.4 ERROR IN FLOATING POINT REPRESENTATIONS
The fact that finite precision introduces error means that we should consider how great the error is (by “error”, we mean the distance between two adjacent representable numbers), and whether it is acceptable for our application. As an example of a potential pitfall, consider representing one million in floating point, and then subtracting one million 1’s from it. We may still be left with a million if the error is greater than 1.

Computer Architecture # 02 : Data Representation: EPRESENTING FLOATING POINT NUMBERS IN THE COMPUTER—PRELIMINARIES (13)

2.3.3 REPRESENTING FLOATING POINT NUMBERS IN THE COMPUTER—PRELIMINARIES

Let us design a simple floating point format to illustrate the important factors in representing oating point numbers on the computer. Our format may at first seem to be unnecessarily complex. We will represent the significand in signed magnitude format, with a single bit for the sign bit, and three exadecimal digits for the magnitude. The exponent will be a 3-bit excess-4 number, with a radix of 16.

Computer Architecture # 02 : Data Representation: NORMALIZATION, AND THE HIDDEN BIT (12)

2.3.2  NORMALIZATION, AND THE HIDDEN BIT

A potential problem with representing floating point numbers is that the same number can be represented in different ways, which makes comparisons and arithmetic operations difficult. For example, consider the numerically equivalent forms shown below:

3584.1 × 100 = 3.5841 × 103 = .35841 × 104.

In order to avoid multiple representations for the same number, floating point numbers are maintained in normalized form. That is, the radix point is shifted to the left or to the right and the exponent is adjusted accordingly until the radix point is to the left of the leftmost nonzero digit. So the rightmost number above is the