Systems Architecture Assignment

jpFlute

chapter-3.pdf

Home >Computer Science homework help >Systems Architecture Assignment

C H A P T E R 3 DATA REPRESENTATION

C H A P T E R G O A L S

Describe numbering systems and their use in data representation

Compare different data representation methods

Summarize the CPU data types and explain how nonnumeric data is represented

Describe common data structures and their uses

Computers manipulate and store a variety of data, such as numbers, text, sound, and pictures. This

chapter describes how data is represented and stored in computer hardware. It also explains how

simple data types are used as building blocks to create more complex data structures, such as arrays

and records. Understanding data representation is key to understanding hardware and software

technologies.

DATA REPRESENTATION AND PROCESSING

People can understand and manipulate data represented in a variety of forms. For example, they can understand numbers represented symbolically as Arabic numerals (such as 8714), Roman numerals (such as XVII), and simple lines or tick marks on paper (for example, ||| to represent the value 3). They can understand words and concepts represented with pictorial characters ( ) or alphabetic characters ( computer and , Cyrillic text of the Russian word for computer) and in the form of sound waves (spoken words). People also extract data from visual images (photos and movies) and from the senses of taste, smell, and touch. The human brain s processing power and flexibility are evident in the rich variety of data representations it can recognize and understand.

To be manipulated or processed by the brain, external data representations, such as printed text, must be converted to an internal format and transported to the brain s pro- cessing circuitry. Sensory organs convert inputs, such as sight, smell, taste, sound, and skin sensations, into electrical impulses that are transported through the nervous system to the brain. Processing in the brain occurs as networks of neurons exchange data electrically.

Any data and information processor, whether organic, mechanical, electrical, or opti- cal, must be capable of the following:

Recognizing external data and converting it to an internal format Storing and retrieving data internally Transporting data between internal storage and processing components Manipulating data to produce results or decisions

Note that these capabilities correspond roughly to computer system components described in Chapter 2 I/O units, primary and secondary storage, the system bus, and the CPU.

Automated Data Processing Computer systems represent data electrically and process it with electrical switches. Two- state (on and off) electrical switches are well suited for representing data that can be expressed in binary (1 or 0) format, as you see later in Chapter 4. Electrical switches are combined to form processing circuits, which are then combined to form processing sub- systems and entire CPUs. You can see this processing as an equation:

A B C

In this equation, data inputs A and B, represented as electrical currents, are trans- ported through processing circuits (see Figure 3.1). The electrical current emerging from the circuit represents a data output, C. Automated data processing, therefore, combines physics (electronics) and mathematics.

The physical laws of electricity, optics, and quantum mechanics are described by mathematical formulas. If a device s behavior is based on well-defined, mathematically described laws of physics, the device, in theory, can implement a processor to perform the equivalent mathematical function. This relationship between mathematics and physics underlies all automated computation devices, from mechanical clocks (using the

FIGURE 3.1 Two electrical inputs on the left flow through processing circuitry that generates their sum on the right

Courtesy of Course Technology/Cengage Learning

Chapter 3

mathematical ratios of gears) to electronic microprocessors (using the mathematics of electrical voltage and resistance). As you learned in Chapter 2, in quantum mechanics, the mathematical laws are understood but not how to build reliable and cost-effective com- puting devices based on these laws.

Basing computer processing on mathematics and physics has limits, however. Proces- sing operations must be based on mathematical functions, such as addition and equality comparison; use numerical data inputs; and generate numerical outputs. These processing functions are sufficient when a computer performs numeric tasks, such as accounting or statistical analysis. When you ask a computer to perform tasks such as searching text documents and editing sound, pictures, and video, numeric-processing functions do have limitations, but ones that modern software has largely overcome. However, when you want to use a computer to manipulate data with no obvious numeric equivalent for example, literary or philosophical analysis of concepts such as mother, friend, love, and hate numeric-processing functions have major shortcomings. As the data you want to

process moves further away from numbers, applying computer technology to processing the data becomes increasingly difficult and less successful.

Binary Data Representation In a decimal (base 10) number, each digit can have 1 of 10 possible values: 0, 1, 2, 3, 4, 5, 6, 7, 8, or 9. In a binary number, each digit can have only one of two possible values: 0 or 1. Computers represent data with binary numbers for two reasons:

Binary numbers represented as binary electrical signals can be transported reliably between computer systems and their components (discussed in detail in Chapter 8). Binary numbers represented as electrical signals can be processed by two- state electrical devices that are easy to design and fabricate (discussed in detail in Chapter 4).

For computer applications to produce accurate outputs, reliable data transport is important. Given current technology, binary signals and processing devices represent the most cost-efficient tradeoffs between capacity, accuracy, reliability, and cost.

Binary numbers are also well suited to computer processing because they correspond directly with values in Boolean logic. This form of logic is named for 19th-century mathe- matician George Boole, who developed methods of reasoning and logical proof that use sequences of statements that can be evaluated only as true or false. Similarly, a computer can perform logical comparisons of two binary data values to determine whether one data value is greater than, equal to, less than, less than or equal to, not equal to, or greater than or equal to another value. As discussed in Chapter 2, a computer uses this primitive logical capability to exhibit intelligent behavior.

Both computers and humans can combine digits to represent and manipulate larger numbers. Decimal and binary notations are alternative forms of a positional numbering system, in which numeric values are represented as groups, or strings, of digits. The symbol used to represent a digit and the digit s position in a string determine its value. The value of the entire string is the sum of the values of all digits in the string.

Data Representation and Processing

For example, in the decimal numbering system, the number 5689 is interpreted as follows:

5 1000 6 100 8 10 9

5000 600 80 9 5689

The same series of operations can be represented in columnar form, with positions of the same value aligned in columns:

5000 600 80 9

5689

For whole numbers, values are accumulated from right to left. In the preceding exam- ple, the digit 9 is in the first position, 8 is in the second position, 6 is in the third, and 5 is in the fourth.

The maximum value, or weight, of each position is a multiple of the weight of the position to its right. In the decimal numbering system, the first (rightmost) position is the ones (100), and the second position is 10 times the first position (101). The third position is 10 times the second position (102, or 100), the fourth is 10 times the third position (103, or 1000), and so on. In the binary numbering system, each position is 2 times the previous position, so position values for whole numbers are 1, 2, 4, 8, and so forth. The multiplier that describes the difference between one position and the next is the base, or radix, of the numbering system. In the decimal numbering system, it s 10, and in the binary numbering system, it s 2.

The fractional part of a numeric value is separated from the whole part by a period, although in some countries, a comma is used instead of a period. In the decimal number- ing system, the period or comma is called a decimal point. In other numbering systems, the term radix point is used for the period or comma. Here s an example of a decimal value with a radix point:

5689 368

The fractional portion of this real number is .368, and its value is interpreted as follows:

3 10-1 6 10-2 8 10-3

3 1 6 01 8 001

0 3 0 06 0 008 0 368

Proceeding toward the right from the radix point, the weight of each position is a fraction of the position to its left. In the decimal (base 10) numbering system, the first position to the right of the decimal point represents tenths (10-1), the second position represents hundredths (10-2), the third represents thousandths (10-3), and so forth.

Chapter 3

In the binary numbering system, the first position to the right of the radix point represents halves (2-1), the second position represents quarters (2-2), the third represents eighths (2-3), and so forth. As with whole numbers, each position has a weight 10 (or 2) times the position to its right. Table 3.1 compares decimal and binary notations for the values 0 through 10.

The number of digits needed to represent a value depends on the numbering system s base: The number of digits increases as the numbering system s base decreases. Therefore, values that can be represented in a compact format in decimal notation might require lengthy sequences of binary digits. For example, the decimal value 99 requires two decimal digits but seven binary digits. Table 3.2 summarizes the number of binary digits needed to represent decimal values up to 16 positions.

TABLE 3.1 Binary and decimal notations for the values 0 through 10

Binary system (base 2) Decimal system (base 10)

Place 23 22 21 20 103 102 101 100

Values 8 4 2 1 1000 100 10 1

0 0 0 0 5 0 0 0 0

0 0 0 1 5 0 0 0 1

0 0 1 0 5 0 0 0 2

0 0 1 1 5 0 0 0 3

0 1 0 0 5 0 0 0 4

0 1 0 1 5 0 0 0 5

0 1 1 0 5 0 0 0 6

0 1 1 1 5 0 0 0 7

1 0 0 0 5 0 0 0 8

1 0 0 1 5 0 0 0 9

1 0 1 0 5 0 0 1 0

Data Representation and Processing

To convert a binary value to its decimal equivalent, use the following procedure:

1. Determine each position weight by raising 2 to the number of positions left ( ) or right (-) of the radix point.

2. Multiply each digit by its position weight. 3. Sum all the values calculated in Step 2.

N O T E The standard Windows calculator can convert between binary, octal, decimal, and hexadecimal. To open the calculator in Windows 7, click Start, All Programs, Accessories, Calculator. To convert a binary num- ber to decimal, click View, Programmer from the menu (View, Scientific for Vista and earlier Windows versions). Click the Bin (for binary) option button at the upper left, enter the binary number in the text box, and then click the Dec (for decimal) option button.

TABLE 3.2 Binary notations for decimal values up to 16 positions

Number of bits (n) Number of values (2n) Numeric range (decimal)

1 2 0 1

