Transcript CA-sp06-m09-NumReps - FAMU

FAMU-FSU College of Engineering
Computer
Architecture
EEL 4713/5764, Spring 2006
Dr. Michael Frank
Module #9 – Number Representations
1
Part III
The Arithmetic/Logic Unit
June 2005
Computer Architecture, Instruction-Set Architecture
Slide 2
III The Arithmetic/Logic Unit
Overview of computer arithmetic and ALU design:
• Review representation methods for signed integers
• Discuss algorithms & hardware for arithmetic ops
• Consider floating-point representation & arithmetic
Topics in This Part
Chapter 9
Number Representation
Chapter 10 Adders and Simple ALUs
Chapter 11 Multipliers and Dividers
Chapter 12 Floating-Point Arithmetic
June 2005
Computer Architecture, Instruction-Set Architecture
Slide 3
9 Number Representation
Arguably the most important topic in computer arithmetic:
• Affects system compatibility and ease of arithmetic
• Two’s complement, flp, and unconventional methods
Topics in This Chapter
9.1 Positional Number Systems
9.2 Digit Sets and Encodings
9.3 Number-Radix Conversion
9.4 Signed Integers
9.5 Fixed-Point Numbers
9.6 Floating-Point Numbers
June 2005
Computer Architecture, Instruction-Set Architecture
Slide 4
9.1 Positional Number Systems
Representations of natural numbers {0, 1, 2, 3, …}
||||| ||||| ||||| ||||| ||||| ||
27
11011
XXVII
sticks or unary code
radix-10 or decimal code
radix-2 or binary code
Roman numerals
Fixed-radix positional representation with k digits
k–1
Value of a number: x = (xk–1xk–2 . . . x1x0)r = S xi r i
i=0
For example:
27 = (11011)two = (124) + (123) + (022) + (121) + (120)
Number of digits for [0, P]: k = logr (P + 1) = logr P + 1
June 2005
Computer Architecture, Instruction-Set Architecture
Slide 5
Unsigned Binary Integers
Overflow marker
0000
1111
1110
15
0001
0
1
14
0010
2
1101
0011
13
1100
12
1011
Turn x notches
counterclockwise
to add x
3
Inside: Natural number
Outside: 4-bit encoding
11
10
1010
0100
0101
12
11
10
15
1
2
0
3
4
5
9 8 7
6
6
9
1001
4
5
Increasing
values
14
13
8
1000
7
0110
0111
Turn y notches
clockwise
to subtract y
Figure 9.1 Schematic “roulette wheel” representation
of 4-bit code for integers in [0, 15].
June 2005
Computer Architecture, Instruction-Set Architecture
Slide 6
Representation Range and Overflow

Overflow region max
max  Overflow region
Numbers smaller
than max 
Numbers larger
than max 
Finite set of representable numbers
Figure 9.2 Overflow regions in finite number representation systems.
For unsigned representations covered in this section, max – = 0.
Example 9.2, Part d
Discuss if overflow will occur when computing 317 – 316 in a number
system with k = 8 digits in radix r = 10.
Solution
The result 86 093 442 is representable in the number system which
has a range [0, 99 999 999]; however, if 317 is computed en route to
the final result, overflow will occur.
June 2005
Computer Architecture, Instruction-Set Architecture
Slide 7
9.2 Digit Sets and Encodings
Conventional and unconventional digit sets
 Decimal digits in [0, 9]; 4-bit BCD, 8-bit ASCII
 Hexadecimal, or hex for short: digits 0-9 & a-f (or A-F)
 Conventional ternary digit set in [0, 2]
Conventional digit set for radix r is [0, r – 1]
Symmetric ternary digit set in [–1, 1]
 Conventional binary digit set in [0, 1]
