The Techno-Art Park

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

2011-12-22T15:15:00.001+07:00

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 signiﬁcant full adder to the outputs of the most signiﬁcant full adder.

The process of summing the inputs at each bit position is relatively fast (a small two-level circuit sufﬁces) 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 signiﬁcant ﬁgures in an addition translates to more time to perform the addition.

In this section, we look at a method of speeding the carry propagation in what is known as a carry lookahead adder. In Appendix B, reduced Boolean expressions for the sum (si) and carry outputs (ci+1) of a full adder are created. These expressions are repeated below, with subscripts added to denote the relative position of a full adder in a ripple-carry adder:

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

2011-12-22T04:26:00.004+07:00

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 ﬁxed and ﬂoating 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)

2011-12-22T04:26:00.002+07:00

3.4.2 FLOATING POINT MULTIPLICATION AND DIVISION

Floating point multiplication and division are performed in a manner similar to ﬂoating 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.

Consider using three-bit fractions in performing the base 2 computation: (+.101 × 2²) × (−.110 × 2^-3). The source operand signs differ, which means that the result will have a negative sign. We add exponents for multiplication, and so the exponent of the result is 2 + −3 = −1. We multiply the fractions, which produces the product .01111. Normalizing the product and retaining only three bits in the fraction produces −.111 × 2 ^-2.

Now consider using three-bit fractions in performing the base 2 computation: (+.110 × 2⁵) / (+.100 × 2⁴). The source operand signs are the same, which means that the result will have a positive sign. We subtract exponents for division, and so the exponent of the result is 5 – 4 = 1. We divide fractions, which can be done in a number of ways. If we treat the fractions as unsigned integers, then we will have 110/100 = 1 with a remainder of 10. What we really want is a contiguous set of bits representing the fraction instead of a separate result and remainder,

and so we can scale the dividend to the left by two positions, producing the result: 11000/100 = 110. We then scale the result to the right by two positions to restore the original scale factor, producing 1.1. Putting it all together, the result of dividing (+.110 × 2⁵) by (+.100 × 2⁴) produces (+1.10 × 2¹). After normalization, the ﬁnal result is (+.110 × 2²).

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

2011-10-10T05:35:00.000+07:00

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 scientiﬁc 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 ﬂoating point addition (.101 × 2³ + .111 × 2⁴) in which the fractions have three signiﬁcant digits. We start by adjusting the smaller exponent to be equal to the larger exponent, and adjusting the fraction accordingly.
Thus we have .101 × 2³ = .010 × 2⁴, losing .001 × 2³ of precision in the process. The resulting sum is

(.010 + .111) × 2⁴ = 1.001 × 2⁴ = .1001 × 2⁵,

and rounding to three signiﬁcant digits, .100 × 2⁵, and we have lost another 0.001 × 2⁴ in the rounding process.

Why do ﬂoating point numbers have such complicated formats?
We may wonder why ﬂoating point numbers have such a complicated structure, with the mantissa being stored in signed magnitude representation, the exponent stored in excess notation, and the sign bit separated from the rest of the magnitude by the intervening exponent ﬁeld. There is a simple explanation for this structure. Consider the complexity of performing ﬂoating point arithmetic in a computer. Before any arithmetic can be done, the number must be unpacked from the form it takes in storage. (See Chapter 2 for a description of the IEEE
754 ﬂoating point format.) The exponent and mantissa must be extracted from the packed bit pattern before an arithmetic operation can be performed; after the arithmetic operation(s) are performed, the result must be renormalized and rounded, and then the bit patterns are re-packed into the requisite format.

The virtue of a ﬂoating point format that contains a sign bit followed by an exponent in excess notation, followed by the magnitude of the mantissa, is that two ﬂoating point numbers can be compared for >, <, and = without unpacking.

The sign bit is most important in such a comparison, and it appropriately is the MSB in the ﬂoating point format. Next most important in comparing two numbers is the exponent, since a change of ± 1 in the exponent changes the value by a factor of 2 (for a base 2 format), whereas a change in even the MSB of the fractional part will change the value of the ﬂoating point number by less than that.
In order to account for the sign bit, the signed magnitude fractions are represented as integers and are converted into two’s complement form. After the addition or subtraction operation takes place in two’s complement, there may be a need to normalize the result and adjust the sign bit. The result is then converted back to signed magnitude form.

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

2011-10-10T05:16:00.001+07:00

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

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

2011-09-16T05:59:00.000+07:00

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.

A solution is shown in the right side of Figure 3-16, in which each partial product is extended to the width of the result, and only the rightmost eight bits of the result are retained. If both operands are negative, then the signs are extended for both operands, again retaining only the rightmost eight bits of the result.

Figure 3-15 An example of division using the serial divider.

Figure 3-16 Multiplication of signed integers.

Signed division is more difﬁcult. We will not explore the methods here, but as a general technique, we can convert the operands into their positive forms, perform the division, and then convert the result into its true signed form as a ﬁnal step.

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

2011-09-10T02:17:00.000+07:00

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 “ﬁt” in 0 or 01, but does ﬁt 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 “ﬁt” 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.

In the division algorithm, instead of shifting the product to the right as we did for multiplication, we now shift the quotient to the left, and we subtract instead of adding. When two n-bit unsigned numbers are being divided, the result is no larger than n bits.

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

2011-09-10T02:11:00.000+07:00

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.

Figure 3-10 Multiplication of two unsigned binary integers.

When two signed n-bit numbers are multiplied, the result can be as large as only 2(n-1)+1 = (2n-1) bits, because this is equivalent to multiplying two (n-1)-bit unsigned numbers and then introducing the sign bit.

A hardware implementation of integer multiplication can take a similar form to the manual method. Figure 3-11 shows a layout of a multiplication unit for four-bit numbers, in which there is a four-bit adder, a control unit, three four-bit registers, and a one-bit carry register.

Figure 3-11 A serial multiplier.

In order to multiply two numbers, the multiplicand is placed in the M register, the multiplier is placed in the Q register, and the A and C registers are cleared to zero. During multiplication, the rightmost bit of the multiplier determines whether the multiplicand is added into the product at each step. After the multiplicand is added into the product, the multiplier and the A register are simultaneously shifted to the right. This has the effect of shifting the multiplicand to the left (as for the manual process) and exposing the next bit of the multiplier in position q0.