2 4 0 3

3 8 0 7

4 16 0 15

5 32 0 31

6 64 0 63

7 128 0 127

8 256 0 255

9 512 0 511

10 1024 0 1023

11 2048 0 2047

12 4096 0 4095

13 8192 0 8191

14 16,384 0 16,383

15 32,768 0 32,767

16 65,536 0 65,535

Chapter 3

Figure 3.2 shows how the binary number 101101.101 is converted to its decimal equivalent, 45.625.

In computer terminology, each digit of a binary number is called a bit. A group of bits that describe a single data value is called a bit string. The leftmost digit, which has the greatest weight, is called the most significant digit, or high-order bit. Conversely, the rightmost digit is the least significant digit, or low-order bit. A string of 8 bits is called a byte. Generally, a byte is the smallest unit of data that can be read from or written to a storage device.

The following mathematical rules define addition of positive binary digits:

0 0 0 1 0 1 0 1 1 1 1 10

To add two positive binary bit strings, you first must align their radix points as follows:

101101 101 10100 0010

FIGURE 3.2 Computing the decimal equivalent of a binary number Courtesy of Course Technology/Cengage Learning

Data Representation and Processing

The values in each column are added separately, starting with the least significant, or rightmost, digit. If a column result exceeds 1, the excess value must be carried to the next column and added to the values in that column.

N O T E The standard Windows calculator can add and subtract binary integers. To use this feature, click View, Programmer from the menu (View, Scientific for Vista and earlier Windows versions), and click the Bin option button. You can also click View, Digit grouping from the menu to place digits in groups of four for easier readability.

This is the result of adding the two preceding numbers:

1 1 1 1

101101 101 10100 0010

1000001 1100

The result is the same as when adding the values in base-10 notation:

Real Real Binary fractions decimal

101101 101 45 58 45 625 10100 0010 20 18 20 125

1000001 1100 65 34 65 750

Binary numbers usually contain many digits and are difficult for people to remember and manipulate without error. Compilers and interpreters for high-level programming lan- guages, such as C and Java, convert decimal numbers into binary numbers automatically when generating CPU instructions and data values. However, sometimes programmers must deal with binary numbers directly, such as when they program in machine language or for some operating system (OS) utilities. To minimize errors and make dealing with binary numbers easier, numbering systems based on even multiples of 2 are sometimes used. These numbering systems include hexadecimal and octal, discussed in the following sections.

Hexadecimal Notation Hexadecimal numbering uses 16 as its base or radix ( hex 6 and decimal 10). There aren t enough numeric symbols (Arabic numerals) to represent 16 different values, so English letters represent the larger values (see Table 3.3).

Chapter 3

The primary advantage of hexadecimal notation, compared with binary notation, is its compactness. Large numeric values expressed in binary notation require four times as many digits as those expressed in hexadecimal notation. For example, the data content of a byte requires eight binary digits (such as 11110000) but only two hexadecimal digits (such as F0). This compact representation helps reduce programmer error.

Hexadecimal numbers often designate memory addresses. For example, a 64 KB memory region contains 65,536 bytes (64 1024 bytes/KB). Each byte is identified by a sequential numeric address. The first byte is always address 0. Therefore, the range of possible memory addresses is 0 to 65,535 in decimal numbers, 0 to 1111111111111111 in binary numbers, and 0 to FFFF in hexadecimal numbers. As you can see from this exam- ple, hexadecimal addresses are more compact than decimal or binary addresses because of the numbering system s higher radix.

When reading a numeric value in written text, the number s base might not be obvious. For example, when reading an OS error message or a hardware installation manual, should the number 1000 be interpreted in base 2, 10, 16, or something else? In mathematical expressions, the base is usually specified with a subscript, as in this example:

10012

The subscript 2 indicates that 1001 should be interpreted as a binary number. Similarly, in the following example, the subscript 16 indicates that 6044 should be interpreted as a hexadecimal number:

604416

The base of a written number can be made explicit by placing a letter at the end. For example, the letter B in this example indicates a binary number:

1001B

The letter H in this example indicates a hexadecimal number:

6044H

TABLE 3.3 Hexadecimal and decimal values

Base-16 digit Decimal value Base-16 digit Decimal value

0 0 8 8

1 1 9 9

2 2 A 10

3 3 B 11

4 4 C 12

5 5 D 13

6 6 E 14

7 7 F 15

Data Representation and Processing

Normally, no letter is used to indicate a decimal (base 10) number. Some program- ming languages, such as Java and C , use the prefix 0x to indicate a hexadecimal number. For example, 0x1001 is equivalent to 100116.

Unfortunately, these conventions aren t observed consistently. Often it s left to the reader to guess the correct base by the number s content or the context in which it appears. A value containing a numeral other than 0 or 1 can t be binary, for instance. Similarly, the use of letters A through F indicates that the contents are expressed in hexadecimal. Bit strings are usually expressed in binary, and memory addresses are usually expressed in hexadecimal.

Octal Notation Some OSs and machine programming languages use octal notation. Octal notation uses the base-8 numbering system and has a range of digits from 0 to 7. Large numeric values expressed in octal notation are one-third the length of corresponding binary notation and double the length of corresponding hexadecimal notation.

GOALS OF COMPUTER DATA REPRESENTATION

Although all modern computers represent data internally with binary digits, they don t necessarily represent larger numeric values with positional bit strings. Positional number- ing systems are convenient for people to interpret and manipulate because the sequential processing of digits in a string parallels the way the human brain functions and because people are taught to perform computations in a linear fashion. For example, positional numbering systems are well suited to adding and subtracting numbers in columns by using pencil and paper. Computer processors, however, operate differently from a human brain. Data representation tailored to human capabilities and limitations might not be best suited to computers.

Any representation format for numeric data represents a balance among several factors, including the following:

Compactness Range Accuracy Ease of manipulation Standardization

As with many computer design decisions, alternatives that perform well in one factor often perform poorly in others. For example, a data format with a high degree of accuracy and a large range of representable values is usually difficult and expensive to manipulate because it s not compact.

Compactness and Range The term compactness (or size) describes the number of bits used to represent a numeric value. Compact representation formats use fewer bits to represent a value, but they re limited in the range of values they can represent. For example, the largest binary integer that can be stored in 32 bits is 232, or 4,294,967,29610. Halving the number of bits

Chapter 3

to make the representation more compact decreases the largest possible value to 216, or 65,53510.

Computer users and programmers usually prefer a large numeric range. For example, would you be happy if your bank s computer limited your maximum checking account balance to 65,535 pennies? The extra bit positions required to increase the numeric range have a cost, however. Primary and secondary storage devices must be larger and, there- fore, more expensive. Additional and more expensive capacity is required for data trans- mission between devices in a computer system or across computer networks. CPU processing circuitry becomes more complex and expensive as more bit positions are added. The more compact a data representation format, the less expensive it is to implement in computer hardware.

Accuracy Although compact data formats can minimize hardware s complexity and cost, they do so at the expense of accurate data representation. The accuracy, or precision, of representa- tion increases with the number of data bits used.

It s possible for routine calculations to generate quantities too large or too small to be contained in a machine s finite circuitry (that is, in a fixed number of bits). For example, the fraction 1/3 can t be represented accurately in a fixed number of bits because it s a nonterminating fractional quantity (0.333333333 , with an infinite number of 3s). In these cases, the quantities must be manipulated and stored as approximations, and each approximation introduces a degree of error. If approximate results are used as inputs for other computations, errors can be compounded and even result in major errors. For this reason, a program can have no apparent logical flaws yet still produce inaccurate results.

If all data types were represented in the most compact form possible, approximations would introduce unacceptable margins of error. If a large number of bits were allocated to each data value instead, machine efficiency and performance would be sacrificed, and hardware cost would be increased. The best balance in performance and cost can be achieved by using an optimum coding method for each type of data or each type of oper- ation to be performed. Striving for this balance is the main reason for the variety of data representation formats used in modern CPUs.

Ease of Manipulation When discussing computer processing, manipulation refers to executing processor instructions, such as addition, subtraction, and equality comparisons, and ease refers to machine efficiency. A processor s efficiency depends on its complexity (the number of its primitive components and the complexity of the wiring that binds them together). Effi- cient processor circuits perform their functions quickly because of the small number of components and the short distance electricity must travel. More complex devices need more time to perform their functions.

Data representation formats vary in their capability to support efficient processing. For example, most people have more difficulty performing computations with fractions than with decimal numbers. People process the decimal format more efficiently than the fractional format.

Goals of Computer Data Representation

Unfortunately, there s no best representation format for all types of computation operations. For example, representing large numeric values as logarithms simplifies multi- plication and division for people and computers because log A log B log (A B) and log A - log B log (A B). Logarithms complicate other operations, such as addition and subtraction, and they can increase a number s length substantially (for example, log 99 1.9956351945975499153402557777533).

Standardization Data must be communicated between devices in a single computer and to other computers via networks. To ensure correct and efficient data transmission, data formats must be suitable for a wide variety of devices and computers. For this reason, several organizations have created standard data-encoding methods (discussed later in the Character Data section). Adhering to these standards gives computer users the flexibility to combine hardware from different vendors with minimal data communication problems.

CPU DATA TYPES

The CPUs of most modern computers can represent and process at least the following primitive data types:

Integer Real number Character Boolean Memory address