Redundant digit set [0, 2], encoded in 2 bits
( 0 2 1 1 0 )two and ( 1 0 1 0 2 )two both represent 22
June 2005
Computer Architecture, Instruction-Set Architecture
Slide 8
The Notion of Carry-Save Addition
Digit-set combination: {0, 1, 2} + {0, 1} = {0, 1, 2, 3} = {0, 2} + {0, 1}
This bit
being 1
represents
overflow
(ignore it)
Carry-save
input
Carry-save
addition
Two
carry-save
inputs
Binary input
Carry-save
0
output
0
Carry-save
addition
0
a. Carry-save addition.
b. Adding two carry-save numbers.
Figure 9.3 Adding a binary number or another
carry-save number to a carry-save number .
June 2005
Computer Architecture, Instruction-Set Architecture
Slide 9
9.3 Number Radix Conversion
Two ways to convert numbers from an old radix r to a new radix R
 Perform arithmetic in the new radix R
Suitable for conversion from radix r to radix 10
Horner’s rule:
(xk–1xk–2 . . . x1x0)r = (…((0 + xk–1)r + xk–2)r + . . . + x1)r + x0
(1 0 1 1 0 1 0 1)two = 0 + 1  1  2 + 0  2  2 + 1  5  2 + 1 
11  2 + 0  22  2 + 1  45  2 + 0  90  2 + 1  181
 Perform arithmetic in the old radix r
Suitable for conversion from radix 10 to radix R
Divide the number by R, use the remainder as the LSD
and the quotient to repeat the process
19 / 3  rem 1, quo 6 / 3  rem 0, quo 2 / 3  rem 2, quo 0
Thus, 19 = (2 0 1)three
June 2005
Computer Architecture, Instruction-Set Architecture
Slide 10
Expression for Digits using
Modulo Method


x  (  ...   x / R  mod R  / R  mod R... / R  mod R,


  x / R  mod R  / R  mod R,


 x / R  mod R,
x mod R ) R
October 2005
Michael Frank, FAMU-FSU College of
Engineering
11
A Third Method


Also uses modulo arithmetic in the old radix r.
First, find k = logR x,



i.e., Rk is greatest integer power of R that is ≤ x.
Digit #k (MSD) is then just the quotient x/Rk
Repeat the process using the remainder
(x mod Rk) to find later digits in the sequence.
October 2005
Michael Frank, FAMU-FSU College of
Engineering
12
Digits with Third Method
x  (  x / R k  ,
 x mod R k R k 1  ,


 x mod R k mod R k 1






R k 2  ,



 
  x mod R  mod R  mod R


x mod R k
k
October 2005
mod R 3 mod R 2
2
Michael Frank, FAMU-FSU College of
Engineering

R  ,

)R
13
Justifications for Radix Conversion Rules
( xk 1 xk  2
x0 )r  xk 1r k 1  xk  2 r k  2 
 x1r  x0
 x0  r ( x1  r ( x2  r ( )))
Justifying Horner’s rule.
x
Binary representation of x/2
Figure 9.4
June 2005
0
x mod 2
Justifying one step of the conversion of x to radix 2.
Computer Architecture, Instruction-Set Architecture
Slide 14
9.4 Signed Integers
 We dealt with representing the natural numbers
 Signed or directed whole numbers = integers
{ . . . , 3, 2, 1, 0, 1, 2, 3, . . . }
 Signed-magnitude representation
+27 in 8-bit signed-magnitude binary code 0 0011011
–27 in 8-bit signed-magnitude binary code 1 0011011
–27 in 2-digit decimal code with BCD digits 1 0010 0111
 Biased representation
Represent the interval of numbers [N, P] by the unsigned
interval [0, P + N]; i.e., by adding N to every number
June 2005
Computer Architecture, Instruction-Set Architecture
Slide 15
Two’s-Complement Representation
With k bits, numbers in the range [–2k–1, 2k–1 – 1] represented.
Negation is performed by inverting all bits and adding 1.
0000
1111
+0
–1
1110
0001
+1
0010
–2
+2
Increasing
values
1101
–3
_
–4
1100
1011
Turn x notches
counterclockwise
to add x
0011
+
–5
+3
+4
+5
–6
1001
0100
–8
1000
+7
–4
–5
–6
0101
+6
–7
1010
–2
–3
0110
0111
–1
1
2
0
3
4
5
–7 –8 7
6
Turn y notches
Turn 16 – y notches
clockwise to
counterclockwise
add
y (subtractyy)
to–subtract
Overflow marker
Figure 9.5 Schematic roulette wheel representation of 4-bit 2’scomplement code for integers in [–8, +7].
June 2005
Computer Architecture, Instruction-Set Architecture
Slide 16
Another way to think about
two’s complement representation