Figure 3-12 illustrates the multiplication process. Initially, C and A are cleared, and M and Q hold the multiplicand and multiplier, respectively.

Figure 3-12 An example of multiplication using the serial multiplier.

The rightmost bit of Q is 1, and so the multiplier M is added into the product in the A register. The A and Q registers together make up the eight-bit product, but the A register is where the multiplicand is added. After M is added to A, the A and Q registers are shifted to the right. Since the A and Q registers are linked as a pair to form the eight-bit product, the rightmost bit of A is shifted into the leftmost bit of Q.

The rightmost bit of Q is then dropped, C is shifted into the leftmost bit of A, and a 0 is shifted into C.

The process continues for as many steps as there are bits in the multiplier. On the second iteration, the rightmost bit of Q is again 1, and so the multiplicand is added to A and the C/A/Q combination is shifted to the right. On the third iteration, the rightmost bit of Q is 0 so M is not added to A, but the C/A/Q combination is still shifted to the right. Finally, on the fourth iteration, the rightmost bit of Q is again 1, and so M is added to A and the C/A/Q combination is shifted to the right. The product is now contained in the A and Q registers, in which A holds the high-order bits and Q holds the low-order bits.

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

2011-09-07T19:14:00.002+07:00

3.3 Fixed Point Multiplication and Division

Multiplication and division of ﬁxed point numbers can be accomplished with addition, subtraction, and shift operations. The sections that follow describe methods for performing multiplication and division of ﬁxed point numbers in both unsigned and signed forms using these basic operations. We will ﬁrst 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)

2011-09-07T19:05:00.001+07:00

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 signiﬁcant position of the integer portion as shown in Figure 3-7.
This is known as an end-around carry

We can better visualize the reason that the end-around carry is needed by examining the 3-bit one’s complement number circle in Figure 3-8.

Notice that the number circle has two positions for 0. When we add two numbers, if we traverse through both −0 and +0, then we must compensate for the fact that 0 is visited twice. The end-around carry advances the result by one position for this situation.

Notice that the distance between −0 and +0 on the number circle is the distance between two integers, and is not the distance between two successive representable numbers. As an illustration of this point, consider adding (5.5)10 and (−1.0)10 in one’s complement arithmetic, which is shown in Figure 3-9. (Note that we can also treat this as a subtraction problem, in which the subtrahend is negated by complementing all of the bits, before adding it to the minuend.)

In order to add (+5.5)10 and (−1.0)10 and obtain the correct result in one’s complement, we add the end-around carry into the one’s position as shown. This adds complexity to our number circle, because in the gap between +0 and −0, there are valid numbers that represent fractions that are less than 0, yet they appear on the number circle before −0 appears. If the number circle is reordered to avoid this anomaly, then addition must be handled in a more complex manner. The need to look for two different representations for zero, and the potential need to perform another addition for the end-around carry are two important reasons for preferring the two’s complement arithmetic to one’s complement arithmetic.

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

2011-09-07T08:33:00.003+07:00

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.

Figure 3-2 shows a 4-bit ripple-carry adder that is developed in Appendix A. Two binary nnumbers A and B are added from right to left, creating a sum and a carry at the outputs of each full adder for each bit position.

Four 4-bit ripple-carry adders are cascaded in Figure 3-3 to add two 16-bit numbers. The rightmost full adder has a carry-in of 0. Although the rightmost full adder can be simpliﬁed as a result of the carry-in of 0, we will use the more general form and force c0 to 0 in order to simplify subtraction later on.

Subtraction of binary numbers proceeds in a fashion analogous to addition. We can subtract oone number from another by working in a single column at a time,subtracting digits of the subtrahend bi, from the minuend ai, as we move from right to left. As in decimal subtraction, if the subtrahend is larger than the minuend or there is a borrow from a previous digit then a borrow must be propagated to the next most signiﬁcant bit. Figure 3-4 shows the truth table and a “black-box” circuit for subtraction.

Full subtractors can be cascaded to form ripple-borrow subtractors in the same
manner that full adders are cascaded to form ripple-carry adders. Figure 3-5 illustrates a four-bit ripple-borrow subtractor that is made up of four full subtractors.

As discussed above, an alternative method of implementing subtraction is to form the two’s complement negative of the subtrahend and add it to the minuend.

The circuit that is shown in Figure 3-6 performs both addition and subtraction on four-bit two’s complement numbers by allowing the bi inputs to be complemented when subtraction is desired. An ADD/SUBTRACT control line determines which function is performed. The bar over the ADD symbol indicates the ADD operation is active when the signal is low. That is, if the control

line is 0, then the ai and bi inputs are passed through to the adder, and the sum is generated at the si outputs. If the control line is 1, then the ai inputs are passed through to the adder, but the
bi inputs are one’s complemented by the XOR gates before they are passed on to the adder. In order to form the two’s complement negative, we must add 1 to the one’s complement negative, which is accomplished by setting the carry_in line (c0) to 1 with the control input. In this way, we can share the adder hardware among both the adder and the subtractor.

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

2011-07-05T01:47:00.002+07:00

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.

To see why this is the case, consider Figure 3-1. With addition on the real number line, numbers can be as large or as small as desired—the number line goes to ±∞ , so the real number line can accommodate numbers of any size. On the other hand, as discussed in Chapter 2, computers represent data using a ﬁnite number of bits, and as a result can only store numbers within a certain range. For example, an examination of Table 2.1 shows that if we restrict the size of a number to, for example, 3 bits, there will only be eight possible two’s complement values that the number can assume.

In Figure 3-1 these values are arranged in a circle beginning with 000 and proceeding around the circle to 111 and then back to 000.

Figure 3-1 Number circle for 3-bit two’s complement numbers.

The ﬁgure also shows the decimal equivalents of these same numbers. Some experimentation with the number circle shows that numbers can be added or subtracted by traversing the number circle clockwise for addition and counter clockwise for subtraction. Numbers can also be subtracted by two’s complementing the subtrahend and adding. Notice that overﬂow can only occur for addition when the operands (“addend” and “augend”) are of the same sign. Furthermore, overﬂow occurs if a transition is made from +3 to −4 while proceeding around the number circle when adding, or from −4 to +3 while subtracting. (Two’s complement overﬂow is discussed in more detail later in the chapter.)