The arrangement and interpretation of bits in a bit string are usually different for each data type. The representation format for each data type balances compactness, range, accuracy, ease of manipulation, and standardization. A CPU can also implement multiple versions of each type to support different types of processing operations.

Integers An integer is a whole number a value that doesn t have a fractional part. For example, the values 2, 3, 9, and 129 are integers, but the value 12.34 is not. Integer data formats can be signed or unsigned. Most CPUs provide an unsigned integer data type, which stores positive integer values as ordinary binary numbers. An unsigned integer s value is always assumed to be positive.

A signed integer uses one bit to represent whether the value is positive or negative. The choice of bit value (0 or 1) to represent the sign (positive or negative) is arbitrary. The sign bit is normally the high-order bit in a numeric data format. In most data formats, it s 1 for a negative number and 0 for a nonnegative number. (Note that 0 is a nonnegative number.)

The sign bit occupies a bit position that would otherwise be available to store part of the data value. Therefore, using a sign bit reduces the largest positive value that can be stored in any fixed number of bit positions. For example, the largest positive value that

Chapter 3

can be stored in an 8-bit unsigned integer is 255, or 28 - 1. If a bit is used for the sign, the largest positive value that can be stored is 127, or 27 - 1.

With unsigned integers, the lowest value that can be represented is always 0. With signed integers, the lowest value that can be represented is the negative of the highest value that can be stored (for example, -127 for 8-bit signed binary).

Excess Notation

One format that can be used to represent signed integers is excess notation, which always uses a fixed number of bits, with the leftmost bit representing the sign. For example, the value 0 is represented by a bit string with 1 in the leftmost digit and 0s in all the other digits. As shown in Table 3.4, all nonnegative values have 1 as the high-order bit, and neg- ative values have 0 in this position. In essence, excess notation divides a range of ordinary binary numbers in half and uses the lower half for negative values and the upper half for nonnegative values.

To represent a specific integer value in excess notation, you must know how many storage bits are to be used, whether the value fits within the numeric range of excess notation for that number of bits, and whether the value to be stored is positive or negative. For any number of bits, the largest and smallest values in excess notation are 2(n-1) - 1 and -2(n-1), where n is the number of available storage bits.

TABLE 3.4 Excess notation

Bit string Decimal value

1111 7

Nonnegative numbers

1110 6

1101 5

1100 4

1011 3

1010 2

1001 1

1000 0

0111 -1

Negative numbers

0110 -2

0101 -3

0100 -4

0011 -5

0010 -6

0001 -7

0000 -8

CPU Data Types

For example, consider storing a signed integer in 8 bits with excess notation. Because the leftmost bit is a sign bit, the largest positive value that can be stored is 27 - 1, or 12710, and the smallest negative value that can be stored is -27, or -12810. The range of positive values appears to be smaller than the range of negative values because 0 is considered a positive (nonnegative) number in excess notation. Attempting to represent larger positive or smaller negative values results in errors because the leftmost (sign) bit might be over- written with an incorrect value.

Now consider how 9 and -9 are represented in 8-bit excess notation. Both values are well within the numeric range limits for 8-bit excess notation. The ordinary binary repre- sentation of 910 in 8 bits is 00001001. Recall that the excess notation representation of 0 is always a leading 1 bit followed by all 0 bits 10000000 for 8-bit excess notation. Because 9 is nine integer values greater than 0, you can calculate the representation of

9 by adding its ordinary binary representation to the excess notation representation of 0 as follows:

10000000 00001001 10001001

To represent negative values, you use a similar method based on subtraction. Because -9 is nine integer values less than 0, you can calculate the representation of -9 by sub- tracting its ordinary binary representation from the excess notation representation of 0 as follows:

10000000 - 00001001 01110111

Twos Complement Notation

In the binary numbering system, the complement of 0 is 1, and the complement of 1 is 0. The complement of a bit string is formed by substituting 0 for all values of 1 and 1 for all values of 0. For example, the complement of 1010 is 0101. This transformation is the basis of twos complement notation. In this notation, nonnegative integer values are represented as ordinary binary values. For example, a twos complement representation of 710 using 4 bits is 0111.

Bit strings for negative integer values are determined by the following transformation:

complement of positive value 1 negative representation

Parentheses are a common mathematical notation for showing a value s complement; for example, if A is a numeric value, (A) represents its complement. In 4-bit twos comple- ment representation, -710 is calculated as follows:

0111 0001

1000 0001

1001 -710

As another example, take a look at the twos complement representation of 3510 and -3510 in 8 bits. The ordinary binary equivalent of 3510 is 00100011, which is also the

Chapter 3

twos complement representation. To determine the twos complement representation of -3510, use the previous formula with 8-bit numbers:

00100011 00000001

11011100 00000001

11011101 -3510

Twos complement notation is awkward for most people, but it s highly compatible with digital electronic circuitry for the following reasons:

The leftmost bit represents the sign. A fixed number of bit positions are used. Only two logic circuits are required to perform addition on single-bit values. Subtraction can be performed as addition of a negative value.

The latter two reasons enable CPU manufacturers to build processors with fewer components than are needed for other integer data formats, which saves money and increases computational speed. For these reasons, all modern CPUs represent and mani- pulate signed integers by using twos complement format.

Range and Overflow

Most modern CPUs use 64 bits to represent a twos complement value and support 32-bit formats for backward compatibility with older software. A 32-bit format is used in the remainder of this book to simplify the discussion and examples. A small positive value, such as 1, occupies 32 bits even though, in theory, only 2 bits are required (one for the value and one for the sign). Although people can deal with numeric values of varying lengths, computer circuitry isn t nearly as flexible. Fixed-width formats enable more efficient processor and data communication circuitry. The additional CPU complexity required to process variable-length data formats results in unacceptably slow performance. Therefore, when small numeric values are stored, the extra bit positions are filled with leading 0s.

The numeric range of a twos complement value is -(2n-1) to (2n-1 - 1), where n is the number of bits used to store the value. The exponent is n-1 because 1 bit is used for the sign. For 32-bit twos complement format, the numeric range is -2,147,483,64810 to 2,147,483,64710. With any fixed-width data storage format, it s possible that the result of a computation will be too large to fit in the format. For example, the Gross Domestic Prod- uct of each U.S. state was less than $2 billion in 2005. Therefore, these values can be represented as 32-bit twos complement integers. Adding these numbers to calculate Gross National Product (GNP), however, yields a sum larger than $2 billion. Therefore, a pro- gram that computes GNP by using 32-bit twos complement values will generate a value that exceeds the format s numeric range. This condition, referred to as overflow, is treated as an error by the CPU. Executing a subtraction instruction can also result in overflow for example, -(231) - 1. Overflow occurs when the absolute value of a computational result contains too many bits to fit into a fixed-width data format.

As with most other aspects of CPU design, data format length is one design factor that needs to be balanced with others. Large formats reduce the chance of overflow by increasing the maximum absolute value that can be represented, but many bits are wasted

CPU Data Types

(padded with leading 0s) when smaller values are stored. If bits were free, there would be no tradeoff. However, extra bits increase processor complexity and storage requirements, which increase computer system cost. A CPU designer chooses a data format width by balancing numeric range, the chance of overflow during program execution, and the complexity, cost, and speed of processing and storage devices.

To avoid overflow and increase accuracy, some computers and programming lan- guages define additional numeric data types called double-precision data formats. A double-precision data format combines two adjacent fixed-length data items to hold a single value. Double-precision integers are sometimes called long integers.

Overflow can also be avoided by careful programming. If a programmer anticipates that overflow is possible, the units of measure for program variables can be made larger. For example, calculations on centimeters could be converted to meters or kilometers, as appropriate.

Real Numbers A real number can contain both whole and fractional components. The fractional portion is represented by digits to the right of the radix point. For example, the following compu- tation uses real number data inputs and generates a real number output:

18 0 4 0 4 5

This is the equivalent computation in binary notation:

10010 100 100 1

Representing a real number in computer circuitry requires some way to separate the value s whole and fractional components (that is, the computer equivalent of a written radix point). A simple way to accomplish this is to define a storage format in which a fixed-length portion of the bit string holds the whole portion and the remainder of the bit string holds the fractional portion. Figure 3.3 shows this format with a sign bit and fixed radix point.

The format in Figure 3.3 is structurally simple because of the radix point s fixed loca- tion. The advantage of this simplicity is simpler and faster CPU processing circuitry.

FIGURE 3.3 A 32-bit storage format for real numbers using a fixed radix point Courtesy of Course Technology/Cengage Learning

Chapter 3

Unfortunately, processing efficiency is gained by limiting numeric range. Although the sample format uses 32 bits, its numeric range is substantially less than 32-bit twos com- plement. Only 16 bits are allocated to the whole portion of the value. Therefore, the larg- est possible whole value is 216 - 1, or 65,535. The remaining bits store the fractional portion of the value, which can never be greater than or equal to 1.

You could increase the format s numeric range by allocating more bits to the whole portion (shifting the radix point in Figure 3.3 to the right). If the format s total size is fixed at 32 bits, however, the reallocation would reduce the number of bits used to store the fractional portion of the value. Reallocating bits from the fractional portion to the whole portion reduces the precision of fractional quantities, which reduces computational accuracy.

Floating-Point Notation