All we’re really doing is taking the block of all bit patterns that
start with 1 and re-mapping it, shifting it over to cover the part of
the number line located just to the left of 0.



While leaving them in the same order relative to each other.
Basically, we’re subtracting 2n from the values of all these patterns.
We’re re-valuing the high-order bit position from +2n-1 to −2n-1!
−8 −7 … −1 0 +1 … +7 +8 +9 … +15
0000 0001
October 2005
…
0111 1000 1001
Michael Frank, FAMU-FSU College of
Engineering
…
1111
17
Conversion from 2’s-Complement to Decimal
Example 9.7
Convert x = (1 0 1 1 0 1 0 1)2’s-compl to decimal.
Solution
Given that x is negative, one could change its sign and evaluate –x.
Shortcut: Use Horner’s rule, but take the MSB as negative
–1  2 + 0  –2  2 + 1  –3  2 + 1  –5  2 + 0  –10  2 + 1
 –19  2 + 0  –38  2 + 1  –75
Sign Change for a 2’s-Complement Number
Example 9.8
Given y = (1 0 1 1 0 1 0 1)2’s-compl, find the representation of –y.
Solution
–y = (0 1 0 0 1 0 1 0) + 1 = (0 1 0 0 1 0 1 1)2’s-compl
June 2005
Computer Architecture, Instruction-Set Architecture
(i.e., 75)
Slide 18
Two’s-Complement Addition and Subtraction
x
k
/
c in
Adder
y
k
/
k
/
k
/
xy
c out
y or
y
AddSub
Figure 9.6
June 2005
Binary adder used as 2’s-complement adder/subtractor.
Computer Architecture, Instruction-Set Architecture
Slide 19
9.5 Fixed-Point Numbers
Positional representation: k whole and l fractional digits
Value of a number: x = (xk–1xk–2 . . . x1x0 . x–1x–2 . . . x–l )r = S xi r i
For example:
2.375 = (10.011)two = (121) + (020) + (021) + (122) + (123)
Numbers in the range [0, rk – ulp] representable, where ulp = r –l
Fixed-point arithmetic (addition & subtraction) same as integer arithmetic
(radix point implied, not explicit)
Two’s complement properties (including sign change) hold here as well:
(01.011)2’s-compl = (–021) + (120) + (02–1) + (12–2) + (12–3) = +1.375
(11.011)2’s-compl = (–121) + (120) + (02–1) + (12–2) + (12–3) = –0.625
June 2005
Computer Architecture, Instruction-Set Architecture
Slide 20
Fixed-Point 2’s-Complement Numbers
1.111
–.125
1.110
0.000
+0
–.25
0.001
+.125
0.010
+.25
1.101
0.011
–.375
1.011
+
_
–.5
1.100
+.5
0.100
+.625
–.625
0.101
+.75
–.75
1.010
+.375
–.875
1.001
–1
1.000
+.875
0.110
0.111
Figure 9.7 Schematic representation of 4-bit 2’s-complement
encoding for (1 + 3)-bit fixed-point numbers in the range [–1, +7/8].
June 2005
Computer Architecture, Instruction-Set Architecture
Slide 21
Radix Conversion for Fixed-Point Numbers
Convert the whole and fractional parts separately.
To convert the fractional part from an old radix r to a new radix R:
 Perform arithmetic in the new radix R
Evaluate a polynomial in r –1: (.011)two = 0  2–1 + 1  2–2 + 1  2–3
Simpler: View the fractional part as integer, convert, divide by r l
(.011)two = (?)ten
Multiply by 8 to make the number an integer: (011)two = (3)ten
Thus, (.011)two = (3 / 8)ten = (.375)ten
 Perform arithmetic in the old radix r