Here are two examples of 8-bit two’s complement addition, ﬁrst using two positive numbers:

A positive and a negative number can be added in a similar manner:

The carry produced by addition at the highest (leftmost) bit position is discarded in two’s complement addition. A similar situation arises with a carry out of the highest bit position when adding two negative numbers:

The carry out of the leftmost bit is discarded because the number system is modular —it “wraps around” from the largest positive number to the largest negative number as Figure 3-1 shows.

Although an addition operation may have a (discarded) carry-out from the MSB, this does not mean that the result is erroneous. The two examples above yield correct results in spite of the fact that there is a carry-out of the MSB. The next section discusses overﬂow in two’s complement addition in more detail.

Overﬂow

When two numbers are added that have large magnitudes and the same sign, an overﬂow will occur if the result is too large to ﬁt in the number of bits used in the representation. Consider adding (+80)10 and (+50)10 using an eight bit format. The result should be (+130)10, however, as shown below, the result is (−126)10:

This should come as no surprise, since we know that the largest positive 8-bit two’s complement number is +(127)10, and it is therefore impossible to represent (+130)10. Although the result 100000102 “looks” like 13010 if we think of it in unsigned form, the sign bit indicates a negative number in the signed form, which is clearly wrong.

In general, if two numbers of opposite signs are added, then an overﬂow cannot occur. Intuitively, this is because the magnitude of the result can be no larger than the magnitude of the larger operand. This leads us to the deﬁnition of two’s complement overﬂow:

If the numbers being added are of the same sign and the result is of the opposite sign, then an overﬂow occurs and the result is incorrect. If the numbers being added are of opposite signs, then an overﬂow will never occur. As an alternative method of detecting overﬂow for addition, an

overﬂow occurs if and only if the carry into the sign bit differs from the carry out of the sign bit.

If a positive number is subtracted from a negative number and the result is positive, or if a negative number is subtracted from a positive number and the result is negative, then an overﬂow occurs. If the numbers being subtracted are of the same sign, then an overﬂow will never occur.

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

2011-06-30T22:44:00.001+07:00

3.2 FIXED POINT ADDITION AND SUBTRACTION
The addition of binary numbers and the concept of overﬂow were brieﬂy discussed in Chapter 2. Here, we cover addition and subtraction of both signed and unsigned ﬁxed 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 brieﬂy cover operations on 1’s complement and BCD numbers, which have a foundational signiﬁcance 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)

2011-06-30T22:13:00.000+07:00

3.1 OVERVIEW
In the previous chapter we explored a few ways that numbers can be represented in a digital computer, but we only brieﬂy 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 ﬁxed point numbers, and continue with a description of how these four operations can be performed on ﬂoating point numbers.

Some of the largest problems, such as weather calculations, quantum mechanical simulations, and land-use modeling, tax the abilities of even today’s largest computers. Thus the topic of high-performance arithmetic is also important. We conclude the chapter with an introduction to some of the algorithms and techniques used in speeding arithmetic operations.

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

2011-06-30T21:49:00.001+07:00

2.5 CHARACTER CODE
Unlike real numbers, which have an inﬁnite range, there is only a ﬁnite 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.
The representation for each character consists of 7 bits, and all 27 possible bit patterns represent valid characters. The characters in positions 00 – 1F and position 7F are special control characters that are used for transmission, printing control, and other non-textual purposes.
The remaining characters are all printable, and include letters, numbers, punctuation, and a space. The digits 0-9 appear in sequence, as do the upper and lower case letters1. This organization simpliﬁes character manipulation. In order to change the character representation of a digit into its numerical value, we can subtract (30)16 from it. In order to convert the ASCII character ‘5,’ which is in position (35)16, into the number 5, we compute (35 – 30 = 5)16.
(1. As an aside, the character ‘a’ and the character ‘A’ are different, and have different codes
in the ASCII table. The small letters like ‘a’ are called lower case, and the capital letters like ‘A’ are called upper case. The naming comes from the positions of the characters in a printer’s typecase. The capital letters appear above the small letters, which resulted in the upper case / lower case naming. These days, typesetting is almost always performed electronically, but the traditional naming is still used.)

In order to convert an upper case letter into a lower case letter, we add (20)16. For example, to convert the letter ‘H,’ which is at location (48)16 in the ASCII table, into the letter ‘h,’ which is at position (68)16, we compute (48 + 20 = 68)16.

2.5.2 THE EBCDIC CHARACTER SET
A problem with the ASCII code is that only 128 characters can be represented, which is a limitation for many keyboards that have a lot of special characters in addition to upper and lower case letters. The Extended Binary Coded Decimal Interchange Code (EBCDIC) is an eight-bit code that is used extensively in IBM
mainframe computers. Since seven-bit ASCII characters are frequently represented in an eight-bit modiﬁed form (one character per byte), in which a 0 or a 1 is appended to the left of the seven-bit pattern, the use of EBCDIC does not place a greater demand on the storage of characters in a computer. For serial transmission, however, (see Chapter 8), an eight-bit code takes more time to transmit than a seven-bit code, and for this case the wider code does make a difference.
The EBCDIC code is summarized in Figure 2-14. There are gaps in the table, which can be used for application speciﬁc characters. The fact that there are gaps in the upper and lower case sequences is not a major disadvantage because character manipulations can still be done as for ASCII, but using different offsets.

2.5.3 THE UNICODE CHARACTER SET
The ASCII and EBCDIC codes support the historically dominant (Latin) character sets used in computers. There are many more character sets in the world, and a simple ASCII-to-language-X mapping does not work for the general case, and so a new universal character standard was developed that supports a great breadth of the world’s character sets, called Unicode.
Unicode is an evolving standard. It changes as new character sets are introduced into it, and as existing character sets evolve and their representations are reﬁned.
In version 2.0 of the Unicode standard, there are 38,885 distinct coded characters that cover the principal written languages of the Americas, Europe, the Middle East, Africa, India, Asia, and Paciﬁca.
The Unicode Standard uses a 16-bit code set in which there is a one-to-one correspondence between 16-bit codes and characters. Like ASCII, there are no complex modes or escape codes. While Unicode supports many more characters than ASCII or EBCDIC, it is not the end-all standard. In fact, the 16-bit Unicode
standard is a subset of the 32-bit ISO 10646 Universal Character Set (UCS-4).
Glyphs for the ﬁrst 256 Unicode characters are shown in Figure 2-15, according to Unicode version 2.1. Note that the ﬁrst 128 characters are the same as for ASCII.

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