One way of dealing with the tradeoff between range and precision is to abandon the con- cept of a fixed radix point. To represent extremely small (precise) values, move the radix point far to the left. For example, the following value has only a single digit to the left of the radix point:

0 0000000013526473

Similarly, very large values can be represented by moving the radix point far to the right, as in this example:

1352647300000000 0

Note that both examples have the same number of digits. By floating the radix point left or right, the first example trades range of the whole portion for increased fractional precision, and the second example trades fractional precision for increased whole range. Values can be very large or very small (precise) but not both at the same time.

People tend to commit errors when manipulating long strings of digits. To minimize errors, they often write large numbers in a more compact format called scientific notation. In scientific notation, the two preceding numbers shown are represented as 13,526,473 10-16 and 13,526,473 108. Note that the numbering system s base (10) is part of the multiplier. The exponent can be interpreted as the number and direction of positional moves of the radix point, as shown in Figure 3.4. Negative exponents indicate movement to the left, and positive exponents indicate movement to the right.

FIGURE 3.4 Conversion of scientific notation to decimal notation Courtesy of Course Technology/Cengage Learning

CPU Data Types

Real numbers are represented in computers by using floating-point notation, which is similar to scientific notation except that 2 (rather than 10) is the base. A numeric value is derived from a floating-point bit string according to the following formula:

value mantissa 2exponent

The mantissa holds the bits that are interpreted to derive the real number s digits. By convention, the mantissa is assumed to be preceded by a radix point. The exponent value indicates the radix point s position.

Many CPU-specific implementations of floating-point notation are possible. Differences in these implementations can include the length and coding formats of the mantissa and exponent and the radix point s location in the mantissa. Although twos complement can be used to code the exponent, mantissa, or both, other coding formats might offer better design tradeoffs. Before the 1980s, there was little compatibility in floating-point format between different CPUs, which made transporting floating-point data between different computers difficult or impossible.

The Institute of Electrical and Electronics Engineers (IEEE) addressed this problem in standard 754, which defines the following formats for floating-point data:

binary32 32-bit format for base 2 values binary64 64-bit format for base 2 values binary128 128-bit format for base 2 values decimal64 64-bit format for base 10 values decimal128 128-bit format for base 10 values

The binary32 and binary64 formats were specified in the standard s 1985 version and have been adopted by all computer and microprocessor manufacturers. The other three formats were defined in the 2008 version. Computer and microprocessor manufacturers are currently in the process of incorporating these formats into their products, and some products (such as the IBM POWER6 processor) already include some newer formats. For the remainder of this chapter, all references to floating-point representation refer to the binary32 format, unless otherwise specified.

Figure 3.5 shows the binary32 format. The leading sign bit applies to the mantissa, not the exponent, and is 1 if the mantissa is negative. The 8-bit exponent is coded in excess notation (meaning its first bit is a sign bit). The 23-bit mantissa is coded as an ordinary binary number. It s assumed to be preceded by a binary 1 and the radix point. This format extends the mantissa s precision to 24 bits, although only 23 are actually stored.

Chapter 3

Range, Overflow, and Underflow

The number of bits in a floating-point string and the formats of the mantissa and exponent impose limits on the range of values that can be represented. The number of digits in the mantissa determines the number of significant (nonzero) digits in the largest and smallest values that can be represented. The number of digits in the exponent determines the number of possible bit positions to the right or left of the radix point.

Using the number of bits assigned to mantissa and exponent, the largest absolute value of a floating-point value appears to be the following:

1 11111111111111111111111 211111111

Exponents containing all 0s and all 1s, however, represent special data values in the IEEE standards. Therefore, the usable exponent range is reduced, and the decimal range for the entire floating-point value is approximately 10-45 to 1038.

Floating-point numbers with large absolute values have large positive exponents. When overflow occurs, it always occurs in the exponent. Floating-point representation is also subject to a related error condition called underflow. Very small numbers are repre- sented by negative exponents. Underflow occurs when the absolute value of a negative exponent is too large to fit in the bits allocated to store it.

Precision and Truncation

Recall that scientific notation, including floating-point notation, trades numeric range for accuracy. Accuracy is reduced as the number of digits available to store the mantissa is reduced. The 23-bit mantissa used in the binary32 format represents approximately seven decimal digits of precision. However, many useful numbers contain more than seven nonzero decimal digits, such as the decimal equivalent of the fraction 1/3:

1 3 0 33333333

The number of digits to the right of the decimal point is infinite. Only a limited number of mantissa digits are available, however.

Numbers such as 1/3 are stored in floating-point format by truncation. The numeric value is stored in the mantissa, starting with its most significant bit, until all available bits are used. The remaining bits are discarded. An error or approximation occurs any time a floating-point value is truncated. However, the truncated digits are insignificant compared

FIGURE 3.5 IEEE binary32 floating-point format Courtesy of Course Technology/Cengage Learning

CPU Data Types

with the significant, or large, value that s stored. Problems can result when truncated values are used as input to computations. The error introduced by truncation can be magnified when truncated values are used and generate inaccurate results. The error resulting from a long series of computations starting with truncated inputs can be large.

An added difficulty is that more values have nonterminating representations in the binary system than in the decimal system. For example, the fraction 1/10 is nonterminat- ing in binary notation. The representation of this value in floating-point notation is a truncated value, but these problems can usually be avoided with careful programming. In general, programmers reserve binary floating-point calculations for quantities that can vary continuously over wide ranges, such as measurements made by scientific instruments.

When possible, programmers use data types other than binary32 to avoid or minimize the impact of truncation. Most current microprocessors can store and manipulate binary64 values, and support for binary128 is gradually being added. In addition, most programming languages can emulate binary128, decimal64, and decimal128 values, although processing these values is considerably slower than when the microprocessor supports them as hardware data types. Programmers seeking to minimize representation and computation errors should choose the largest floating-point format supported by hardware or software.

Monetary values are particularly sensitive to truncation errors. Most monetary sys- tems have at least one fractional monetary unit, such as pennies fractions of a U.S. dol- lar. Novice programmers sometimes assume that monetary amounts should be stored and manipulated as binary floating-point numbers. Inevitably, truncation errors caused by nonterminating representations of tenths and other fractions occur. Cumulative errors mount when truncated numbers, or approximations, are input in subsequent calculations.

One way to address the problem is to use integer arithmetic for accounting and finan- cial applications. To do so, a programmer stores and manipulates monetary amounts in the smallest possible monetary unit for example, U.S. pennies or Mexican pesos. Small denominations are converted to larger ones only when needed for output, such as printing a dollar amount on a check or account statement.

Although representing and manipulating monetary values as integers provides computa- tional accuracy, this method has limitations. For example, complex formulas for computing interest on loans or investment balances include exponents and division. Intermediate cal- culation results for programs using these formulas can produce fractional quantities unless monetary amounts are scaled to very small units (for example, millionths of a penny).

The decimal64 and decimal128 bit formats defined in the 2008 version of IEEE stan- dard 754 are intended to address the shortcomings of both binary floating-point and inte- ger representation of monetary units. These formats provide accurate representation of decimal values, and the standard specifies rounding methods that can be used instead of truncation to improve computational accuracy. Both formats use the same basic approach as in binary formats a mantissa and an exponent but they encode three decimal digits in each 10-bit group.

Processing Complexity

The difficulty of learning to use scientific and floating-point notation is understandable. These formats are far more complex than integer data formats, and the complexity affects

Chapter 3

both people and computers. Although floating-point formats are optimized for processing efficiency, they still require complex processing circuitry. The simpler twos complement format used for integers requires much less complex circuitry.

The difference in processing circuitry complexity translates to a difference in speed of performing calculations. The magnitude of the difference depends on several factors, including the computation and the exact details of the processing circuitry. As a general rule, simple computational operations, such as addition and subtraction, take at least twice as long with floating-point numbers than with integers. The difference is even greater for operations such as division and exponentiation. For this reason and for reasons of accuracy, careful programmers never use a real number when an integer can be used, particularly for frequently updated data items.

Character Data In their written form, English and many other languages use alphabetic letters, numerals, punctuation marks, and a variety of other special-purpose symbols, such as $ and &. Each symbol is a character. A sequence of characters that forms a meaningful word, phrase, or other useful group is a string. In most programming languages, single characters are sur- rounded by single quotation marks ('c'), and strings are surrounded by double quotation marks ("computer").

Character data can t be represented or processed directly in a computer because computers are designed to process only digital data (bits). It can be represented indirectly by defining a table that assigns a numeric value to each character. For example, the inte- ger values 0 through 9 can be used to represent the characters (numerals)'0' through'9', the uppercase letters'A' through'Z' can be represented as the integer values 10 through 36, and so forth.

A table-based substitution of one set of symbols or values for another is one example of a coding method. All coding methods share several important characteristics, including the following:

All users must use the same coding and decoding methods. The coded values must be capable of being stored or transmitted. A coding method represents a tradeoff among compactness, range, ease of manipulation, accuracy, and standardization.

The following sections describe some common coding methods for character data.

EBCDIC

Extended Binary Coded Decimal Interchange Code (EBCDIC) is a character-coding method developed by IBM in the 1960s and used in all IBM mainframes well into the 2000s. Recent IBM mainframes and mainframe OSs support more recent character-coding methods, but support for EBCDIC is still maintained for backward compatibility. EBCDIC characters are encoded as strings of 8 bits.

