Tinder, R F, Oklobdzija, V.G., Hamacher, V.C., Vranesic, Z.G., Zaky, S.G., Raymond The electrical Engineering Handbook Ed. Richard C. Dorf Boca Raton: CRc Press llc. 2000
Tinder, R.F., Oklobdzija, V.G., Hamacher, V.C., Vranesic, Z.G., Zaky, S.G., Raymond, J. “Organization” The Electrical Engineering Handbook Ed. Richard C. Dorf Boca Raton: CRC Press LLC, 2000
86 Organization 86.1 Number Systems Richard e. Tinder Positional and Polynomial Representations. Unsigned Binary Washington State University Number System. Unsigned Binary-Coded Decimal, Hexadecimal and Octal Systems.Conversion between Number Systems. Signed Vojin G. Oklobdzija Binary Numbers. Floating-Point Number Systems 86.2 Computer Arithmetic Number Representation. Algorithms for Basic Arithmetic V. Carl hamacher Operations. Implementatino of Addition. Implementation of the Queens University, canada Multiplication Algorithm. Floating-Point Representation Zvonko g. vranesic 86.3 Architecture Functional Units. Basic Operational Concepts Performance University of Toronto Safwat G. Zaky 86.4 Microprogramming Levels of Programming. Microinstruction Structure Microprogram Development. High-Level Languages for Jacques raymond Microprogramming. Emulation. Applications of University of ottawa 86.1 Number Systems Richard e. Tinder Number systems provide the basis for conveying and quantifying information. Weather data, stocks, pagination of books, weights and measures-these are just a few examples of the use of numbers that affect our daily lives. For this purpose we find the decimal (or arabic)number system to be reliable and easy to use. This system evolved presumably because early humans were equipped with a crude type of calculator, their ten fingers. A lumber system that is appropriate for humans, however, may be intractable for use by a machine such as a computer. Likewise, a number system appropriate for a machine may not be suitable for human use Before concentrating on those number systems that are useful in computers, it will be helpful to review the characteristics that are desirable in any number system. There are four important characteristics in all Distinguishability of symbols Arithmetic operations capability Error control capability To one degree or another the decimal system of numbers satisfies these characteristics for hard-copy transfer of information between humans. Roman numerals and binary are examples of number systems that do not satisfy all four characteristics for human use. On the other hand, the binary number system is preferable for use in digital computers. The reason is simply put: current digital electronic machines recognize only two identifiable states physically represented by a high voltage level and a low voltage level. These two physical states are logically interpreted as the binary symbols 1 and 0 c 2000 by CRC Press LLC
© 2000 by CRC Press LLC 86 Organization 86.1 Number Systems Positional and Polynomial Representations • Unsigned Binary Number System • Unsigned Binary-Coded Decimal, Hexadecimal, and Octal Systems • Conversion between Number Systems • Signed Binary Numbers • Floating-Point Number Systems 86.2 Computer Arithmetic Number Representation • Algorithms for Basic Arithmetic Operations • Implementatino of Addition • Implementation of the Multiplication Algorithm • Floating-Point Representation 86.3 Architecture Functional Units • Basic Operational Concepts • Performance • Multiprocessors 86.4 Microprogramming Levels of Programming • Microinstruction Structure • Microprogram Development • High-Level Languages for Microprogramming • Emulation • Applications of Microprogramming 86.1 Number Systems Richard F. Tinder Number systems provide the basis for conveying and quantifying information. Weather data, stocks, pagination of books, weights and measures—these are just a few examples of the use of numbers that affect our daily lives. For this purpose we find the decimal (or arabic) number system to be reliable and easy to use. This system evolved presumably because early humans were equipped with a crude type of calculator, their ten fingers. A number system that is appropriate for humans, however, may be intractable for use by a machine such as a computer. Likewise, a number system appropriate for a machine may not be suitable for human use. Before concentrating on those number systems that are useful in computers, it will be helpful to review the characteristics that are desirable in any number system. There are four important characteristics in all: • Distinguishability of symbols • Arithmetic operations capability • Error control capability • Tractability and speed To one degree or another the decimal system of numbers satisfies these characteristics for hard-copy transfer of information between humans. Roman numerals and binary are examples of number systems that do not satisfy all four characteristics for human use. On the other hand, the binary number system is preferable for use in digital computers. The reason is simply put: current digital electronic machines recognize only two identifiable states physically represented by a high voltage level and a low voltage level. These two physical states are logically interpreted as the binary symbols 1 and 0. Richard F. Tinder Washington State University Vojin G. Oklobdzija University of California, Davis V. Carl Hamacher Queen's University, Canada Zvonko G. Vranesic University of Toronto Safwat G. Zaky University of Toronto Jacques Raymond University of Ottawa
fifth desirable characteristic of a number system to be used in a computer should be that it have a minimum number of easily identifiable states. The binary number system satisfies this condition. However, the digital computer must still interface with humankind. This is done by converting the binary data to a decimal and character-based form that can be readily understood by humans. A minimum number of identifiable characters (say I and o, or true and false)is not practical or desirable for direct human use. If this is difficult to understand, hand,use of a computer for this purpose would not only be practical but, in many cases, highly desirable imagine trying to complete a tax form in binary or in any number system other than decimal. On the ot Positional and Polynomial Representations The positional form of a number is a set of side-by-side juxtaposed) digits given generally in fixed-point form as MSD Radix point LSD Intege aao Fraction- where the radix(or base) is the total number of digits in the number system and a is a digit in the set defined for radix r. Here, the radix point separates n integer digits on the left from m fraction digits on the right. Notice that a,- is the most significant(highest-order) digit, called MSD, and that a-m is the least significant (lowe order)digit, denoted by LsD The value of the number in Eq. (86. 1)is given in polynomial form by ∑ a,r+ a where a, is the digit in the ith position with a weight ri. rectly. For the decimal system r= 10, indicating that there are 10 distinguishable characters recognized as decimal numerals 0, 1, 2,..r-1(=9). Examples of the positional and polynomial representations for the decimal system are No=(d3d,,do.d_d,_,)1o =3017.528 ∑4 3×103+0×102+1×101+7×10°+5×10-1+2×10-2+8×10-3 =3000+10+7+0.5+0.02+0.008 where d, is the decimal digit in the th position. Exclusive of possible leading and trailing zeros, the MSD and LSD for this number are 3 and 8, respectively. This number could have been written in a form such as Nio 03017.52800 without altering its value but implying greater accuracy of the fraction portion. e 2000 by CRC Press LLC
© 2000 by CRC Press LLC A fifth desirable characteristic of a number system to be used in a computer should be that it have a minimum number of easily identifiable states. The binary number system satisfies this condition. However, the digital computer must still interface with humankind. This is done by converting the binary data to a decimal and character-based form that can be readily understood by humans. A minimum number of identifiable characters (say 1 and 0, or true and false) is not practical or desirable for direct human use. If this is difficult to understand, imagine trying to complete a tax form in binary or in any number system other than decimal. On the other hand, use of a computer for this purpose would not only be practical but, in many cases, highly desirable. Positional and Polynomial Representations The positional form of a number is a set of side-by-side (juxtaposed) digits given generally in fixed-point form as MSD Radix Point LSD Nr = (an–1 … a3a2a1a0 . a–1a–2a–3 … a–m)r (86.1) Integer Fraction where the radix (or base) r is the total number of digits in the number system and a is a digit in the set defined for radix r. Here, the radix point separates n integer digits on the left from m fraction digits on the right. Notice that an–1 is the most significant (highest-order) digit, called MSD, and that a–m is the least significant (lowestorder) digit, denoted by LSD. The value of the number in Eq. (86.1) is given in polynomial form by (86.2) where ai is the digit in the ith position with a weight ri . Application of Eqs. (86.1) and (86.2) follows directly. For the decimal system r = 10, indicating that there are 10 distinguishable characters recognized as decimal numerals 0, 1, 2, …,r – 1(= 9). Examples of the positional and polynomial representations for the decimal system are N10 = (d3d2d1d0.d–1d–2d–3)10 = 3017.528 and where di is the decimal digit in the ith position. Exclusive of possible leading and trailing zeros, the MSD and LSD for this number are 3 and 8, respectively. This number could have been written in a form such as N10 = 03017.52800 without altering its value but implying greater accuracy of the fraction portion. N a r a r a r a r a r a r a r a r r i i i m n n n m m r = = + + + + + + + + Ê Ë Á Á ˆ ¯ ˜ ˜ = - - - - - - - - - - Â 1 1 1 2 2 1 1 0 0 1 1 2 2 L L N di i i n 10 3 1 3 2 1 0 1 2 3 10 3 10 0 10 1 10 7 10 5 10 2 10 8 10 3000 10 7 0 5 0 02 0 008 = = ¥ + ¥ + ¥ + ¥ + ¥ + ¥ + ¥ = + + + + + = - - - - - Â . .
Unsigned Binary Number System Applying Eqs.(86. 1)and (86.2)to the binary system requires that r= 2, indicating that there are two distin- guishable characters, typically 0 and(r-1)=l, that are used. In positional representation these characters (numbers)are called binary digits or bits. Examples of the positional and polynomial notations for a binary umber are 2b1bo.b1b2b3…bm) =101101.10 MSB l×25+0×24+1×23+1×22+0×21+1×20+1×2-1+0×2-+1×2-3 32+8+4+1+0.5+0.125 where b; is the bit in the ith position. Thus, the bit positions are weighted..,16, 8, 4, 2, 1, y4, ys,.for any number consisting of integer and fraction portions. Binary numbers so represented are sometimes referred to as natural binary. In positional representation the bits on the extreme left and extreme are called the MSB (most significant bit) and LSB (least significant bit), respectively. Notice that by obtai e value of binary number a conversion from binary to decimal has been performed. The subject of radi conversion will be dealt with more extensively later. For reference purposes Table 86.1 provides the binary-to-decimal conversion for two-, three-, four-, five and six-bit binary. The six-bit binary column is only halfway completed for brevity TABLE 86.1 Binary-to-Decimal Conversion Two- Bit Decimal Three- Bit Decimal F Decimal Five- Bit Decimal Six-Bit Decimal value value 10000 100000 32 l00001 1810001034 10001135 0100 101 10110 1000 11000 1001 l1001 1010 11010 10101042 l011 l101 10101143 l1100 l101 l110l 29101101 101110 l1111311011l e 2000 by CRC Press LLC
© 2000 by CRC Press LLC Unsigned Binary Number System Applying Eqs. (86.1) and (86.2) to the binary system requires that r = 2, indicating that there are two distinguishable characters, typically 0 and (r – 1) = 1, that are used. In positional representation these characters (numbers) are called binary digits or bits. Examples of the positional and polynomial notations for a binary number are N2 = (bn–1 … b3b2b1b0 . b–1 b–2 b–3 … b–m)2 = 101101.1012 MSB LSB and where bi is the bit in the ith position. Thus, the bit positions are weighted …, 16, 8, 4, 2, 1, ½, ¼, ⅛, … for any number consisting of integer and fraction portions. Binary numbers so represented are sometimes referred to as natural binary. In positional representation the bits on the extreme left and extreme right are called the MSB (most significant bit) and LSB (least significant bit), respectively. Notice that by obtaining the value of a binary number a conversion from binary to decimal has been performed. The subject of radix (base) conversion will be dealt with more extensively later. For reference purposes Table 86.1 provides the binary-to-decimal conversion for two-, three-, four-, five-, and six-bit binary. The six-bit binary column is only halfway completed for brevity. TABLE 86.1 Binary-to-Decimal Conversion Two-Bit Decimal Three-Bit Decimal Four-Bit Decimal Five-Bit Decimal Six-Bit Decimal Binary Value Binary Value Binary Value Binary Value Binary Value 00 0 000 0 0000 0 10000 16 100000 32 01 1 001 1 0001 1 10001 17 100001 33 10 2 010 2 0010 2 10010 18 100010 34 11 3 011 3 0011 3 10011 19 100011 35 100 4 0100 4 10100 20 100100 36 101 5 0101 5 10101 21 100101 37 110 6 0110 6 10110 22 100110 38 111 7 0111 7 10111 23 100111 39 1000 8 11000 24 101000 40 1001 9 11001 25 101001 41 1010 10 11010 26 101010 42 1011 11 11011 27 101011 43 1100 12 11100 28 101100 44 1101 13 11101 29 101101 45 1110 14 11110 30 101110 46 1111 15 11111 31 101111 47 . . . . . . N bi i i m n = = ¥ + ¥ + ¥ + ¥ + ¥ + ¥ + ¥ + ¥ + ¥ = + + + + + = =- - - - - Â 2 1 2 0 2 1 2 1 2 0 2 1 2 1 2 0 2 1 2 32 8 4 1 0 5 0 125 45 625 1 5 4 3 2 1 0 1 2 3 10 . .
TABLE 86.2 NBCD Bit Patterns and Decimal Equivalent NBCD Bit pattern Decimal Decimal 0 uuutoow 89AAAAAA NNNNN NA In the natural binary system the number of bits in a unit of data is commonly assigned a name. Examples are: 4-data-bit unit: nibble(or half-byte 8-data-bit unit: byte 16-data-bit unit: two bytes(or half-word d(or four 64-data-bit unit: double-word The word size for a computer is determined by the number of bits that can be manipulated and stored in registers. The foregoing list of names would be applicable to a 32-bit computer. Unsigned Binary-Coded Decimal, Hexadecimal and Octal Systems While the binary system of numbers is most appropriate for use in computers, it has several disadvantages when used by humans who have become accustomed to the decimal system. For example, binary machine code long, difficult to assimilate, and tedious to convert to decimal. However there exist simpler ways to represent binary numbers for conversion to decimal representation. Three examples, commonly used, are natural binary coded decimal(NBCD), binary-coded hexadecimal (BCH), and binary-coded octal(BCO). These number stems are useful in applications where a digital device, such as a computer, must interface with humans. The NBCD code representation is also useful in carrying out computer arithmetic. The NBCD Representation The BCD system as used here is actually an 8, 4, 2, 1 weighted code called natural BCD or NBCD. This system uses patterns of four bits to represent each decimal position of a number and is one of several such weighted BCD code systems. The NBCD code is converted to its decimal equivalent by polynomials of the form N1o=b3×23+b2×22+b1×21+b×20 b3×8+b2×4+b1×2+b×1 for any b3b,b,b code integer. Thus, decimal 6 is represented as(0x8)+(14)+(1 x2)+(0x1), or 0110 in NBCD code. Like natural binary, NBCD code is also called"natural"because its bit positional weights are derived from integer powers of 2m. Table 86.2 shows the NBCD bit patterns for decimal integers 0 through 9 The NBCD code is currently the most widely used of the BCD codes. There are many excellent sources of information on BCD codes. One, in particular, provides a fairly extensive coverage of both weighted and unweighted BCD codes [ Tinder, 1991 e 2000 by CRC Press LLC
© 2000 by CRC Press LLC In the natural binary system the number of bits in a unit of data is commonly assigned a name. Examples are: • 4-data-bit unit: nibble (or half-byte) • 8-data-bit unit: byte • 16-data-bit unit: two bytes (or half-word) • 32-data-bit unit: word (or four bytes) • 64-data-bit unit: double-word etc. The word size for a computer is determined by the number of bits that can be manipulated and stored in registers. The foregoing list of names would be applicable to a 32-bit computer. Unsigned Binary-Coded Decimal, Hexadecimal, and Octal Systems While the binary system of numbers is most appropriate for use in computers, it has several disadvantages when used by humans who have become accustomed to the decimal system. For example, binary machine code is long, difficult to assimilate, and tedious to convert to decimal. However there exist simpler ways to represent binary numbers for conversion to decimal representation. Three examples, commonly used, are natural binarycoded decimal (NBCD), binary-coded hexadecimal (BCH), and binary-coded octal (BCO). These number systems are useful in applications where a digital device, such as a computer, must interface with humans. The NBCD code representation is also useful in carrying out computer arithmetic. The NBCD Representation The BCD system as used here is actually an 8, 4, 2, 1 weighted code called natural BCD or NBCD. This system uses patterns of four bits to represent each decimal position of a number and is one of several such weighted BCD code systems. The NBCD code is converted to its decimal equivalent by polynomials of the form N10 = b3 ¥ 23 + b2 ¥ 22 + b1 ¥ 21 + b0 ¥ 20 = b3 ¥ 8 + b2 ¥ 4 + b1 ¥ 2 + b0 ¥ 1 for any b3b2b1b0 code integer. Thus, decimal 6 is represented as (0 ¥8) + (1 ¥4) + (1 ¥2) + (0 ¥1), or 0110 in NBCD code. Like natural binary, NBCD code is also called “natural” because its bit positional weights are derived from integer powers of 2n. Table 86.2 shows the NBCD bit patterns for decimal integers 0 through 9. The NBCD code is currently the most widely used of the BCD codes. There are many excellent sources of information on BCD codes. One, in particular, provides a fairly extensive coverage of both weighted and unweighted BCD codes [Tinder, 1991]. TABLE 86.2 NBCD Bit Patterns and Decimal Equivalent NBCD NBCD Bit Pattern Decimal Bit Pattern Decimal 0000 0 1000 8 0001 1 1001 9 0010 2 1010 NA 0011 3 1011 NA 0100 4 1100 NA 0101 5 1101 NA 0110 6 1110 NA 0111 7 1111 NA NA = not allowed
Decimal numbers greater than 9 or less than 1 can be represented by the NBCD code if each digit is giver in that code and if the results are combined. For example, the number 63.98 is represented by (or converted to)NBCD code as 63 639810=01100011.10011000)BCD 1100011.10011NBCD Here, the code weights are80,40,20,10;8,4,2,1;0.8,0.4,0.2,0.1;and0.08,0.04,0.02,0.01 for the tens units,tenths, and hundredths digits, respectively, representing four decades. Conversion between binary and NBCD requires conversion to decimal as an intermediate step. For example, to convert from NBCD to binary requires that groups of four bits be selected in both directions from the radix point to form the decimal number. If necessary, zeros are added to the leftmost or rightmost ends to complete the groups of four bits as in the above example. Negative NBCD numbers can be represented either in sign-magnitude notation or 1s or 2s complement notation as discussed later Another BCD code that is used for number representation and manipulation is called excess 3 BCD (or XS3 NBCD, or simply XS3) XS3 is an example of a biased-weighted code (a bias of 3). This code is formed by ding 00112(=310)to the NBCD bit patterns in Table 86. 2. Thus, to convert XS3 to NBCD code, 0011 must be subtracted from XS3 code In four-bit quantities the XS3 code has the useful feature that when adding two numbers together in XS3 notation a carry will result and yield the correct value any time a carry results decimal (i.e, when 9 is exceeded). This feature is not shared by either natural binary or NBCD addition The Hexadecimal and Octal Systems The hexadecimal number system requires that r= 16 in Eqs.(86.1)and(86.2), indicating that there are 16 distinguishable characters in the system. By convention, the permissible hexadecimal digits are 0, 1, 2, 3,4,5, 6,7,8,9,A,B, C,D,E, and F for decimals O through 15, respectively. Examples of the positional and polynom representations for a hexadecimal number are h2h2h1h.h1h2h3…h =(AF3C8)16 with a decimal value of N=∑h6 10×162+15×16+3×16+12×16-1+8×16-2 =2803.7812510 Here, it is seen that a hexadecimal number has been converted to decimal by using Eq (86.2 The octal number system requires that r=8 in Eqs. (86.)and(86.2), indicating that there are eight distinguishable characters in this system. The permissible octal digits are 0, 1, 2, 3, 4, 5, 6, and 7, as one might expect. Examples of the application of Eqs.(86. 1)and (86. 2)are 501.74 with a decimal value of e 2000 by CRC Press LLC
© 2000 by CRC Press LLC Decimal numbers greater than 9 or less than 1 can be represented by the NBCD code if each digit is given in that code and if the results are combined. For example, the number 63.98 is represented by (or converted to) NBCD code as 6 3 . 9 8 63.9810 = 0110 0011 . 1001 1000)NBCD = 1100011.10011NBCD Here, the code weights are 80, 40, 20, 10; 8, 4, 2, 1; 0.8, 0.4, 0.2, 0.1; and 0.08, 0.04, 0.02, 0.01 for the tens, units, tenths, and hundredths digits, respectively, representing four decades. Conversion between binary and NBCD requires conversion to decimal as an intermediate step. For example, to convert from NBCD to binary requires that groups of four bits be selected in both directions from the radix point to form the decimal number. If necessary, zeros are added to the leftmost or rightmost ends to complete the groups of four bits as in the above example. Negative NBCD numbers can be represented either in sign-magnitude notation or 1’s or 2’s complement notation as discussed later. Another BCD code that is used for number representation and manipulation is called excess 3 BCD (or XS3 NBCD, or simply XS3). XS3 is an example of a biased-weighted code (a bias of 3). This code is formed by adding 00112 (= 310) to the NBCD bit patterns in Table 86.2. Thus, to convert XS3 to NBCD code, 0011 must be subtracted from XS3 code. In four-bit quantities the XS3 code has the useful feature that when adding two numbers together in XS3 notation a carry will result and yield the correct value any time a carry results in decimal (i.e., when 9 is exceeded). This feature is not shared by either natural binary or NBCD addition. The Hexadecimal and Octal Systems The hexadecimal number system requires that r = 16 in Eqs. (86.1) and (86.2), indicating that there are 16 distinguishable characters in the system. By convention, the permissible hexadecimal digits are 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, and F for decimals 0 through 15, respectively. Examples of the positional and polynomial representations for a hexadecimal number are N16 = (hn–1 … h3h2h1h0 . h–1h–2h–3 … h–m)16 = (AF3.C8)16 with a decimal value of Here, it is seen that a hexadecimal number has been converted to decimal by using Eq. (86.2). The octal number system requires that r = 8 in Eqs. (86.1) and (86.2), indicating that there are eight distinguishable characters in this system. The permissible octal digits are 0, 1, 2, 3, 4, 5, 6, and 7, as one might expect. Examples of the application of Eqs. (86.1) and (86.2) are N8 = (on–1 … o3o2o1o0 . o–1o–2o–3 … o–m)8 = 501.748 with a decimal value of N hi i i m n = = ¥ + ¥ + ¥ + ¥ + ¥ = = - - - - Â 16 10 16 15 16 3 16 12 16 8 16 2803 78125 1 2 1 0 1 2 10
TABLE 86.3 The BCh and BCO Number Binary BCH BCO Decimal Binary BCH BCO Decimal 1010 1100C 1101D l110 100001020 10 l10001 100 N 08 +0×81+1×8°+7×8-1+4×8 321.937510 When the hexadecimal and octal number systems are used to represent bit patterns in binary, they are called binary-coded hexadecimal(BCH) and binary-coded octal(BCO), respectively. These two number systems are examples of binary-derived radices. Table 86.3 lists several selected examples showing the relationships between BCO, binary, and decimal. What emerges on close inspection of Table 86.3 is that each hexadecimal digit corresponds to four binary digits and that each octal digit corresponds to three binary digits. The following example illustrates the relationships between these number systems: l0110l11ll.110112=010110l11l11.11011000 5BED8 2677 66 01011011 10110 2677.668 1471.8437510 To separate the binary digits into groups of four(for BCH)or groups of three(for BCO), counting must begin from the radix point and continue outward in both directions. Then, where needed, zeros are added to the leading and trailing ends of the binary representation to complete the MSDs and LSDs for the BCH and BCO forms Conversion between Number Systems It is not the intent of this section to cover all methods for radix(base)conversion. Rather, the plan is to provide general approaches, separately applicable to the integer and fraction portions, followed by specific examples Conversion of Integer Since the polynomial form of Eq.(86.2)is a geometrical progression, the integer portion can be represented in nested radix form. In source radix s, the nested representation is e 2000 by CRC Press LLC
© 2000 by CRC Press LLC When the hexadecimal and octal number systems are used to represent bit patterns in binary, they are called binary-coded hexadecimal (BCH) and binary-coded octal (BCO), respectively. These two number systems are examples of binary-derived radices. Table 86.3 lists several selected examples showing the relationships between BCH, BCO, binary, and decimal. What emerges on close inspection of Table 86.3 is that each hexadecimal digit corresponds to four binary digits and that each octal digit corresponds to three binary digits. The following example illustrates the relationships between these number systems: 5 B F . D 8 10110111111.110112 = 0101 1011 1111 . 1101 1000 = 5BF.D816 2 6 7 7 . 6 6 = 010 110 111 111 . 110 110 = 2677.668 = 1471.8437510 To separate the binary digits into groups of four (for BCH) or groups of three (for BCO), counting must begin from the radix point and continue outward in both directions. Then, where needed, zeros are added to the leading and trailing ends of the binary representation to complete the MSDs and LSDs for the BCH and BCO forms. Conversion between Number Systems It is not the intent of this section to cover all methods for radix (base) conversion. Rather, the plan is to provide general approaches, separately applicable to the integer and fraction portions, followed by specific examples. Conversion of Integers Since the polynomial form of Eq. (86.2) is a geometrical progression, the integer portion can be represented in nested radix form. In source radix s, the nested representation is TABLE 86.3 The BCH and BCO Number Systems Binary BCH BCO Decimal Binary BCH BCO Decimal 0000 0 0 0 1010 A 12 10 0001 1 1 1 1011 B 13 11 0010 2 2 2 1100 C 14 12 0011 3 3 3 1101 D 15 13 0100 4 4 4 1110 E 16 14 0101 5 5 5 1111 F 17 15 0110 6 6 6 10000 10 20 16 0111 7 7 7 11011 1B 33 27 1000 8 10 8 110001 31 61 49 1001 9 11 9 1001110 4E 116 78 N oi i i m n = = ¥ + ¥ + ¥ + ¥ + ¥ = = - - - - Â 8 5 8 0 8 1 8 7 8 4 8 321 9375 1 2 1 0 1 2 10
+s(a t s(a for digits a; having integer values from 0 to s-1. The nested radix form not only suggests a conversion proces but also forms the basis for computerized conversion. Consider that the number in Eq. (86.3)is to be represented in nested radix r form N,=b+r(b+r(b2+…+bm-1) (86.4) where, in general, m* n. Then, if N, is divided by r, the results are of the form R =0+ (86.5) where Q is the integer quotient rearranged as Q=b,+rb+-+ bm-I)))), and R is the remainder ro= bo A second division by r yields Q/r=Q+R,/r, where Q is arranged as Q=b2+ r(b,+..+ b-d)), and r= b,. Thus, by repeated division of the integer result Q, by r, the remainders yield(bo, b,, b2,...,bm-1), in that order. The conversion method just described, called the radix divide method, can be used to convert between any two integers of different radices. However, the requirement is that the arithmetic required by N, /r must be carried out in source radix, s. Except for source radices 10 and 2, this poses a severe problem for humans. Table 86.4 provides the recommended procedures for integer conversion. The radix divide method is suitable for computer conversion providing, of course, that the computer is programmed to carry out the arithmetic in different radice TABLE 86.4 Summary of Recommended Methods for Integer Conversion by Noncomputer Means N1n→N Radix division by radix r using Eq. (86.5 863) 10->Nm10N→ NIo by Eq(86.2)or(86.3) 6-N, radix division by r using Eq.(86.5) Special Cases for Binary Forms MMN Partition N, into groups of four bits starting from radix point, then apply Table 86 N, into groups of three bits starting from radix point, then apply Table 86.3 NBco→N2 NBco→ o→N2→N NBCD→Ns Add 0011,(=3,o)to Naacp Nxs- NNHoD Subtract 0011,(=31o) from NNECD e 2000 by CRC Press LLC
© 2000 by CRC Press LLC (86.3) for digits ai having integer values from 0 to s – 1. The nested radix form not only suggests a conversion process but also forms the basis for computerized conversion. Consider that the number in Eq. (86.3) is to be represented in nested radix r form (86.4) where, in general, m ¹ n. Then, if Ns is divided by r, the results are of the form (86.5) where Q is the integer quotient rearranged as Q0 = b1 + r(b2 + … + bm–1 ))))r and R is the remainder R0 = b0. A second division by r yields Q0 /r = Q1 + R1 /r, where Q1 is arranged as Q1 = b2 + r(b3 + … + bm–1)))r and R1 = b1. Thus, by repeated division of the integer result Qi by r, the remainders yield (b0 , b1, b2 , …, bm–1)r in that order. The conversion method just described, called the radix divide method, can be used to convert between any two integers of different radices. However, the requirement is that the arithmetic required by Ns/r must be carried out in source radix, s. Except for source radices 10 and 2, this poses a severe problem for humans. Table 86.4 provides the recommended procedures for integer conversion. The radix divide method is suitable for computer conversion providing, of course, that the computer is programmed to carry out the arithmetic in different radices. TABLE 86.4 Summary of Recommended Methods for Integer Conversion by Noncomputer Means Integer Conversion Conversion Method N10 Æ Nr Radix division by radix r using Eq. (86.5) Ns Æ N10 Eq. (86.2) or Eq. (86.3) Ns )s¹10 —> Nr )r¹10 Ns Æ N10 by Eq. (86.2) or (86.3) N10 Æ Nr radix division by r using Eq. (86.5) Special Cases for Binary Forms N2 Æ N10 Positional weighting N2 Æ NBCH Partition N2 into groups of four bits starting from radix point, then apply Table 86.3 N2 Æ NBCO Partition N2 into groups of three bits starting from radix point, then apply Table 86.3 NBCH Æ N2 Reverse of N2 Æ NBCH NBCO Æ N2 Reverse of N2 Æ NBCO NBCH Æ NBCO NBCH Æ N2 Æ NBCO NBCO Æ NBCH NBCO Æ N2 Æ NBCH NNBCD Æ NXS3 Add 00112 (= 310) to NNBCD NXS3 Æ NNBCD Subtract 00112 (= 310) from NNBCD N a s a s a s a s a s a s a a a s a s s s s n n n n n i i i n = ( + + + + ) = + + + + = + Ê Ë Á ˆ ¯ ˜ - - - - - - = - Â 1 1 2 2 1 1 0 0 012 1 0 1 1 1 L ( ( L ))))) N b r b r b b b r b r r m i i i m r = + + + + = + Ê Ë Á ˆ ¯ ˜ - - = - Â 012 1 0 1 1 1 ( ( L ))))) N r Q R r s = +
The integer conversion methods of Table 86.4 can be illustrated by the following simple examples Example 1.139→N2 R 139/2=691 69/2=341 17/2 20 01139=10001011 Example 2. 100010112- N1o By positional weights, N1o=128+8+2+1=13910 Example3.1391a→N Q R 139/8=173 17/8=21 2/8=0213910=213 Example 4. 100010112 NBco 213 Example5.213g→NBa 13Bo=010001011=100010112=10001011=8B16 Example6.2138→N 2138 N/r Q R 27/5 1/5=012138=10245 Check:1×53+2×51+4×5°=125+10+4=139 Conversion of fractions By extracting the fraction portion from Eq. (86. 2)one can write s(a1+s-(a2+…+an) (86.6) (a- ,+>a s-i+) in radix s. This is called the nested inverse radix form that provides the basis for computerized conversion. e 2000 by CRC Press LLC
© 2000 by CRC Press LLC The integer conversion methods of Table 86.4 can be illustrated by the following simple examples: Example 1. 13910 Æ N2 N/r Q R 139/2 = 69 1 69/2 = 34 1 34/2 = 17 0 17/2 = 8 1 8/2 = 4 0 4/2 = 2 0 2/2 = 1 0 1/2 = 0 1 13910 = 100010112 Example 2. 100010112 Æ N10. By positional weights, N10 = 128 + 8 + 2 + 1 = 13910 Example 3. 13910 Æ N8 N/r QR 139/8 = 17 3 17/8 = 2 1 2/8 = 0 2 13910 = 2138 Example 4. 100010112 Æ NBCO 213 010 001 011 = 213BCO Example 5. 213BCO Æ NBCH 213 8 B 213BCO = 010 001 011 = 100010112 = 1000 1011 = 8B16 Example 6. 2138 Æ N5 2138 = 2 ¥ 82 + 1 ¥ 81 + 3 ¥ 80 = 13910 N/r Q R 139/5 = 27 4 27/5 = 5 2 5/5 = 1 0 1/5 = 0 1 2138 = 10245 Check: 1 ¥ 53 + 2 ¥ 51 + 4 ¥ 50 = 125 + 10 + 4 = 13910 Conversion of Fractions By extracting the fraction portion from Eq. (86.2) one can write (86.6) in radix s. This is called the nested inverse radix form that provides the basis for computerized conversion. .( ) ( ( ))))) ( ) N as as a s sa sa a s a as s m m s m s i i s i m = + ++ = + ++ = + - - - - - - - - - - - - - - - + = Â 1 1 2 2 1 1 1 2 1 1 1 2 L L
ABLE 86.5 ry of Recommended Methods for fraction c n by Noncomputer Means Fraction Conversion Method Radix multiplication by using Eq(86.8) quation(86.2) A,m→)mNm山b(68 Special Cases for Binary Forms N2→,NB Partition. N2 into groups of four bits from radix point, then apply Table 86.3 Partition N2 into groups of three bits from radix point, then apply Table 86.3 NaH→.N2 Reverse of.N2→.NB NB→.N2 Reverse of.N2→.NB NBa→. NuCO . NECH→N2→NBco NB→NBc If the fraction in Eq (86.6) is represented in nested inverse radix r form, then "(6 +b-P)) (86.7) (b+∑br“) for any fraction represented in radix r. Now, if N, is multiplied by r, the result is of the for N.×r=I+F (86.8) where I is the product integer, I,= b-I, and Fo is the product fraction arranged as F=r(b-2+r(b-3+.+ b)))),. By repeated multiplication by r of the remaining fractions F, the resulting integers yield(b-,b-2 b33…bn), in that order The conversion just described is called the radix multiply method and is perfectly general for converting between fractions of different radices. However, as in the case of integer conversion, the requirement is that the arithmetic required by N, Xr must be carried out in source radix, s For noncomputer use by humans, this procedure is usually limited to fraction conversions N1o -N, where the source radix is 10( decimal). The recommended methods for converting between fractions of different radices are given in Table 86.5. The radix multiply method is well suited to computer use. 4 For any integer of radix s, there exists an exact representation in radix r. This is not the case for a fraction lose conversion is a geometrical progression that never converges. Terminating a fraction conversion at digits(to the right of the radix point)results in an error or uncertainty. In decimal, this error is given by r+ a n+]) ∑ where the quantity in brackets approaches the value of a_+ 1. Therefore, terminating a fraction conversion at n digits from the radix point results in an error with bounds e 2000 by CRC Press LLC
© 2000 by CRC Press LLC If the fraction in Eq. (86.6) is represented in nested inverse radix r form, then (86.7) for any fraction represented in radix r. Now, if Ns is multiplied by r, the result is of the form .Ns ¥ r = I + F (86.8) where I is the product integer, I1 = b–1, and F0 is the product fraction arranged as F1 = r –1(b–2 + r –1(b–3 + … + b–p))))r . By repeated multiplication by r of the remaining fractions Fi , the resulting integers yield (b–1, b–2 , b–3 , … b–m)r , in that order. The conversion just described is called the radix multiply method and is perfectly general for converting between fractions of different radices. However, as in the case of integer conversion, the requirement is that the arithmetic required by .Ns ¥ r must be carried out in source radix, s. For noncomputer use by humans, this procedure is usually limited to fraction conversions N10 Æ Nr , where the source radix is 10 (decimal). The recommended methods for converting between fractions of different radices are given in Table 86.5. The radix multiply method is well suited to computer use. For any integer of radix s, there exists an exact representation in radix r. This is not the case for a fraction whose conversion is a geometrical progression that never converges. Terminating a fraction conversion at n digits (to the right of the radix point) results in an error or uncertainty. In decimal, this error is given by where the quantity in brackets approaches the value of a–n + 1. Therefore, terminating a fraction conversion at n digits from the radix point results in an error with bounds TABLE 86.5 Summary of Recommended Methods for Fraction Conversion by Noncomputer Means Fraction Conversion Conversion Method .N10 Æ .Nr Radix multiplication by using Eq. (86.8) .Ns Æ .N10 Equation (86.2) or Eq. (86.6) .Nr )s¹10 Æ .Nr )r¹10 Ns Æ Ns10 by Eq. (86.2) or Eq. (86.6) N10 Æ Nr radix multiply by Eq. (86.8) Special Cases for Binary Forms .N2 Æ .NBCH Partition .N2 into groups of four bits from radix point, then apply Table 86.3 .N2 Æ .NBCO Partition .N2 into groups of three bits from radix point, then apply Table 86.3 .NBCH Æ .N2 Reverse of .N2 Æ .NBCH .NBCO Æ .N2 Reverse of .N2 Æ .NBCO .NBCH Æ .NBCO .NBCH Æ .N2 Æ .NBCO .NBCO Æ .NBCH .NBCO Æ .N2 Æ .NBCH . ( ( ))))) ( ) N r b r b b r b b r r p r i i r i p = + + + = + - - - - - - - - - + = Â 1 1 1 2 1 1 1 2 L e10 1 1 2 2 1 = + + + = + È Î Í Í ˘ ˚ ˙ ˙ - - -( ) + -( ) + -( ) + -( ) + - - -( ) + -( ) + = • Â a r a r a r r a a r n n n n n n n n n i n i i r L