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