ASCII

The American Standard Code for Information Interchange (ASCII), adopted in the United States in the 1970s, is a widely used coding method in data communication. The international

CPU Data Types

equivalent of this coding method is International Alphabet 5 (IA5), an International Organi- zation for Standardization (ISO) standard. Almost all computers and OSs support ASCII, although a gradual migration is in progress to its newer relative, Unicode.

ASCII is a 7-bit format because most computers and peripheral devices transmit data in bytes and because parity checking was used widely in the 1960s to 1980s for detecting transmission errors. Chapter 8 discusses parity checking and other error detection and correction methods. For now, the important characteristic of parity checking is that it requires 1 extra bit per character. Therefore, 1 of every 8 bits isn t part of the data value, leaving only 7 bits for data representation.

The standard ASCII version used for data transfer is sometimes called ASCII-7 to emphasize its 7-bit format. This coding table has 128, or 27, defined characters. Computers that use 8-bit bytes are capable of representing 256, or 28, different characters. In most computers, the ASCII-7 characters are included in an 8-bit character coding table as the first, or lower, 128 table entries. The additional, or upper, 128 entries are defined by the computer manufacturer and typically used for graphical characters, such as line-drawing characters and multinational characters for example, á, ñ, Ö, and . This encoding method is sometimes called ASCII-8. The term is a misnomer, as it implies that the entire table (all 256 entries) is standardized. In fact, only the first 128 entries are defined by the ASCII standard. Table 3.5 shows portions of the ASCII and EBCDIC coding tables.

TABLE 3.5 Partial listing of ASCII and EBCDIC codes

Symbol ASCII EBCDIC

0 0110000 11110000

1 0110001 11110001

2 0110010 11110010

3 0110011 11110011

4 0110100 11110100

5 0110101 11110101

6 0110110 11110110

7 0110111 11110111

8 0111000 11111000

9 0111001 11111001

A 1000001 11000001

B 1000010 11000010

C 1000011 11000011

a 1100001 10000001

b 1100010 10000010

c 1100011 10000011

Chapter 3

Device Control When text is printed or displayed on an output device, often it s format- ted in a particular way. For example, text output to a printer is normally formatted in lines and paragraphs, and a customer record can be displayed onscreen so that it looks like a printed form. Certain text can be highlighted when printed or displayed by using methods such as underlining, bold font, or reversed background and foreground colors.

ASCII defines several device control codes (see Table 3.6) used for text formatting by sending them immediately before or after the characters they modify. Among the simpler codes are carriage return, which moves the print head or insertion point to the beginning of a line; line feed, which moves the print head or insertion point down one line; and bell, which generates a short sound, such as a beep or bell ring. In ASCII, each of these func- tions is assigned a numeric code and a short character name, such as CR for carriage return, LF for line feed, and BEL for bell. In addition, some ASCII device control codes are used to control data transfer. For example, ACK is sent to acknowledge correct receipt of data, and NAK is sent to indicate that an error has been detected.

N O T E The 33 device control codes in the ASCII table occupy the first 32 entries (numbered 0 through 31) and the last entry (number 127).

TABLE 3.6 ASCII control codes

Decimal code Control character Description

000 NUL Null

001 SOH Start of heading

002 STX Start of text

003 ETX End of text

004 EOT End of transmission

005 ENQ Enquiry

006 ACK Acknowledge

007 BEL Bell

008 BS Backspace

009 HT Horizontal tabulation

010 LF Line feed

011 VT Vertical tabulation

012 FF Form feed

013 CR Carriage return

014 SO Shift out

015 SI Shift in

CPU Data Types

Software and Hardware Support Because characters are usually represented in the CPU as unsigned integers, there s little or no need for special character-processing instructions. Instructions that move and copy unsigned integers behave the same whether the content being manipulated is an actual numeric value or an ASCII-encoded character. Similarly, an equality or inequality comparison instruction that works for unsigned inte- gers also works for values representing characters.

The results of nonequality comparisons are less straightforward. The assignment of numeric codes to characters follows a specific order called a collating sequence. A greater- than comparison with two character inputs (for example,'a' less than'z') returns a result based on the numeric comparison of the corresponding ASCII codes that is, whether the numeric code for'a' is less than the numeric code for'z'. If the character set has an order and the coding method follows the order, less-than and greater-than comparisons usually produce expected results.

However, using numeric values to represent characters can produce some unexpected or unplanned results. For example, the collating sequence of letters and numerals in ASCII follows the standard alphabetic order for letters and numeric order for numerals, but uppercase and lowercase letters are represented by different codes. As a result, an equality comparison between uppercase and lowercase versions of the same letter returns false because the numeric codes aren t identical. For example,'a' doesn t equal'A', as shown

TABLE 3.6 ASCII control codes (continued)

Decimal code Control character Description

016 DLE Data link escape

017 DC1 Device control 1

018 DC2 Device control 2

019 DC3 Device control 3

020 DC4 Device control 4

021 NAK Negative acknowledge

022 SYN Synchronous idle

023 ETB End of transmission block

024 CAN Cancel

025 EM End of medium

026 SUB Substitute

027 ESC Escape

028 FS File separator

029 GS Group separator

030 RS Record separator

031 US Unit separator

127 DEL Delete

Chapter 3

previously in Table 3.5. Punctuation symbols also have a specific order in the collating sequence, although there s no widely accepted ordering for them.

ASCII Limitations ASCII s designers couldn t foresee the code s long lifetime (almost 50 years) or the revolutions in I/O device technologies that would take place. They never envisioned modern I/O device characteristics, such as color, bitmapped graphics, and selectable fonts. Unfortunately, ASCII doesn t have the range to define enough control codes to account for all the formatting and display capabilities in modern I/O devices.

ASCII is also an English-based coding method. This isn t surprising, given that when it was defined, the United States accounted for most computer use and almost all computer production. ASCII has a heavy bias toward Western languages in general and American English in particular, which became a major limitation as computer use and production proliferated worldwide.

Recall that 7-bit ASCII has only 128 table entries, 33 of which are used for device control. Only 95 printable characters can be represented, which are enough for a usable subset of the characters commonly used in American English text. This subset, however, doesn t include any modified Latin characters, such as ç and á, or those from other alphabets, such as .

The ISO partially addressed this problem by defining many different 256-entry tables based on the ASCII model. One, called Latin-1, contains the ASCII-7 characters in the lower 128 table entries and most of the characters used by Western European languages in the upper 128 table entries. The upper 128 entries are sometimes called multinational characters. The number of available character codes in a 256-entry table, however, is still much too small to represent the full range of printable characters in world languages.

Further complicating matters is that some printed languages aren t based on charac- ters in the Western sense. Chinese, Japanese, and Korean written text consists of ideo- graphs, which are pictorial representations of words or concepts. Ideographs are composed of graphical elements, sometimes called strokes, that number in the thousands. Other written languages, such as Arabic, present similar, although less severe, coding problems.

Unicode

The Unicode Consortium (www.unicode.org) was founded in 1991 to develop a multilin- gual character-encoding standard encompassing all written languages. The original mem- bers were Apple Computer Corporation and Xerox Corporation, but many computer companies soon joined. This effort has enabled software and data to cross international boundaries. Major Unicode standard releases are coordinated with ISO standard 10646. As of this writing, the latest standard is Unicode 5.2, published in October 2009.

Like ASCII, Unicode is a coding table that assigns nonnegative integers to represent printable characters. The ISO Latin-1 standard, which includes ASCII-7, is incorporated into Unicode as the first 256 table entries. Therefore, ASCII is a subset of Unicode. An important difference between ASCII and Unicode is the size of the coding table. Early versions of Unicode used 16-bit code, which provided 65,536 table entries numbered 0 through 65,535. As development efforts proceeded, the number of characters exceeded the capacity of a 16-bit code. Later Unicode versions use 16-bit or 32-bit codes, and the standard currently encompasses more than 100,000 characters.

The additional table entries are used primarily for characters, strokes, and ideographs of languages other than English and its Western European siblings. Unicode includes many other alphabets, such as Arabic, Cyrillic, and Hebrew, and thousands of Chinese,

CPU Data Types

Japanese, and Korean ideographs and characters. Some extensions to ASCII device control codes are also provided. As currently defined, Unicode can represent written text from all modern languages. Approximately 6000 characters are reserved for private use.

Unicode is widely supported in modern software, including most OSs and word- processing applications. Because most CPUs support characters encoded in 32-bit unsigned integers, there s no need to upgrade processor hardware to support Unicode. The main impact of Unicode on hardware is in storage and I/O devices. Because the numeric code s size is quadruple that of ASCII, pure text files are four times as large. This increased size seems to be a problem at first glance, but the impact is reduced with custom word-processing file formats and the ever-declining cost of secondary storage. In addition, most documents aren t stored as ASCII or Unicode text files. Instead, they re stored in a format that intermixes text and formatting commands. Because formatting commands also occupy file space, the file size increase caused by switching from ASCII to Unicode is generally less than implied by quadrupling per- character storage.

Before Unicode, devices designed for character I/O used ASCII by default and vendor- specific methods or older ISO standards to process character sets other than Latin-1. The typical method was to maintain an internal set of alternative coding tables, with each table containing a different alphabet or character set. Device-specific commands switched from one table to another. Unicode unifies and standardizes the content of these tables to pro- vide a standardized method for processing international character sets. This standard has been widely adopted by I/O device manufacturers. In addition, backward compatibility with ASCII is ensured because Unicode includes ASCII.