2011-06-29T20:18:00.003+07:00

2.4 Case Study: Patriot Missile Defense Failure Caused by Loss of Precision
During the 1991-1992 Operation Desert Storm conﬂict 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 ﬂoating point number representation.

A radar system operates by sending out a train of electromagnetic pulses in vari ous directions and then listening for return signals that are reﬂected from objects in the path of the radar beam. If an airborne object of interest such as a Scud is detected by the Patriot radar system, then the position of a range gate is determined, which estimates the position of the object being tracked during the next scan.
The range gate also allows information outside of its boundaries to be ﬁltered out, which simpliﬁes tracking. The position of the object (a Scud for this case) is conﬁrmed if it is found within the range gate.

The prediction of where the Scud will next appear is a function of the Scud’s velocity. The Scud’s velocity is determined by its change in position with respect to time, and time is updated in the Patriot’s internal clock in 100 ms intervals.

Velocity is represented as a 24-bit ﬂoating point number, and time is represented as a 24-bit integer, but both must be represented as 24-bit ﬂoating point numbers in order to predict where the Scud will next appear.

The conversion from integer time to real time results in a loss of precision that increases as the internal clock time increases. The error introduced by the conversion results in an error in the range gate calculation, which is proportional to the target’s velocity and the length of time that the system is running. The cause of the Dhahran incident, after the Patriot battery had been operating continuously for over 100 hours, is that the range gate shifted by 687 m, resulting in the failed interception of a Scud.

The conversion problem was known two weeks in advance of the Dhahran incident as a result of data provided by Israel, but it took until the day after the attack for new software to arrive due to the difﬁculty of distributing bug ﬁxes in a wartime environment. A solution to the problem, until a software ﬁx could be made available, would have been to simply reboot the system every few hours which would have the effect of resetting the internal clock. Since ﬁeld personnel were not informed of how long was too long to keep a system running, which was in fact known at the time from data provided by Israel, this solution was never implemented. The lesson for us is to be very aware of the limitations of relying on calculations that use ﬁnite precision

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

2011-04-03T06:02:00.000+07:00

2.3.5 THE IEEE 754 FLOATING POINT STANDARD

There are many ways to represent ﬂoating 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 ﬂoating point calculations, the IEEE 754 ﬂoating 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.

The IEEE 754 standard as described below must be supported by a computer system, and not necessarily by the hardware entirely. That is, a mixture of hardware and software can be used while still conforming to the standard.

2.3.5.1 Formats

There are two primary formats in the IEEE 754 standard: single precision and double precision. Figure 2-10 summarizes the layouts of the two formats. The single precision format occupies 32 bits, whereas the double precision format occupies 64 bits. The double precision format is simply a wider version of the single precision format.

Figure 2-10 Single precision and double precision IEEE 754 floating point formats.

The sign bit is in the leftmost position and indicates a positive or negative number for a 0 or a 1, respectively. The 8-bit excess 127 (not 128) exponent follows, in which the bit patterns 00000000 and 11111111 are reserved for special cases, as described below. For double precision, the 11-bit exponent is represented in excess 1023, with 00000000000 and 11111111111 reserved. The 23-bit base 2 fraction follows. There is a hidden bit to the left of the binary point, which when taken together with the single-precision fraction form a 23 + 1 = 24-bit signiﬁcand of the form 1.fff...f where the fff...f pattern represents the 23-bit fractional part that is stored. The double-precision format also uses a hidden bit to the left of the binary point, which supports a 52 + 1 = 53 bit signiﬁcand. For both formats, the number is normalized unless denormalized numbers are supported, as described later.

There are ﬁve basic types of numbers that can be represented. Nonzero normalized numbers take the form described above. A so-called “clean zero” is represented by the reserved bit pattern 00000000 in the exponent and all 0’s in the fraction. The sign bit can be 0 or 1, and so there are two representations for zero: +0 and −0.

Inﬁnity has a representation in which the exponent contains the reserved bit pattern 11111111, the fraction contains all 0’s, and the sign bit is 0 or 1. Inﬁnity is useful in handling overﬂow situations or in giving a valid representation to a number (other than zero) divided by zero. If zero is divided by zero or inﬁnity is divided by inﬁnity, then the result is undeﬁned. This is represented by the NaN (not a number) format in which the exponent contains the reserved bit pattern 11111111, the fraction is nonzero and the sign bit is 0 or 1. A NaN can also be produced by attempting to take the square root of −1.

As with all normalized representations, there is a large gap between zero and the ﬁrst representable number. The denormalized, “dirty zero” representation allows numbers in this gap to be represented. The sign bit can be 0 or 1, the exponent contains the reserved bit pattern 00000000 which represents −126 for single precision (−1022 for double precision), and the fraction contains the actual bit pattern for the magnitude of the number. Thus, there is no hidden 1 for this format.

Note that the denormalized representation is not an unnormalized representation. The key difference is that there is only one representation for each denormalized number, whereas there are inﬁnitely many unnormalized representations.

Figure 2-11 illustrates some examples of IEEE 754 ﬂoating point numbers.

Figure 2-11 Examples of IEEE 754 floating point numbers in single precision

format (a – h) and double precision format (i). Spaces are shown for

clarity only: they are not part of the representation.

Examples (a) through (h) are in single precision format and example (i) is in double precision format. Example (a) shows an ordinary single precision number.

Notice that the signiﬁcand is 1.101, but that only the fraction (101) is explicitly represented. Example (b) uses the smallest single precision exponent (–126) and example (c) uses the largest single precision exponent (127).

Examples (d) and (e) illustrate the two representations for zero. Example (f ) illustrates the bit pattern for +∞. There is also a corresponding bit pattern for –∞.

Example (g) shows a denormalized number. Notice that although the number itself is 2−128, the smallest representable exponent is still −126. The exponent for single precision denormalized numbers is always −126, which is represented by the bit pattern 00000000 and a nonzero fraction. The fraction represents the magnitude of the number, rather than a signiﬁcand. Thus we have +2−128 = +.01 × 2–126, which is represented by the bit pattern shown in Figure 2-11g.

Example (h) shows a single precision NaN. A NaN can be positive or negative.

