Chapter 2 Number Systems and Codes 2.1 Positional Number Systems The traditional number system that we learned in school and use every day in positional number business is called a positional number system.In such a system,a number is rep- resented by a string of digits where each digit position has an associated weight. weight The value of a number is a weighted sum of the digits,for example: 1734=1.1000+7-100+3.10+41 Each weight is a power of 10 corresponding to the digit's position.A decimal point allows negative as well as positive powers of 10 to be used: 5185.68=5·1000+1-100+8-10+5-1+6-0.1+8-0.01 In general,a number D of the form dido.dd2 has the value D=d110+d010+d1101+d210 Here,10 is called the base or radix of the number system.In a general positional radix number system,the radix may be any integerr2,and a digit in position i has weight r.The general form of a number in such a system is dp-dp-2.d0.dd2.dn where there are p digits to the left of the point and n digits to the right of the radix point point,called the radix point.If the radix point is missing,it is assumed to be to the right of the rightmost digit.The value of the number is the sum of each digit multiplied by the corresponding power of the radix: D=∑df i=-n high-order digit Except for possible leading and trailing zeroes,the representation of a most significant digit number in a positional number system is unique.(Obviously,0185.6300 equals low-order digit 185.63,and so on.)The leftmost digit in such a number is called the high-order least significant digit or most significant digit,the rightmost is the low-order or least significant digit. As we'll learn in Chapter 3,digital circuits have signals that are normally binary digit in one of only two conditions-low or high,charged or discharged,off or on The signals in these circuits are interpreted to represent binary digits(or bits) binary radix that have one of two values,0 and 1.Thus,the binary radix is normally used to represent numbers in a digital system.The general form of a binary number is bp-1bp-2.bbo.b1b-2·bn and its value is B= b·2 Copyright 1999 by John F.Wakerly Copying Prohibited
22 Chapter 2 Number Systems and Codes DO NOT COPY DO NOT COPY DO NOT COPY DO NOT COPY DO NOT COPY DO NOT COPY DO NOT COPY DO NOT COPY DO NOT COPY Copyright © 1999 by John F. Wakerly Copying Prohibited 2.1 Positional Number Systems The traditional number system that we learned in school and use every day in business is called a positional number system. In such a system, a number is represented by a string of digits where each digit position has an associated weight. The value of a number is a weighted sum of the digits, for example: 1734 = 1·1000 + 7·100 + 3·10 + 4·1 Each weight is a power of 10 corresponding to the digit’s position. A decimal point allows negative as well as positive powers of 10 to be used: 5185.68 = 5·1000 + 1·100 + 8·10 + 5·1 + 6·0.1 + 8·0.01 In general, a number D of the form d1d0.d−1d−2 has the value D = d1·101 + d0·100 + d–1·10–1 + d–2·10–2 Here, 10 is called the base or radix of the number system. In a general positional number system, the radix may be any integer r ≥ 2, and a digit in position i has weight ri . The general form of a number in such a system is dp–1dp–2···d1d0 . d–1d–2···d–n where there are p digits to the left of the point and n digits to the right of the point, called the radix point. If the radix point is missing, it is assumed to be to the right of the rightmost digit. The value of the number is the sum of each digit multiplied by the corresponding power of the radix: Except for possible leading and trailing zeroes, the representation of a number in a positional number system is unique. (Obviously, 0185.6300 equals 185.63, and so on.) The leftmost digit in such a number is called the high-order or most significant digit; the rightmost is the low-order or least significant digit. As we’ll learn in Chapter 3, digital circuits have signals that are normally in one of only two conditions—low or high, charged or discharged, off or on. The signals in these circuits are interpreted to represent binary digits (or bits) that have one of two values, 0 and 1. Thus, the binary radix is normally used to represent numbers in a digital system. The general form of a binary number is bp–1bp–2···b1b0 . b–1b–2···b–n and its value is positional number system weight base radix radix point D di r i ⋅ i n = – p – 1 = ∑ high-order digit most significant digit low-order digit least significant digit binary digit bit binary radix B bi 2i ⋅ i n = – p – 1 = ∑
Section 2.2 Octal and Hexadecimal Numbers 23 In a binary number,the radix point is called the binary point.When dealing with binary point binary and other nondecimal numbers.we use a subscript to indicate the radix of each number,unless the radix is clear from the context.Examples of binary numbers and their decimal equivalents are given below. 100112=116+08+04+1-2+11=1o 1000102=1-32+016+0-8+0-4+1-2+01=340 101.0012=14+0:2+11+00.5+00.25+10.125=5.120 The leftmost bit of a binary number is called the high-order or most significant MS bit (MSB);the rightmost is the low-order or least significant bit (LSB). LSB 2.2 Octal and Hexadecimal Numbers Radix 10 is important because we use it in everyday business,and radix 2 is important because binary numbers can be processed directly by digital circuits. Numbers in other radices are not often processed directly,but may be important for documentation or other purposes.In particular,the radices8 and 16 provide convenient shorthand representations for multibit numbers in a digital system. The octal number system uses radix 8,while the hexadecimal number sys- octal number system em uses radix 16.Table 2-1 shows the binary integers fromto 1111 and their cimal number octal,decimal,and hexadecimal equivalents.The octal system needs8 digits,so it uses digits 0-7 of the decimal system.The hexadecimal system needs 16 dig- its,so it supplements decimal digits 09with the letters4-F. hexadecimal digit The octal and hexadecimal number systems are useful for representing multibit numbers because their radices are powers of 2.Since a string of three bits can take on eight different combinations.it follows that each 3-bit string can be uniquely sented by one octal digit,according to the third and fourth col- umns of Table 2-1.Likewise,a 4-bit string can be represented by one hexadecimal digit according to the fifth and sixth columns of the table. Thus,it is very easy to convert a binary number to octal.Starting at the binary point and working ef we simply separate the bits into groups of three and replace each group with the corresponding octal digit: 1000110011102=1000110011102=43168 111011011101010012=0111011011101010012=3556518 The procedure for binary to hexadecimal conversion is similar,except we use binary to hexadecimal groups of four bits: comersion 1000110011102=1000110011102=8CE16 111011011101010012=000111011011101010012=1DBA916 In these examples we have freely added zeroes on the left to make the total num- ber of bits a multiple of 3 or 4 as required. Copyright1999 by John F.Wakerly Copying Prohibited
Section 2.2 Octal and Hexadecimal Numbers 23 DO NOT COPY DO NOT COPY DO NOT COPY DO NOT COPY DO NOT COPY DO NOT COPY DO NOT COPY DO NOT COPY DO NOT COPY Copyright © 1999 by John F. Wakerly Copying Prohibited In a binary number, the radix point is called the binary point. When dealing with binary and other nondecimal numbers, we use a subscript to indicate the radix of each number, unless the radix is clear from the context. Examples of binary numbers and their decimal equivalents are given below. The leftmost bit of a binary number is called the high-order or most significant bit (MSB); the rightmost is the low-order or least significant bit (LSB). 2.2 Octal and Hexadecimal Numbers Radix 10 is important because we use it in everyday business, and radix 2 is important because binary numbers can be processed directly by digital circuits. Numbers in other radices are not often processed directly, but may be important for documentation or other purposes. In particular, the radices 8 and 16 provide convenient shorthand representations for multibit numbers in a digital system. The octal number system uses radix 8, while the hexadecimal number system uses radix 16. Table 2-1 shows the binary integers from 0 to 1111 and their octal, decimal, and hexadecimal equivalents. The octal system needs 8 digits, so it uses digits 0–7 of the decimal system. The hexadecimal system needs 16 digits, so it supplements decimal digits 0–9 with the letters A–F. The octal and hexadecimal number systems are useful for representing multibit numbers because their radices are powers of 2. Since a string of three bits can take on eight different combinations, it follows that each 3-bit string can be uniquely represented by one octal digit, according to the third and fourth columns of Table 2-1. Likewise, a 4-bit string can be represented by one hexadecimal digit according to the fifth and sixth columns of the table. Thus, it is very easy to convert a binary number to octal. Starting at the binary point and working left, we simply separate the bits into groups of three and replace each group with the corresponding octal digit: The procedure for binary to hexadecimal conversion is similar, except we use groups of four bits: In these examples we have freely added zeroes on the left to make the total number of bits a multiple of 3 or 4 as required. 100112 = 1·16 + 0·8 + 0·4 + 1·2 + 1·1 = 1910 1000102 = 1·32 + 0·16 + 0·8 + 0·4 + 1·2 + 0·1 = 3410 101.0012 = 1·4 + 0·2 + 1·1 + 0·0.5 + 0·0.25 + 1·0.125 = 5.12510 1000110011102 = 100 011 001 1102 = 43168 111011011101010012 = 011 101 101 110 101 0012 = 3556518 1000110011102 = 1000 1100 11102 = 8CE16 111011011101010012 = 00011101 1011 1010 10012 = 1DBA916 binary point MSB LSB octal number system hexadecimal number system hexadecimal digits A–F binary to octal conversion binary to hexadecimal conversion
24 Chapter 2 Number Systems and Codes Table 2-1 3-Bit Binary,decimal 4-Bit Binary Decimal Octal String Hexadecimal String 0 0 0 000 0 0000 numbers. 1 001 0001 10 2 2 010 2 0010 1 3 3 011 3 0011 4 100 4 0100 101 5 101 0101 6 6 110 6 0110 111 7 111 0111 1000 8 10 1000 1001 9 11 9 1001 1010 10 12 A 1010 1011 11 B 1011 1100 14 1100 1101 3 15 D 1101 1110 14 6 E 1110 1111 15 1 1111 If a binary number contains digits to the right of the binary point,we can convert them to octal or hexadecimal by starting at the binary point and working right.Both the left-hand and right-hand sides can be padded with zeroes to get multiples of three or four bits,as shown in the example below: 10.10110010112=010.1011001011002=2.5454g =0010.1011001011002=2.B2C16 octal or hexadecimal to Converting in the reverse direction,from octal or hexadecimal to binary,is binary comversion very easy.We simply replace each octal or hexadecimal digit with the corre- sponding 3-or 4-bit string,as shown below 13573=0010111011112 2046.17g=010000100110.0011112 BEAD16=10111110101011012 9F.46C16=1001111.0100011011002 The octal number system was quite popular 25 years ago because of certain minicomputers that had their front-panel lights and switches arranged in groups of three.However,the octal number system is not used much today,because of byte the preponderance of machines that process 8-bit bytes.It is difficult to extract individual byte values in multibyte quantities in the octal representation,for Copyright 1999 by John F.Wakerly Copying Prohibited
24 Chapter 2 Number Systems and Codes DO NOT COPY DO NOT COPY DO NOT COPY DO NOT COPY DO NOT COPY DO NOT COPY DO NOT COPY DO NOT COPY DO NOT COPY Copyright © 1999 by John F. Wakerly Copying Prohibited If a binary number contains digits to the right of the binary point, we can convert them to octal or hexadecimal by starting at the binary point and working right. Both the left-hand and right-hand sides can be padded with zeroes to get multiples of three or four bits, as shown in the example below: Converting in the reverse direction, from octal or hexadecimal to binary, is very easy. We simply replace each octal or hexadecimal digit with the corresponding 3- or 4-bit string, as shown below: The octal number system was quite popular 25 years ago because of certain minicomputers that had their front-panel lights and switches arranged in groups of three. However, the octal number system is not used much today, because of the preponderance of machines that process 8-bit bytes. It is difficult to extract individual byte values in multibyte quantities in the octal representation; for Table 2-1 Binary, decimal, octal, and hexadecimal numbers. Binary Decimal Octal 3-Bit String Hexadecimal 4-Bit String 0 0 0 000 0 0000 1 1 1 001 1 0001 10 2 2 010 2 0010 11 3 3 011 3 0011 100 4 4 100 4 0100 101 5 5 101 5 0101 110 6 6 110 6 0110 111 7 7 111 7 0111 1000 8 10 — 8 1000 1001 9 11 — 9 1001 1010 10 12 — A 1010 1011 11 13 — B 1011 1100 12 14 — C 1100 1101 13 15 — D 1101 1110 14 16 — E 1110 1111 15 17 — F 1111 10.10110010112 = 010 . 101 100 101 1002 = 2.54548 = 0010 . 1011 0010 11002 = 2.B2C16 13578 = 001 011 101 1112 2046.178 = 010 000 100 110 . 001 1112 BEAD16 = 1011 1110 1010 11012 9F.46C16 = 1001 111 . 0100 0110 11002 octal or hexadecimal to binary conversion byte
Section 2.3 General Positional Number System Conversions 25 WHEN I'M 64 As you grow older,you'll find that the hexadecimal number system is useful for thcmper When tud40 Itodhhds The 16 as whi d under my breath,o ，Atag People get all excited about decennial birthdays like 20,30,40,50,.but you should be able to convince your friends that the decimal system is of no fundamental significance.More significant life changes occur around birthdays2,4,8,16,32,and 64.when you add a most significant bit to your age.Why do you think the Beatles sang"When I'm sixty-four"? example,what are the octal values of the four 8-bit bytes in the 32-bit number with octal representation 12345670123g? In the hexadecimal system,two digits represent an 8-bit byte,and 2n digits represent word each pair of digits utes exactly one byte.For example,the 32-bit hexadecimal number 5678ABCD consists of four bytes with values 5616,7816,AB16,and CD16.In this context,a 4-bit hexadecimal digit is sometimes called a nibble;a 32-bit(4-byte)number has eight nibbles.Hexa- nibble decimal numbers are often used to describe a computer's memory address space For example,a computer with 16-bit addresses might be described as having read/write memory installed at addresses 0-EFFF16 and read-only memory at addresses F000-FFFF6Many computer programming languages use the prefix Ox"to denote a hexadecimal number,for example,0xBFC0000. 0x prefix 2.3 General Positional Number System Conversions In general,conversion between two radices cannot be done by simple substitu tions;arithmetic operations are required.In this section,we show how to convert a number in any radix to radix 10 and vice versa,using radix-10 arithmetic. In Section 2.1,we indicated that the value ofa number in any radix is given radix-r to decima by the formula D=dr wherer is the radix of the number and there are p digits to the left of the radix point and n to the right.Thus.the value of the number can be found by convert- ing each digit of the number to its radix-10 equivalent and expanding the formula using radix-10 arithmetic.Some examples are given below 1CE816=116+12-12+1416+8160=740010 F1A316=15·16+1162+10-16+316=6185910 436.5g=482+38+680+581=286.62510 132.34=1·42+341+240+31-=30.7510 Copyright 1999 by John F.Wakerly Copying Prohibited
Section 2.3 General Positional Number System Conversions 25 DO NOT COPY DO NOT COPY DO NOT COPY DO NOT COPY DO NOT COPY DO NOT COPY DO NOT COPY DO NOT COPY DO NOT COPY Copyright © 1999 by John F. Wakerly Copying Prohibited example, what are the octal values of the four 8-bit bytes in the 32-bit number with octal representation 123456701238? In the hexadecimal system, two digits represent an 8-bit byte, and 2n digits represent an n-byte word; each pair of digits constitutes exactly one byte. For example, the 32-bit hexadecimal number 5678ABCD16 consists of four bytes with values 5616, 7816, AB16, and CD16. In this context, a 4-bit hexadecimal digit is sometimes called a nibble; a 32-bit (4-byte) number has eight nibbles. Hexadecimal numbers are often used to describe a computer’s memory address space. For example, a computer with 16-bit addresses might be described as having read/write memory installed at addresses 0–EFFF16, and read-only memory at addresses F000–FFFF16. Many computer programming languages use the prefix “0x” to denote a hexadecimal number, for example, 0xBFC0000. 2.3 General Positional Number System Conversions In general, conversion between two radices cannot be done by simple substitutions; arithmetic operations are required. In this section, we show how to convert a number in any radix to radix 10 and vice versa, using radix-10 arithmetic. In Section 2.1, we indicated that the value of a number in any radix is given by the formula where r is the radix of the number and there are p digits to the left of the radix point and n to the right. Thus, the value of the number can be found by converting each digit of the number to its radix-10 equivalent and expanding the formula using radix-10 arithmetic. Some examples are given below: 1CE816 = 1·163 + 12·162 + 14·161 + 8·160 = 740010 F1A316 = 15·163 + 1·162 + 10·161 + 3·160 = 6185910 436.58 = 4·82 + 3·81 + 6·80 + 5·8–1 = 286.62510 132.34 = 1·42 + 3·41 + 2·40 + 3·4–1 = 30.7510 WHEN I’M 64 As you grow older, you’ll find that the hexadecimal number system is useful for more than just computers. When I turned 40, I told friends that I had just turned 2816. The “16” was whispered under my breath, of course. At age 50, I’ll be only 3216. People get all excited about decennial birthdays like 20, 30, 40, 50, ., but you should be able to convince your friends that the decimal system is of no fundamental significance. More significant life changes occur around birthdays 2, 4, 8, 16, 32, and 64, when you add a most significant bit to your age. Why do you think the Beatles sang “When I’m sixty-four”? nibble 0x prefix radix-r to decimal conversion D di r i ⋅ i n = – p – 1 = ∑
26 Chapter 2 Number Systems and Codes A shortcut for converting whole numbers to radix 10 is obtained by rewrit- ing the expansion formula as follows D=(.(gp-）r+do2)r+).r+d)r+do That is,we start with a sum of 0:beginning with the leftmost digit,we multiply the sum by rand add the next digit to the sum,repeating until all digits have beer processed.For example,we can write F1AC16=((15)16+1·16+10)16+12 what happens if we divide the formula by r.Since the parenthesized part of the formula is evenly divisible by r,the quotient will be 0=（.(p-r+dp-2)r+.)r+d and the remainder will be do.Thus,do can be computed as the remainder of the long division of D by r.Furthermore,the quotient O has the same form as the original formula.Therefore,successive divisions bywill yied ig its of D from right to left,until all the digits of D have been derived.Examples are given below: 179+2=89 remainder 1 (LSB) +2=44 remainder 1 ÷2=22 remainder0 ÷2=1 1 remainder0 ÷2=5 remainder1 ÷2=2 remainder 1 +2=1 remainder 0 ÷2=0 remainder1(MSB) 17910=101100112 467+8=58 remainder 3 (least significant digit) +8=7remainder 2 +8=0 remainder 7 (most significant digit) 46710=723g 3417+16=213 remainder 9 (least significant digit) ÷l6=13 remainder5 +16=0 remainder 13 (most significant digit) 341710=D5916 Table 2-2 summarizes methods for converting among the most common radices. Copyright 1999 by John F.Wakerly Copying Prohibited
26 Chapter 2 Number Systems and Codes DO NOT COPY DO NOT COPY DO NOT COPY DO NOT COPY DO NOT COPY DO NOT COPY DO NOT COPY DO NOT COPY DO NOT COPY Copyright © 1999 by John F. Wakerly Copying Prohibited A shortcut for converting whole numbers to radix 10 is obtained by rewriting the expansion formula as follows: D = ((· · ·((dp–1)·r + dp–2)·r + · · ·) · · ·r + d1)·r + d0 That is, we start with a sum of 0; beginning with the leftmost digit, we multiply the sum by r and add the next digit to the sum, repeating until all digits have been processed. For example, we can write F1AC16 = (((15)·16 + 1·16 + 10)·16 + 12 Although this formula is not too exciting in itself, it forms the basis for a very convenient method of converting a decimal number D to a radix r. Consider what happens if we divide the formula by r. Since the parenthesized part of the formula is evenly divisible by r, the quotient will be Q = (· · ·((dp–1)·r + dp–2)·r + · · ·)·r + d1 and the remainder will be d0. Thus, d0 can be computed as the remainder of the long division of D by r. Furthermore, the quotient Q has the same form as the original formula. Therefore, successive divisions by r will yield successive digits of D from right to left, until all the digits of D have been derived. Examples are given below: 179 ÷ 2 = 89 remainder 1 (LSB) ÷2 = 44 remainder 1 ÷2 = 22 remainder 0 ÷2 = 11 remainder 0 ÷2 = 5 remainder 1 ÷2 = 2 remainder 1 ÷2 = 1 remainder 0 ÷2 = 0 remainder 1 (MSB) 17910 = 101100112 467 ÷ 8 = 58 remainder 3 (least significant digit) ÷8 = 7 remainder 2 ÷ 8 = 0 remainder 7 (most significant digit) 46710 = 7238 3417 ÷ 16 = 213 remainder 9 (least significant digit) ÷ 16 = 13 remainder 5 ÷ 16 = 0 remainder 13 (most significant digit) 341710 = D5916 Table 2-2 summarizes methods for converting among the most common radices. decimal to radix-r conversion