Boolean Data The Boolean data type has only two data values true and false. Most people don t think of Boolean values as data items, but the primitive nature of CPU processing requires the capability to store and manipulate Boolean values. Recall that processing circuitry physi- cally transforms input signals into output signals. If the input signals represent numbers and the processor is performing a computational function, such as addition, the output signal represents the numerical result.

When the processing function is a comparison operation, such as greater than or equal to, the output signal represents a Boolean result of true or false. This result is stored in a register (as is any other processing result) and can be used by other instructions as input (for example, a conditional or an unconditional branch in a program). The Boolean data type is potentially the most concise coding format because only a single bit is required. For example, binary 1 can represent true, and 0 can represent false. To simplify processor design and implementation, most CPU designers seek to minimize the number of different coding formats used. CPUs generally use an integer coding format for integers to represent Boolean values. When coded in this manner, the integer value zero corresponds to false, and all nonzero values correspond to true.

To conserve memory and storage, sometimes programmers pack many Boolean values into a single integer by using each bit to represent a separate Boolean value. Although this method conserves memory, generally it slows program execution because of the complicated instructions required to extract and interpret separate bits from an integer data item.

Chapter 3

Memory Addresses As described in Chapter 2, primary storage is a series of contiguous bytes of storage. Con- ceptually, each memory byte has a unique identifying or serial number. The identifying numbers are called addresses, and their values start with zero and continue in sequence (with no gaps) until the last byte of memory is addressed.

In some CPUs, this conceptual view is also the physical method of identifying and accessing memory locations. That is, memory bytes are identified by a series of nonnega- tive integers. This approach to assigning memory addresses is called a flat memory model. In CPUs using a flat memory model, using twos complement or unsigned binary as the coding format for memory addresses is logical and typical. The advantage of this approach is that it minimizes the number of different data types and the complexity of processor circuitry.

To maintain backward compatibility with earlier generations of CPUs that don t use a flat memory model, some CPU designers choose not to use simple integers as memory addresses. For example, Intel Core CPUs maintain backward compatibility with the 8086 CPU used in the first IBM PC. Earlier generations of processors typically used a different approach to memory addressing called a segmented memory model, in which primary storage is divided into equal-sized (for example, 64 KB) segments called pages. Pages are identified by sequential nonnegative integers. Each byte in a page is also identified by a sequentially assigned nonnegative integer. Each byte of memory has a two-part address: The first part identifies the page, and the second part identifies the byte in the page.

Because a segmented memory address contains two integer values, the data-coding method for single signed or unsigned integers can t be used. Instead, a specific coding for- mat for memory addresses must be defined and used. For this reason, CPUs with seg- mented memory models have an extra data type, or coding format, for storing memory addresses.

T E C H N O L O G Y F O C U S

Intel Memory Address Formats

Intel microprocessors have been used in PCs since 1981. The original IBM PC used an Intel 8086 microprocessor. All later generations of Intel processors (the 80x86, Pentium, and Core processor families) have maintained backward compatibility with the 8086 and can execute CPU instructions designed for the 8086. Backward compatibility has been considered an essential ingredient in the success of PCs based on Intel CPUs.

Early Intel microprocessors were designed and implemented with speed of processor operation as a primary goal. Because a general-purpose CPU uses memory addresses in nearly every instruction execution cycle, making memory access as efficient as possible is important. Processor complexity rises with the number of bits that must be processed simultaneously. Large coding formats for memory addresses and other data types require complicated and slow processing circuitry. Intel designers wanted to minimize the com- plexity of processor circuitry associated with memory addresses. They also needed to balance the desire for efficient memory processing with the need to maintain a large

(continued)

CPU Data Types

range of possible memory addresses. To achieve this balance, they made two major design decisions for the 8086:

A 20-bit size for memory addresses A segmented memory model

The 20-bit address format limited usable (addressable) memory to 1 MB (220

addressable bytes). This limitation didn t seem like a major one because few computers (including most mainframes) had that much memory at the time. The 20-bit format is divided into two parts: a 4-bit segment identifier and a 16-bit segment offset. The 16-bit segment offset identifies a specific byte in a 64 (216) KB memory segment. Because 4 bits are used to represent the segment, there are 16, or 24, possible segments.

Intel designers anticipated that most programs would fit in a single 64 KB memory segment. Further, they knew that 16-bit memory addresses could be processed more efficiently than larger addresses. Therefore, they defined two types of address-processing functions those using the 4-bit segment portion of the address and those ignoring it. When the segment identifier was used, memory access was slow, but it was much faster when the processor ignored the segment identifier. Intel designers assumed that most memory accesses wouldn t require the segment identifier.

Both the 64 KB segment size and the 1 MB memory limit soon became significant constraints. Although early programs for the IBM PC were generally smaller than 64 KB, later versions of these programs were larger. Because the processor design imposed a performance penalty when the segment identifier was used, later versions ran more slowly than earlier versions did. In addition, both the OS and the computer hardware were becoming more complex and consuming more memory resources. As a result, computer designers, OS developers, and users chafed under the 1 MB memory limit.

Intel designers first addressed these constraints in the 80286 by increasing the seg- ment identifier to 8 bits, thus increasing total addressable memory to 16 MB. The 80386 went a step further by providing two methods of addressing. The first, called real mode, was compatible with the 8086 s addressing method. The second, called protected mode, was a new method based on 32-bit memory addresses. Protected-mode addressing elimi- nated the performance penalty for programs larger than 64 KB. Pentium and Core microprocessors continue to use both addressing methods.

The 32-bit protected-mode addresses are adequate for physical memory up to 4 GB. By the late 1990s and 2000s, larger computer classes were reaching this limit, and PCs and workstations were expected to follow in a decade. Intel expanded protected-mode memory addresses to 64 bits beginning in the mid-2000s. The change was far less dis- ruptive than earlier changes because addresses of both sizes use the flat memory model. Nonetheless, users have encountered some bumps in the road as software manufacturers shifted from 32-bit to 64-bit addressing.

This discussion, and the earlier discussion of ASCII, illustrates a few pitfalls for computer designers in choosing data representation methods and formats. A fundamental characteristic of any data representation method is that it involves balancing several variables. For Intel memory addresses, designers had to balance processor cost, speed of program execution, and memory requirements of typical PC software. The balance might have been optimal, or at least reasonable, given the state of these variables in 1981, but neither time nor technology stands still. The outcome of any CPU design decision, including data representation formats, is affected quickly as technology changes. Attempts to maintain backward compatibility with previous CPU designs can be difficult and expensive and might severely limit future design choices.

Chapter 3

DATA STRUCTURES

The previous sections outlined the data types that a CPU can manipulate directly: integer, real number, character, Boolean, and memory address. The data types a CPU supports are sometimes called primitive data types or machine data types. Computers can also process more complex data, such as strings, arrays, text files, databases, and digital representa- tions of audio and image data, such as MP3, JPEG, and MPEG files. Chapter 7 discusses audio and image data representations and related hardware devices. The remainder of this chapter concentrates on other complex data formats commonly manipulated by system and application software.

If only primitive data types were available, developing programs of any kind would be difficult. Most application programs need to combine primitive data items to form useful aggregations. A common example is a character or text string. Most application programs define and use character strings, but few CPUs provide instructions that manipulate them directly. Application development is simplified if character strings can be defined and manipulated (that is, read, written, and compared) as a single unit instead of one charac- ter at a time.

A data structure is a related group of primitive data elements organized for some type of common processing and is defined and manipulated in software. Computer hardware can t manipulate data structures directly; it must deal with them in terms of their primi- tive components, such as integers, floating-point numbers, single characters, and so on. Software must translate operations on data structures into equivalent machine instruc- tions that operate on each primitive data element. For example, Figure 3.6 shows a com- parison of two strings decomposed into comparison operations on each character.

Data Structures

The complexity of data structures is limited only by programmers imagination and skill. As a practical matter, certain data structures are useful in a wide variety of situa- tions and are used commonly, such as character strings or arrays, records, and files. Sys- tem software often provides application services to manipulate these commonly used data structures. For example, an OS normally provides services for reading from and writing to files.

Other data structures are less commonly supported by system software. Examples include numeric arrays, indexed files, and complex database structures. Indexed files are supported in some, but not all, OSs. Numeric arrays are supported in most programming languages but not in most OSs. Database structures are normally supported by a database management system. Most programming languages support direct manipulation of charac- ter strings.

Data structures have an important role in system software development. For example, OSs commonly use linked lists to keep track of memory blocks allocated to programs and disk blocks allocated to files and directories. Indexes are widely used in database

FIGURE 3.6 Software decomposes operations on data structures into operations on primitive data elements

Courtesy of Course Technology/Cengage Learning

Chapter 3

management systems to speed search and retrieval operations. Programmers who develop system software generally take an entire course in data structures and efficient methods for manipulating them.

Pointers and Addresses Whether implemented in system or application software, almost all data structures make extensive use of pointers and addresses. A pointer is a data element containing the address of another data element. An address is the location of a data element in a storage device. Addresses vary in content and representation, depending on the storage device being addressed. Secondary storage devices are normally organized as a sequence of data blocks. A block is a group of bytes read or written as a unit. For example, disk drives usu- ally read and write data in 512-byte blocks. For block-oriented storage devices, an address can be represented as an integer containing the block s sequential position. Integers can also be used to represent the address of a single byte in a block.