Finally, example (i) revisits the representation of 2–128 but now using double precision. The representation is for an ordinary double precision number and so there are no special considerations here. Notice that 2–128 has a signiﬁcand of 1.0, which is why the fraction ﬁeld is all 0’s.

In addition to the single precision and double precision formats, there are also single extended and double extended formats. The extended formats are not visible to the user, but they are used to retain a greater amount of internal precision during calculations to reduce the effects of roundoff errors. The extended formats increase the widths of the exponents and fractions by a number of bits that can vary depending on the implementation. For instance, the single extended format adds at least three bits to the exponent and eight bits to the fraction. The double extended format is typically 80 bits wide, with a 15-bit exponent and a 64-bit fraction.

2.3.5.2 Rounding

An implementation of IEEE 754 must provide at least single precision, whereas the remaining formats are optional. Further, the result of any single operation on ﬂoating point numbers must be accurate to within half a bit in the least signiﬁcant bit of the fraction. This means that some additional bits of precision may need to be retained during computation (referred to as guard bits), and there must be an appropriate method of rounding the intermediate result to the number of bits in the fraction.

There are four rounding modes in the IEEE 754 standard. One mode rounds to 0, another rounds toward +∞, and another rounds toward −∞. The default mode rounds to the nearest representable number. Halfway cases round to the number whose low order digit is even. For example, 1.01101 rounds to 1.0110 whereas 1.01111 rounds to 1.1000.

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

2011-04-03T05:47:00.003+07:00

2.3.4 ERROR IN FLOATING POINT REPRESENTATIONS
The fact that ﬁnite 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 ﬂoating 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.

1 = In order to characterize error, range, and precision, we use the following notation:
b = Base
s = Number of signiﬁcant digits (not bits) in the fraction
M = Largest exponent
m = Smallest exponent

The number of signiﬁcant digits in the fraction is represented by s, which is different than the number of bits in the fraction if the base is anything other than 2 (for example, base 16 uses four bits for each digit). In general, if the base is 2k where k is an integer, then k bits are needed to represent each digit. The use of a hidden 1 increases s by one bit even though it does not increase the number of representable numbers. In the previous example, there are three signiﬁcant digits in the base 16 fraction and there are 12 bits that make up the three digits.

There are three bits in the excess 4 exponent, which gives an exponent range of [−22 to 22 − 1]. For this case, b = 16, s = 3, M = 3, and m = −4.In the analysis of a ﬂoating point representation, there are ﬁve characteristics that we consider: the number of representable numbers, the numbers that have the largest and smallest magnitudes (other than zero), and the sizes of the largest and smallest gaps between successive numbers.

The number of representable numbers can be determined as shown in Figure 2-8. The sign bit can take on two values, as indicated by the position marked with an encircled “A.” The total number of exponents is indicated in position B.

Figure 2-8 Calculation of the number of representable numbers in

a floating point representation.

Note that not all exponent bit patterns are valid in all representations. The IEEE 754 ﬂoating point standard, which we will study shortly, has a smallest exponent of −126 even though the eight-bit exponent can support a number as small as −128. The forbidden exponents are reserved for special numbers, such as zero and inﬁnity.

The ﬁrst digit of the fraction is considered next, which can take on any value except 0 in a normalized representation (except when a hidden 1 is used) as indicated by (b − 1) at position C. The remaining digits of the fraction can take on any of the b values for the base, as indicated by bs-1 at position D. If a hidden 1 is used, then position C is removed and position 4 is replaced with bs

Finally, there must be a representation for 0, which is accounted for in position E. Consider now the numbers with the smallest and largest magnitudes. The number with the smallest magnitude has the smallest exponent and the smallest nonzero normalized fraction. There must be a nonzero value in the ﬁrst digit, and since a 1 is the smallest value we can place there, the smallest fraction is b−1.

The number with the smallest magnitude is then bm·b−1 = bm−1. Similarly, the number with the largest magnitude has the largest exponent and the largest fraction (when the fraction is all 1’s), which is equal to bM ·(1 − b−s ).

The smallest and largest gaps are computed in a similar manner. The smallest gap occurs when the exponent is at its smallest value and the least signiﬁcant bit of the fraction changes. This gap is bm·b−s = bm−s

The largest gap occurs when the exponent is at its largest value and the least signiﬁcant bit of the fraction changes. This gap is bM·b−s = bM−s

As an example, consider a ﬂoating point representation in which there is a sign bit, a two-bit excess 2 exponent, and a three-bit normalized base 2 fraction in which the leading 1 is visible; that is, the leading 1 is not hidden. The representation of 0 is the bit pattern 000000. A number line showing all possible numbers that can be represented in this format is shown in Figure 2-9.

Notice that there is a relatively large gap between 0 and the ﬁrst representable number, because the normalized representation does not support bit patterns that correspond to numbers between 0 and the ﬁrst representable number. The smallest representable number occurs when the exponent and the fraction are at their smallest values. The smallest exponent is −2, and the smallest normalized fraction is (.100)2. The smallest representable number is then bm×b−1 = bm−1 = 2−2−1 = 1/8.

Similarly, the largest representable number occurs when the exponent and the fraction are both at their largest values. The largest fraction occurs when the fraction is all 1’s, which is a number that is 2−3 less than 1 since there are three digits in the fraction. The largest representable number is then bM ×(1 - b−s ) = 21 × (1 - 2−3) = 7/4.

The smallest gap occurs when the exponent is at its smallest value and the least signiﬁcant bit of the fraction changes, which is bm×b−s = bm−s = 2−2−3 = 1/32.

Similarly, the largest gap occurs when the exponent is at its largest value and the least signiﬁcant bit of the fraction changes, which is bM×b−s = bM−s = 21−3 = 1/4.

The number of bit patterns that represent valid numbers is less than the number of possible bit patterns, due to normalization. As discussed earlier, the number of representable numbers consists of ﬁve parts, which take into account the sign bit, the exponents, the ﬁrst signiﬁcant digit, the remaining digits, and the bit pattern for 0. This is computed as shown below:

2 × ((M − m) + 1) × (b − 1) × bs−1 + 1

= 2 × ((1 − (−2)) + 1) × (2 − 1) × 23−1 + 1

= 33.

Notice that the gaps are small for small numbers and that the gaps are large for large numbers. In fact, the relative error is approximately the same for all numbers. If we take the ratio of a large gap to a large number, and compare that to the ratio of a small gap to a small number, then the ratios are the same:

The representation for a “small number” is used here, rather than the smallest number, because the large gap between zero and the ﬁrst representable number is a special case.

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

2011-04-03T05:16:00.001+07:00

2.3.3 REPRESENTING FLOATING POINT NUMBERS IN THE COMPUTER—PRELIMINARIES

Let us design a simple ﬂoating point format to illustrate the important factors in representing oating point numbers on the computer. Our format may at ﬁrst seem to be unnecessarily complex. We will represent the signiﬁcand 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.

The normalized form of the number has the hexadecimal point to the left of the three hexadecimal digits.

The bits will be packed together as follows: The sign bit is on the left, followed by the 3-bit exponent, followed by the three hexadecimal digits of the signiﬁcand. Neither the radix nor the hexadecimal point will be stored in the packed form.

The reason for these rather odd-seeming choices is that numbers in this format can be compared for =, ≠, ≤, and ≥ in their “packed” format, which is shown in the illustration below:

Consider representing (358)10 in this format.

The ﬁrst step is to convert the ﬁxed point number from its original base into a ﬁxed point number in the target base. Using the method described in Section 2.1.3, we convert the base 10 number into a base 16 number as shown below:

Thus (358)10 = (166)16. The next step is to convert the ﬁxed point number into a ﬂoating point number:

(166)16 = (166.)16 × 160

Note that the form 160 reﬂects a base of 16 with an exponent of 0, and that the number 16 as it appears on the page uses a base 10 form. That is, (160)10 = (100)16. This is simply a notational convenience used in describing a ﬂoating point number.

The next step is to normalize the number:

(166.)16 × 160 = (.166)16 × 163

Finally, we ﬁll in the bit ﬁelds of the number. The number is positive, and so we place a 0 in the sign bit position. The exponent is 3, but we represent it in excess 4, so the bit pattern for the exponent is computed as shown below:

Alternatively, we could have simply computed 3 + 4 = 7 in base 10, and then made the equivalent conversion (7)10 = (111)2.

Finally, each of the base 16 digits is represented in binary as 1 = 0001, 6 = 0110, and 6 = 0110. The ﬁnal bit pattern is shown below:

Notice again that the radix point is not explicitly represented in the bit pattern, but its presence is implied. The spaces between digits are for clarity only, and do not suggest that the bits are stored with spaces between them. The bit pattern as stored in a computer’s memory would look like this:

0111000101100110

The use of an excess 4 exponent instead of a two’s complement or a signed magnitude exponent simpliﬁes addition and subtraction of ﬂoating point numbers (which we will cover in detail in Chapter 3). In order to add or subtract two normalized ﬂoating point numbers, the smaller exponent (smaller in degree, not magnitude) must ﬁrst be increased to the larger exponent (this retains the range), which also has the effect of unnormalizing the smaller number. In order to determine which exponent is larger, we only need to treat the bit patterns as unsigned

numbers and then make our comparison. That is, using an excess 4 representation, the smallest exponent is −4, which is represented as 000. The largest exponent is +3, which is represented as 111. The remaining bit patterns for −3, −2, −1, 0, +1, and +2 fall in their respective order as 001, 010, 011, 100, 101, and 110.

Now if we are given the bit pattern shown above for (358)10 along with a description of the ﬂoating point representation, then we can easily determine the number. The sign bit is a 0, which means that the number is positive. The exponent in unsigned form is the number (+7)10, but since we are using excess 4, we must subtract 4 from it, which results in an actual exponent of (+7 − 4 = +3)10.

The fraction is grouped in four-bit hexadecimal digits, which gives a fraction of (.166)16. Putting it all together results in (+.166 × 163)16 = (358)10. Now suppose that only 10 bits are allowed for the fraction in the above example, instead of the 12 bits that group evenly into fours for hexadecimal digits. How does the representation change? One approach might be to round the fraction and adjust the exponent as necessary. Another approach, which we use here, is to simply truncate the least signiﬁcant bits by chopping and avoid making adjustments to the exponent, so that the number we actually represent is:

If we treat the missing bits as 0’s, then this bit pattern represents (.164 × 163)16.This method of truncation produces a biased error, since values of 00, 01, 10, and 11 in the missing bits are all treated as 0, and so the error is in the range from 0 to (.003)16. The bias comes about because the error is not symmetric about 0. We will not explore the bias problem further here, but a more thorough discussion can be found in (Hamacher et al., 1990).

We again stress that whatever the ﬂoating point format is, that it be known to all parties that intend to store or retrieve numbers in that format. The Institute of Electrical and Electronics Engineers (IEEE), has taken the lead in standardizing ﬂoating point formats. The IEEE 754 ﬂoating point format, which is in nearly universal usage, is discussed in Section 2.3.5.

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

2011-04-03T05:01:00.002+07:00

2.3.2 NORMALIZATION, AND THE HIDDEN BIT

A potential problem with representing ﬂoating point numbers is that the same number can be represented in different ways, which makes comparisons and arithmetic operations difﬁcult. 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, ﬂoating 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

normalized one. Unfortunately, the number zero cannot be represented in this scheme, so to represent zero an exception is made. The exception to this rule is that zero is represented as all 0’s in the mantissa.

If the mantissa is represented as a binary, that is, base 2, number, and if the normalization condition is that there is a leading “1” in the normalized mantissa, then there is no need to store that “1” and in fact, most ﬂoating point formats do not store it. Rather, it is “chopped off ” before packing up the number for storage, and it is restored when unpacking the number into exponent and mantissa. This results in having an additional bit of precision on the right of the number, due to removing the bit on the left. This missing bit is referred to as the hidden bit, also known as a hidden 1. For example, if the mantissa in a given format is .11010 after normalization, then the bit pattern that is stored is 1010—the left-most bit is truncated, or hidden. We will see that the IEEE 754 ﬂoating point format uses a hidden bit.

Computer Architecture # 02 : Data Representation: RANGE AND PRECISION IN FLOATING POINT NUMBERS (11)

2011-04-03T05:00:00.001+07:00

2.3.1 RANGE AND PRECISION IN FLOATING POINT NUMBERS

A ﬂoating point representation allows a large range of expressible numbers to be represented in a small number of digits by separating the digits used for precision from the digits used for range. The base 10 ﬂoating point number representing Avogadro’s number is shown below:

+6.023 × 1023

Here, the range is represented by a power of 10, 1023 in this case, and the precision is represented by the digits in the ﬁxed point number, 6.023 in this case. In discussing ﬂoating point numbers, the ﬁxed point part is often referred to as the mantissa,

or signiﬁcand of the number. Thus a ﬂoating point number can be characterized by a triple of numbers: sign, exponent, and signiﬁcand.

The range is determined primarily by the number of digits in the exponent (two digits are used here) and the base to which it is raised (base 10 is used here) and the precision is determined primarily by the number of digits in the signiﬁcand (four digits are used here). Thus the entire number can be represented by a sign and 6 digits, two for the exponent and four for the signiﬁcand. Figure 2-7 shows how the triple of sign, exponent, signiﬁcand, might be formatted in a computer.

Figure 2-7 Representation of a base 10 floating point number.

Notice how the digits are packed together with the sign ﬁrst, followed by the exponent, followed by the signiﬁcand. This ordering will turn out to be helpful in comparing two ﬂoating point numbers. The reader should be aware that the decimal point does not need to be stored with the number as long as the decimal point is always in the same position in the signiﬁcand. (This will be discussed in Section 2.3.2.)

If we need a greater range, and if we are willing to sacriﬁce precision, then we can use just three digits in the fraction and have three digits left for the exponent without increasing the number of digits used in the representation. An alternative method of increasing the range is to increase the base, which has the effect of increasing the precision of the smallest numbers but decreasing the precision of the largest numbers. The range/precision trade-off is a major advantage of using a ﬂoating point representation, but the reduced precision can cause problems, sometimes leading to disaster, an example of which is described in Section 2.4.

Computer Architecture # 02 : Data Representation: Floating Point Numbers (10)

2011-04-03T04:51:00.001+07:00

2.3 Floating Point Numbers

The ﬁxed point number representation, which we explored in Section 2.2, has a ﬁxed position for the radix point, and a ﬁxed number of digits to the left and right of the radix point. A ﬁxed point representation may need a great many digits in order to represent a practical range of numbers. For example, a computer that can represent a number as large as a trillion1 maintains at least 40 bits to the left of the radix point since 240 ≈ 1012. If the same computer needs to represent one trillionth, then 40 bits must also be maintained to the right of the radix point, which results in a total of 80 bits per number.

In practice, much larger numbers and much smaller numbers appear during the course of computation, which places even greater demands on a computer. A great deal of hardware is required in order to store and manipulate numbers with 80 or more bits of precision, and computation proceeds more slowly for a large number of digits than for a small number of digits. Fine precision, however, is generally not needed when large numbers are used, and conversely, large numbers do not generally need to be represented when calculations are made with small numbers. A more efﬁcient computer can be realized when only as much precision is retained as is needed.

Computer Architecture # 02 : Data Representation: BINARY CODED DECIMAL (9)

2011-04-03T04:48:00.001+07:00

2.2.7 BINARY CODED DECIMAL

Numbers can be represented in the base 10 number system while still using a binary encoding. Each base 10 digit occupies four bit positions, which is known as binary coded decimal (BCD). Each BCD digit can take on any of 10 values. There are 24 = 16 possible bit patterns for each base 10 digit, and as a result, six bit patterns are unused for each digit. In Figure 2-6, there are four decimal significant digits, so 104 = 10,000 bit patterns are valid, even though 216 = 65,536 bit patterns are possible with 16 bits.

Figure 2-6 BCD representations of 301 (a) and –301 in nine’s complement (b) and ten’s comple-

ment (c).

Although some bit patterns are unused, the BCD format is commonly used in calculators and in business applications. There are fewer problems in representing terminating base 10 fractions in this format, unlike the base 2 representation. There is no need to convert data that is given at the input in base 10 form (as in a calculator) into an internal base 2 representation, or to convert from an internal representation of base 2 to an output form of base 10.

Performing arithmetic on signed BCD numbers may not be obvious. Although we are accustomed to using a signed magnitude representation in base 10, a different method of representing signed base 10 numbers is used in a computer. In the nine’s complement number system, positive numbers are represented as in ordinary BCD, but the leftmost digit is less than 5 for positive numbers and is 5 or greater for negative numbers. The nine’s complement negative is formed by subtracting each digit from 9. For example, the base 10 number +301 is represented as 0301 (or simply 301) in both nine’s and ten’s complement as shown in Figure 2-6a. The nine’s complement negative is 9698 (Figure 2-6b), which is obtained by subtracting each digit in 0301 from 9.

The ten’s complement negative is formed by adding 1 to the nine’s complement negative, so the ten’s complement representation of −301 is then 9698 + 1 = 9699 as shown in Figure 2-6c. For this example, the positive numbers range from 0 – 4999 and the negative numbers range from 5000 to 9999.

Computer Architecture # 02 : Data Representation : SIGNED FIXED POINT NUMBERS (8)

2011-04-03T04:28:00.001+07:00

2.2.6 SIGNED FIXED POINT NUMBERS
Up to this point we have considered only the representation of unsigned ﬁxed point numbers. The situation is quite different in representing signed ﬁxed point numbers. There are four different ways of representing signed numbers that are commonly used: sign-magnitude, one’s complement, two’s complement, and excess notation. We will cover each in turn, using integers for our examples.

Throughout the discussion, the reader may wish to refer to Table 2.1 which shows for a 3-bit number how the various representations appear.

Table 2.1: 3-bit Integer Representations

Signed Magnitude
The signed magnitude (also referred to as sign and magnitude) representation is most familiar to us as the base 10 number system. A plus or minus sign to the left of a number indicates whether the number is positive or negative as in +1210 or −1210. In the binary signed magnitude representation, the leftmost bit is used for the sign, which takes on a value of 0 or 1 for ‘+’ or ‘−’, respectively. The remaining bits contain the absolute magnitude. Consider representing (+12)10 and (−12)10 in an eight-bit format:

(+12)10 = (00001100)2

(−12)10 = (10001100)2

The negative number is formed by simply changing the sign bit in the positive number from 0 to 1. Notice that there are both positive and negative representations for zero: 00000000 and 10000000.