Multiply the given fraction by R, use the whole part as the MSD
and the fractional part to repeat the process
(.72)ten = (?)two
0.72  2 = 1.44, so the answer begins with 0.1
0.44  2 = 0.88, so the answer begins with 0.10
June 2005
Computer Architecture, Instruction-Set Architecture
Slide 22
9.6 Floating-Point Numbers
Useful for applications where very large and very small
numbers are needed simultaneously
 Fixed-point representation must sacrifice precision
for small values to represent large values
x = (0000 0000 . 0000 1001)two
Small number
y = (1001 0000 . 0000 0000)two
Large number
 Neither y2 nor y / x is representable in the format above
 Floating-point representation is like scientific notation:
20 000 000 = 2  10 7
0.000 000 007 = 7  10–9
Significand
June 2005
Exponent base
Exponent
Computer Architecture, Instruction-Set Architecture
Also, 7E9
Slide 23
ANSI/IEEE Standard Floating-Point Format (IEEE 754)
Revision (IEEE 754R) is being considered by a committee
Short (32-bit) format
8 bits,
bias = 127,
–126 to 127
23 bits for fractional part
(plus hidden 1 in integer part)
Sign Exponent
11 bits,
bias = 1023,
–1022 to 1023
Short exponent range is –127 to 128
but the two extreme values
are reserved for special operands
(similarly for the long format)
Significand
52 bits for fractional part
(plus hidden 1 in integer part)
Long (64-bit) format
Figure 9.8
June 2005
The two ANSI/IEEE standard floating-point formats.
Computer Architecture, Instruction-Set Architecture
Slide 24
Short and Long IEEE 754 Formats: Features
Table 9.1 Some features of ANSI/IEEE standard floating-point formats
Feature
Word width in bits
Significand in bits
Significand range
Exponent bits
Exponent bias
Zero (±0)
Denormal
Single/Short
32
23 + 1 hidden
[1, 2 – 2–23]
8
127
e + bias = 0, f = 0
e + bias = 0, f ≠ 0
represents ±0.f  2–126
e + bias = 255, f = 0
e + bias = 255, f ≠ 0
e + bias  [1, 254]
e  [–126, 127]
represents 1.f  2e
Double/Long
64
52 + 1 hidden
[1, 2 – 2–52]
11
1023
e + bias = 0, f = 0
e + bias = 0, f ≠ 0
represents ±0.f  2–1022
e + bias = 2047, f = 0
e + bias = 2047, f ≠ 0
e + bias  [1, 2046]
e  [–1022, 1023]
represents 1.f  2e
min
2–126  1.2  10–38
2–1022  2.2  10–308
max
 2128  3.4  1038
 21024  1.8  10308
Infinity (∞)
Not-a-number (NaN)
Ordinary number
June 2005
Computer Architecture, Instruction-Set Architecture
Slide 25
Hand-Converting Numbers to
Binary Floating-Point



Example: convert 5.614106 to 32-bit floating point.
log2 5,614,000 = 22.420… Take the floor  22
Base-2 exponent is 22, add bias (127)  149


Divide original number by 222 or 4,194,304



Gives us 1.33848190308 (significand)
Multiply fractional part by 223 or 8,388,608


Convert to 8-bit binary  1001,0101 for exponent field
Gives 2839392
Convert this to a 23-bit binary number 
010,1011,0101,0011,0110,0000
Now just put the pieces together!
October 2005
Michael Frank, FAMU-FSU College of
Engineering
26
Conversion example, cont.

The fields are:




Thus, the full 32-bit binary word is:
sgn


Sign field (sgn) = 0 (positive)
Exponent field (exp)= 1001,0101 (22+127 = 149)
Significand field (sig) = 010,1011,0101,0011,0110,0000
exp
sig
0100,1010,1010,1011,0101,0011,0110,0000
Check answer: (1)  2
sgn
exp 127
 (1  sig  2
23
)
 1 2  (1  .33848190308)
22
October 2005
 5.614 10
Michael Frank, FAMU-FSU College of
Engineering
6
27