As discussed in the previous Technology Focus, memory addresses can be complex if a segmented memory model is used. For the purpose of discussing data structures, a flat memory model is used, and memory addresses are represented by nonnegative integers.

Arrays and Lists Many types of data can be grouped into lists. A list is a set of related data values. In math- ematics, a list is considered unordered, so no specific list element is designated as first, second, last, and so on. When writing software, a programmer usually prefers to impose some ordering on the list. For example, a list of days of the week can be ordered sequen- tially, starting with Monday.

An array is an ordered list in which each element can be referenced by an index to its position. Figure 3.7 shows an example of an array for the first five letters of the English alphabet. Note that the index values are numbered starting at 0, a common (although not universal) practice in programming. Although the index values are shown in Figure 3.7, they aren t stored. Instead, they re inferred from the data value s location in the storage allocated to the array. In a high-level programming language, array elements are normally referenced by the array name and the index value. For example, the third letter of the alphabet stored in an array might be referenced as follows:

alphabet 2

In this example, alphabet is the array name, and 2 is the index value (with number- ing starting from 0).

Data Structures

Figure 3.8 shows a character array, or string, stored sequentially in contiguous mem- ory locations. In this example, each character of the name John Doe is stored in a single byte of memory, and the characters are ordered in sequential byte locations starting at byte 1000. An equivalent organization can be used to store the name on a secondary stor- age device. The address of an array element can be calculated with the starting address of the array and the element s index. For example, if you want to retrieve the third character in the array, you can compute its address as the sum of the first element s address plus the index value, assuming index values start at 0.

Using contiguous storage locations, especially in secondary storage devices, compli- cates the allocation of storage locations. For example, adding new elements to the end of an array might be difficult if these storage locations are already allocated to other data items. For this reason, contiguous storage allocation is generally used only for fixed-length arrays.

For a variety of reasons, you might need to store array elements in widely dispersed storage locations. A linked list is a data structure that uses pointers so that list elements can be scattered among nonsequential storage locations. Figure 3.9 shows a generic exam- ple of a singly linked list. Each list element occupies two storage locations: The first holds the list element s data value, and the second holds the address of the next list element as a pointer.

FIGURE 3.7 Array elements in contiguous storage locations Courtesy of Course Technology/Cengage Learning

FIGURE 3.8 A character array in contiguous storage locations Courtesy of Course Technology/Cengage Learning

Chapter 3

Figure 3.10 shows a character string stored in a linked list. Note that characters are scattered among nonsequential, or noncontiguous, storage locations.

More storage locations are required for a linked list than for an array with equivalent content because both data and pointers must be stored. Using pointers also complicates the task of locating array elements. References to specific array elements must be resolved by following the chain of pointers, starting with the first array element. This method can be inefficient if the array contains a large number of elements. For example, accessing the 1000th element means reading and following pointers in the first 999 elements.

FIGURE 3.9 Value and pointer fields of a singly linked list Courtesy of Course Technology/Cengage Learning

FIGURE 3.10 A character array stored in noncontiguous memory locations, with pointers connecting the array elements

Courtesy of Course Technology/Cengage Learning

Data Structures

Linked lists are easier to expand or shrink than arrays are. The procedure for adding a new element is as follows (see Figure 3.11):

1. Allocate storage for the new element. 2. Copy the pointer from the element preceding the new element to the pointer

field of the new element. 3. Write the address of the new element in the preceding element s pointer

field.

In contrast, inserting an element in a list stored in contiguous memory can be time consuming. The procedure is as follows (see Figure 3.12):

1. Allocate a new storage location at the end of the list. 2. For each element past the insertion point, copy its value to the next storage

location, starting with the last element and working backward to the insertion point.

3. Write the new element s value in the storage location at the insertion point.

Inserting an element near the beginning of the array is highly inefficient because of the many required copy operations.

FIGURE 3.11 Inserting a new element in a singly linked list Courtesy of Course Technology/Cengage Learning

Chapter 3

Figure 3.13 depicts a more complicated linked list called a doubly linked list. Each element of a doubly linked list has two pointers: one pointing to the next element in the list and one pointing to the previous element in the list. The main advantage of doubly linked lists is that they can be traversed in either direction with equal efficiency. The dis- advantages are that more pointers must be updated each time an element is inserted into or deleted from the list, and more storage locations are required to hold the extra pointers.

FIGURE 3.12 Inserting a new element in an array stored in contiguous memory locations Courtesy of Course Technology/Cengage Learning

FIGURE 3.13 A doubly linked list Courtesy of Course Technology/Cengage Learning

Data Structures

Records and Files A record is a data structure composed of other data structures or primitive data elements. Records are commonly used as a unit of input and output to and from files or databases. For example, the following data items might be the contents of the data structure for a customer record (see Figure 3.14):

Account-Number Street-Address Last-Name City First-Name State Middle-Initial Zip-Code

Each component of the record is a basic data element (for example, Middle-Initial) or another data structure (for example, a character array for Street-Address). To speed input and output, records are usually stored in contiguous storage locations, which restricts the record s array components to a fixed length.

A sequence of records on secondary storage is called a file. A sequence of records stored in main memory is normally called a table, although its structure is essentially the same as a file. Files can be organized in many different ways, the most common being sequential and indexed.

In a sequential file, records are stored in contiguous storage locations. As with arrays stored in contiguous storage, accessing a specific record is simple. The address of the nth record in a file can be computed as follows:

address-of-first-record n - 1 record-size

If the first byte of the first record is at address 1 and the record size is 200 bytes, the address of the fourth record is 601.

Sequential files suffer the same problems as contiguous arrays when records are being inserted and deleted. A copy procedure similar to the one in Figure 3.12 must be used to add a record to a file. The procedure is even less efficient for files than for arrays because of the large size of the records that must be copied.

One method of solving this problem is to use linked lists. With files, the data elements of a linked list are entire records instead of basic data elements. The methods for search- ing, inserting records, and deleting records are essentially the same as described previously.

Another method of organizing files uses an index, an array of pointers to records. The pointers can be ordered in any sequence you need. For example, a file of customer records can be ordered by ascending account number, as shown in Figure 3.15.

FIGURE 3.14 A record data structure Courtesy of Course Technology/Cengage Learning

Chapter 3

The advantage of using an index lies in the efficiency of record insertion, deletion, and retrieval. When a record is added to a file, storage is allocated for the record, and data is placed in the storage location. The index is then updated by inserting the new record s address. An index update follows the same procedure as an array update. Because the array contains only pointers, it s small and fast to update.

Classes and Objects Up to this point, data and programs have been discussed as two fundamentally different things. Programs contain instructions, which transform data inputs into data outputs when executed. Data items are held in storage devices, moved to CPU registers when needed, transformed into data outputs by executing instructions, and sent to output or storage devices again. In this view of computer systems and software behavior, data items are mainly static, and programs are the active means for transforming and updating data items.

In the 1980s and 1990s, computer researchers developed a different view of computer and software behavior: combining program instructions and data into a single data struc- ture. A class is a data structure containing both traditional (static) data elements and pro- grams that manipulate the data. The programs in a class are called methods. A class combines related data items in much the same way a record does, but it extends the record to include methods for manipulating data items.

Think of the customer record in Figure 3.14 as a starting point for defining a Cus- tomer class. The record contains some primitive data items and data structures describing features of a customer. (Others, such as account balance, could be added to create a more complete representation of a customer.)

To turn the customer record into a Customer class, methods for manipulating or modifying data elements in the record must be added. For example, you can add a simple

FIGURE 3.15 An indexed file Courtesy of Course Technology/Cengage Learning

Data Structures

method for updating a data element s content called Update-First-Name. You can check for legal values, such as making sure the value supplied for Zip-Code is a valid U.S. zip code in the customer s state. Functions, such as Print-Mailing-Label, or methods for modifying the customer s account balance to reflect transactions, such as Apply-Payment, can be added. Figure 3.16 shows some possible data elements and methods for the Customer class.

An object is one instance, or variable, of a class. Each person who s a customer is represented by one variable or object of the Customer class. Each object can be stored in a storage device, and each object s data elements occupy a separate part of the storage device.

Viewed as just another data structure, an object differs little from a record. Much as the data element Street-Address can be represented with a character array, a method can be represented as an array of CPU instructions. Methods can be represented in other ways, including linked lists of instructions or pointers to files containing sequential sets of instructions. In essence, the only new primitive data type needed to represent a method in an object is an instruction. As you see in Chapter 4, instructions, like data, have specific representation and storage formats.

FIGURE 3.16 A Customer class containing traditional data elements (darker boxes) and methods (lighter boxes)

Courtesy of Course Technology/Cengage Learning

Chapter 3

Summary

Data can be represented in many ways. To be processed by any device, data must be converted from its native format into a form suitable for the processing device. Modern computers represent data as electronic signals and implement processing devices by using electronic circuitry. Electronic processing devices exploit the physical laws of electricity. Because the laws of electricity can be stated as mathematical equations, electronic devices can perform the computational functions embedded in these equations. Other ways of implementing processors, such as mechanics and optics, use similar mathematically stated physical laws.