There are eight bits in this example format, and all bit patterns represent valid numbers, so there are 28 = 256 possible patterns. Only 28 − 1 = 255 different numbers can be represented, however, since +0 and −0 represent the same number. We will make use of the signed magnitude representation when we look at ﬂoating point numbers in Section 2.3.

One’s Complement
The one’s complement operation is trivial to perform: convert all of the 1’s in the number to 0’s, and all of the 0’s to 1’s. See the fourth column in Table 2.1 for examples. We can observe from the table that in the one’s complement representation the leftmost bit is 0 for positive numbers and 1 for negative numbers, as it is for the signed magnitude representation. This negation, changing 1’s to 0’s and changing 0’s to 1’s, is known as complementing the bits. Consider again representing (+12)10 and (−12)10 in an eight-bit format, now using the one’s complement representation:

(+12)10 = (00001100)2

(−12)10 = (11110011)2

Note again that there are representations for both +0 and −0, which are 00000000 and 11111111, respectively. As a result, there are only 28 − 1 = 255 different numbers that can be represented even though there are 28 different bit patterns.

The one’s complement representation is not commonly used. This is at least partly due to the difﬁculty in making comparisons when there are two representations for 0. There is also additional complexity involved in adding numbers, which is discussed further in Chapter 3.

Two’s Complement

The two’s complement is formed in a way similar to forming the one’s complement: complement all of the bits in the number, but then add 1, and if that addition results in a carry-out from the most signiﬁcant bit of the number, discard the carry-out. Examination of the ﬁfth column of Table 2.1 shows that in the two’s complement representation, the leftmost bit is again 0 for positive numbers and is 1 for negative numbers. However, this number format does not have the unfortunate characteristic of signed-magnitude and one’s complement representations: it has only one representation for zero. To see that this is true, consider forming the negative of (+0)10, which has the bit pattern:

(+0)10 = (00000000)2

Forming the one’s complement of (00000000)2 produces (11111111)2 and adding 1 to it yields (00000000)2, thus (−0)10 = (00000000)2. The carry out of the leftmost position is discarded in two’s complement addition (except when detecting an overﬂow condition). Since there is only one representation for 0, and since all bit patterns are valid, there are 28 = 256 different numbers that can be represented.

Consider again representing (+12)10 and (−12)10 in an eight-bit format, this time using the two’s complement representation. Starting with (+12)10 = (00001100)2, complement, or negate the number, producing (11110011)2. Now add 1, producing (11110100)2, and thus (−12)10 = (11110100)2:

(+12)10 = (00001100)2

(−12)10 = (11110100)2

There is an equal number of positive and negative numbers provided zero is considered to be a positive number, which is reasonable because its sign bit is 0. The positive numbers start at 0, but the negative numbers start at −1, and so the magnitude of the most negative number is one greater than the magnitude of the most positive number. The positive number with the largest magnitude is +127, and the negative number with the largest magnitude is −128. There is thus no positive number that can be represented that corresponds to the negative of −128. If we try to form the two’s complement negative of −128, then we will arrive at a negative number, as shown below:

The two’s complement representation is the representation most commonly used in conventional computers, and we will use it throughout the book.

Excess Representation

In the excess or biased representation, the number is treated as unsigned, but is “shifted” in value by subtracting the bias from it. The concept is to assign the smallest numerical bit pattern, all zeros, to the negative of the bias, and assign the remaining numbers in sequence as the bit patterns increase in magnitude. A convenient way to think of an excess representation is that a number is represented. as the sum of its two’s complement form and another number, which is known as the “excess,” or “bias.” Once again, refer to Table 2.1, the rightmost column, for examples.

Consider again representing (+12)10 and (−12)10 in an eight-bit format but now using an excess 128 representation. An excess 128 number is formed by adding 128 to the original number, and then creating the unsigned binary version. For (+12)10, we compute (128 + 12 = 140)10 and produce the bit pattern (10001100)2. For (−12)10, we compute (128 + −12 = 116)10 and produce the bit pattern (01110100)2:

(+12)10 = (10001100)2

(−12)10 = (01110100)2

Note that there is no numerical signiﬁcance to the excess value: it simply has the effect of shifting the representation of the two’s complement numbers. There is only one excess representation for 0, since the excess representation is simply a shifted version of the two’s complement representation. For the previous case, the excess value is chosen to have the same bit pattern as the largest negative number, which has the effect of making the numbers appear in numerically sorted order if the numbers are viewed in an unsigned binary representation.

Thus, the most negative number is (−128)10 = (00000000)2 and the most positive number is (+127)10 = (11111111)2. This representation simpliﬁes making comparisons between numbers, since the bit patterns for negative numbers have numerically smaller values than the bit patterns for positive numbers. This is important for representing the exponents of ﬂoating point numbers, in which exponents of two numbers are compared in order to make them equal for addition and subtraction. We will explore ﬂoating point representations in Section 2.3.

Computer Architecture # 02 : Data Representation : AN EARLY LOOK AT COMPUTER ARITHMETIC(7)

2011-04-03T04:12:00.001+07:00

2.2.5 AN EARLY LOOK AT COMPUTER ARITHMETIC

We will explore computer arithmetic in detail in Chapter 3, but for the moment, we need to learn how to perform simple binary addition because it is used in representing signed binary numbers. Binary addition is performed similar to the way we perform decimal addition by hand, as illustrated in Figure 2-5. Two binary numbers A and B are added from right to left, creating a sum and a carry in each bit position. Since the rightmost bits of A and B can each assume one of two values, four cases must be considered: 0 + 0, 0 + 1, 1 + 0, and 1 + 1, with a carry of 0, as shown in the ﬁgure.

The carry into the rightmost bit position defaults to 0. For the remaining bit positions, the carry into the position can be 0 or 1, so that a total of eight input combinations must be considered as shown in the ﬁgure.

Figure 2-5 Example of binary addition.

Notice that the largest number we can represent using the eight-bit format shown in Figure 2-5 is (11111111)2 = (255)10 and that the smallest number that can be represented is (00000000)2 = (0)10. The bit patterns 11111111 and 00000000 and all of the intermediate bit patterns represent numbers on the closed interval from 0 to 255, which are all positive numbers. Up to this point we have considered only unsigned numbers, but we need to represent signed numbers as well, in which (approximately) one half of the bit patterns is assigned to positive numbers and the other half is assigned to negative numbers. Four common representations for base 2 signed numbers are discussed in the next section.