All data, including nonnumeric data, are represented in modern computers as strings of binary digits, or bits. Bits are used because 0 and 1 can be encoded in clearly recognizable electrical states, such as high and low voltage. Binary electrical states can be processed and stored by reliable, cheap electrical devices. A handful of primitive data types are repre- sented and processed by a CPU, including integers, real numbers, characters, Boolean values, and memory addresses.

Numeric values other than 0 and 1 are represented by combining multiple bits into larger groups, called bit strings, much as the decimal digits 2, 5, and 9 can be combined to form the larger value 592. Each bit string has a specific data format and coding method. There are many different data formats and coding methods. CPU designers choose formats and methods that represent the best balance among compactness, range, ease of manipulation, accuracy, and standardization. The optimal balance can vary, depending on the type of data and its intended uses.

Integers have no fractional component and can use simple data formats. Twos complement is the most common integer format, although excess notation is used sometimes. Real numbers have both whole and fractional components. Their complex structure requires a complex data format called floating-point notation that represents a numeric value as a mantissa multiplied by a positive or negative power of 2. A value can have many digits of precision in floating-point notation for very large or very small magnitudes but not both large and small magnitudes at the same time. Floating-point formats used in modern computers typically follow IEEE standards, which include binary and decimal representations ranging from 32 to 128 bits in length. Floating-point formats are less accurate and more difficult to process than twos complement format.

Character data isn t inherently numeric. Characters are converted to numbers by means of a coding table, in which each character occupies a sequential position. A character is represented by converting it to its integer table position. Characters are extracted from inte- gers by the reverse process. Many different tables are possible. Most computers use the ASCII or Unicode coding tables. ASCII is an older standard geared toward the English lan- guage. Unicode is a more recent standard with a character set large enough to encompass ASCII and all written languages.

A Boolean data value must be true or false. Memory addresses can be simple or complex numeric values, depending on whether the CPU uses a flat or segmented memory model. Flat memory addresses can be represented as a single integer. Segmented memory

Summary

addresses require multiple integers. Many CPUs also provide double-precision numeric data types, which double the number of bits used to store a value.

Programs often define and manipulate data in larger and more complex units than primitive CPU data types. A data structure is a related group of primitive data elements organized for some type of common processing and is defined in software. To enable a CPU to manipu- late a data structure, software decomposes operations on the data structure into equivalent operations on its primitive components. Commonly used data structures include arrays, linked lists, records, tables, files, indexes, and objects. Many data structures use pointers, which are stored memory addresses, to link primitive data components.

In this chapter, you ve learned the different ways data is represented in modern computers, focusing particularly on the relationship between data representation and the CPU. This chapter and the preceding chapters have introduced basic concepts and terminology of systems archi- tecture. The understanding you ve gained in the first three chapters lays the foundation for the more detailed discussion of the hardware implementations of data processing, storage, and communication in upcoming chapters.

Key Terms

address

American Standard Code for Information Interchange (ASCII)

array

base

binary number

bit

bit string

Boolean data type

Boolean logic

byte

character

class

collating sequence

data structure

decimal point

double-precision

doubly linked list

excess notation

Extended Binary Coded Decimal Interchange Code (EBCDIC)

file

flat memory model

floating-point notation

hexadecimal notation

high-order bit

index

integer

International Alphabet 5 (IA5)

International Organization for Standardization (ISO)

Latin-1

least significant digit

linked list

long integer

low-order bit

machine data type

manipulation

method

most significant digit

multinational character

numeric range

object

octal notation

overflow

pointer

primitive data type

radix

100

Chapter 3

radix point

real number

record

segmented memory model

signed integer

singly linked list

string

truncation

twos complement notation

underflow

Unicode

unsigned integer

Vocabulary Exercises

1. An element in a(n) contains pointers to both the next and previous list elements.

2. notation encodes a real number as a mantissa multiplied by a power (exponent) of 2.

3. A(n) is an integer stored in double the normal number of bit positions.

4. Increasing a numeric representation format s size (number of bits) increases the of values that can be represented.

5. Assembly (machine) language programs for most computers use notation to represent memory address values.

6. A(n) is a data item composed of multiple primitive data items.

7. In older IBM mainframe computers, characters were encoded according to the coding scheme.

8. A(n) is the address of another data item or structure.

9. In a positional numbering system, the separates digits representing whole number quantities from digits representing fractional quantities.

10. A(n) is an array of characters.

11. Most Intel CPUs use the , in which each memory address is represented by two integers.

12. A set of data items that can be accessed in a specified order by using pointers is called a(n) .

13. A(n) contains 8 .

14. A(n) list stores one pointer with each list element.

15. The result of adding, subtracting, or multiplying two integers might result in overflow but never or .

16. A(n) is a sequence of primitive data elements stored in sequential storage locations.

17. A(n) is a data structure composed of other data structures or primitive data ele- ments, commonly used as a unit of input and output to and from files or databases.

18. A(n) data item can contain only the values true or false.

19. A(n) is an array of data items, each of which contains a key value and a pointer to another data item.

101

Vocabulary Exercises

20. Many computers implement numeric data types to increase accuracy and prevent overflow and underflow.

21. Unlike ASCII and EBCDIC, is a 16-bit or 32-bit character coding table.

22. The is the bit of lowest magnitude in a byte or bit string.

23. occurs when the result of an arithmetic operation exceeds the number of bits available to store it.

24. In a CPU, arithmetic generally is easier to implement than arithmetic because of a simpler data coding scheme and data manipulation circuitry.

25. In the , memory addresses consist of a single integer.

26. The has defined a character-coding table called , which combines the ASCII-7 coding table with an additional 128 Western European multinational characters.

27. Data represented in is transmitted accurately between computer equipment from different manufacturers if each computer s CPU represents real numbers by using an IEEE standard notation.

28. The ordering of characters in a coding table is called a(n) .

29. A(n) is a data structure containing both static data and methods.

30. A(n) is one instance or variable of a class.

Review Questions

1. What are the binary, octal, and hexadecimal representations of the decimal number 10?

2. Why is binary data representation and signaling the preferred method of computer hard- ware implementation?

3. What is excess notation? What is twos complement notation? Why are they needed? In other words, why can t integer values be represented by ordinary binary numbers?

4. What is the numeric range of a 16-bit twos complement value? A 16-bit excess notation value? A 16-bit unsigned binary value?

5. What is overflow? What is underflow? How can the probability of their occurrence be minimized?

6. Why are real numbers more difficult to represent and process than integers?

7. Why might a programmer choose to represent a data item in IEEE binary128 floating-point format instead of IEEE binary64 floating-point format? What additional costs might be incurred at runtime (when the application program executes) as a result of using the 128-bit instead of the 64-bit format?

8. Why doesn t a CPU evaluate the expression 'A' = 'a' as true?

9. What are the differences between ASCII and Unicode?

10. What primitive data types can normally be represented and processed by a CPU?

11. What is a data structure? List several types of common data structures.

12. What is an address? What is a pointer? What purpose are they used for?

102

Chapter 3

13. How is an array stored in main memory? How is a linked list stored in main memory? What are their comparative advantages and disadvantages? Give examples of data that would be best stored as an array and as a linked list.

14. How does a class differ from other data structures?

Problems and Exercises

1. Develop an algorithm or program to implement the following function:

insert_in_linked_list (element,after_pointer)

The element parameter is a data item to be added to a linked list, and the after_pointer parameter is the address of the element after which the new element will be inserted.

2. Develop an algorithm or program to implement the following function:

insert_in_array (element,position)

The element parameter is a data item to be added to the array, and the position parameter is the array index at which the new element will be inserted. Make sure to account for elements that must be moved over to make room for the new element.

3. Consider the following binary value:

1000 0000 0010 0110 0000 0110 1101 1001

What number (base 10) is represented if the value is assumed to represent a number stored in twos complement notation? Excess notation? IEEE binary32 floating-point notation?

4. How are the values 51510 and -51510 represented as ordinary binary numbers? How are they represented as octal and hexadecimal numbers? How are they represented in 16-bit excess notation and in 16-bit twos complement notation?

5. How is the binary value 101101 2-101101 represented in IEEE binary32 floating-point notation?

6. Convert the following values represented in base 12 to their equivalent representations in base 2, base 5, and base 10:

1A7812

-90B212

Research Problems

1. Choose a commonly used microprocessor, such as the Intel Core (www.intel.com) or IBM POWER6 (www.ibm.com). What data types are supported? How many bits are used to store each data type? How is each data type represented internally?

2. Most personal and office productivity applications, such as word-processing applications, are marketed internationally. To minimize development costs, software producers develop a single version of the program but have separate configurations for items such as menus and error messages that vary from language to language. Investigate a commonly used development tool for applications (called an integrated development environment ), such

103

Research Problems

as Microsoft Visual Studio (www.microsoft.com). What tools and techniques (for example, Unicode data types and string tables) are supported for developing multilingual programs?

3. Object-oriented programming has been adopted widely because of its capability to reuse code. Most application development software provides class libraries and extensive support for complex data structures, including linked lists. Investigate one of these libraries, such as the Microsoft Foundation Class (www.microsoft.com) or the Java 2 Platform (http://java. sun.com) application programming interface (API). What data structures are supported by the library? What types of data are recommended for use with each data structure object? Which classes contain which data structures, and what methods does the library provide?

104

Chapter 3