Transcript Subject - Western Connecticut State University

Arithmetics
Computer Architecture
CS 215
Data Representation
 Method of storing data using binary
codes
 Fixed Point Numbers
 Floating Point Numbers
 Overflow
Fixed Point Numbers
 Range

Distance between highest and lowest
values
 Precision

Distance between two adjacent values
 Error

Half the precision
Fixed Point Numbers
 Example:






Assume three digit unsigned decimal
numbers
Lowest value: 0.00
Highest value: 9.99
Range: [0.00, 9.99] = 9.99
Precision: 1.23 – 1.22 = 0.01
Error: 0.01 / 2 = 0.005
Associate Law of Algebra &
Digital Representations
 Assume one digit numbers
 Range: [-9, 9]
 Try … 7 + 4 – 3
 7 + (4 – 3) = 7 + 1 = 8
 (7 + 4) – 3 = 11 - 3 = Overflow!
 Oops!
Associate Law of Algebra &
Digital Representations
 Either identify overflow and terminate
process, or …
 Repeat computation with higher
precision numbers
Radix Number Systems
 Radix = Base
 Numbers of possible choices for each digit
 Most systems use base 2 while many
calculators use base 10 internally
 Octal

Base 8
 Hexadecimal

Base 16
Radix Number Systems
 Weighted position code
 Polynomial method of conversion
Value  i  m bi  k
n 1
i
Radix Number Systems
1234.567
Most
significant
digit
Least significant
digit
Converting Among Radices
 Converting integer part

Remainder method
 Converting fractional part

Multiplication method
Remainder Method
(23)10 = (10111)2
Integer
 23/2 = 11
 11/2 = 5
 5/2 = 2
 2/2 = 1
 1/2 = 0
Remainder
1
1
1
0
1
Multiplication Method
(.375)10 = (.011)2
 .375 x 2 = 0.75
 .75 x 2 = 1.5
 .5 x 2 = 1.0
Try this …
 Convert the following to radix 2
Show all work!
1.
2.
3.
(123.875)10
(11.01)10
(10.2)10
Non-terminating Fractions
 Converting (.2)10 to a radix 2
 .2 x 2 = 0.4
 .4 x 2 = 0.8
 .8 x 2 = 1.6
 .6 x 2 = 1.2
 .2 x 2 = 0.4
 And so on …
Signed Fixed Point Numbers
Encoding Schemes …
 Signed Magnitude
 One’s Compliment
 Two’s Compliment
 Excess Representation
 Binary Coded Decimal
Signed Magnitude
 Aka sign & magnitude
 First bit for sign

0 is positive, 1 is negative
 Remaining bits for absolute magnitude
 Two different zeros (+0 and –0)
 28 – 1 = 255 different numbers
 (+12)10 = (00001100)2
One’s Compliment
 Method


Negate the positive of the number
Compliment all of the bits
 Not commonly used
 Difficult for comparisons (2 zeros)
 28 – 1 = 255 different numbers
Two’s Compliment
 Method




Negate the positive of the number
Compliment all of the bits
Add binary 1
Discard any carry-out
 Only one zero
 28 = 256 different numbers
Excess Representation
 Aka biased representation
 Number is treated as unsigned
 Bias is lowest value in the range
 Shifted in value by subtracting bias from it
 Only one zero
 28 = 256 different numbers
 Excess 127 …

(-127)10 = (00000000)2
Try this …
Convert the following numbers to one’s
compliment, two’s compliment and excess
127
64
75
-101
0
FYI
Binary Coded Decimal
 Each decimal digit gets four bits
 9’s compliment

Subtract each digit from 9
 10’s compliment

Add 1 to the 9’s compliment
FYI
Binary Coded Decimal
 9’s & 10’s compliment

0000 0101 0001 0000
(0)10 (5)10 (1)10 (0)10
 What would (–510)10 look like in 9’s
compliment form?
 10’s Compliment?
Floating Point Numbers
 Allows for a large range of expressible
numbers using a small quantity of digits
 Uses different digits for precision and
range
Exponent
 Ex.

+6.023 x 1023
Mantissa
(significand)
Range & Precision
 To increase range …


Use fewer digits for mantissa, more for
exponent
Reduces precision
 Or …


Increase base
Increases precision of smaller numbers;
decrease precision of larger numbers
Normalization & the Hidden Bit
 All floating point numbers are
normalized
 Radix point is set to right of the
leftmost nonzero digit (in base 2)
 This results in a 1 as the leftmost digit
in the mantissa
 Dropping this 1 (hidden bit) increases
precision
Normalization & the Hidden Bit
Normalize and account for a hidden bit in
the following …
 0.3 x 102
Floating Point Example
 Mantissa



Signed magnitude form
Base 2
Three hexadecimal digits
 Exponent




Three bits
Base 2
Excess-4
Simplifies addition & subtraction
Floating Point Example
 What would (358)10 look like in our
format?
Floating Point Example
 Step 1: Convert to base 16
Integer Remainder
358/16
22
6
22/16
1
6
1/16
0
1
 (358)10 = (166)16
Floating Point Example
 Step 2: Normalize
(0 0 0 10 1 1 0 0 1 1 0)16 x 20
= (. 10 1 1 0 0 1 1)16 x 29
Hidden bit
 Step 3: Represent exponent using bits
011
Excess 4 + 1 0 0
111
(+3)10
(+4)10
Floating Point Example
 Step 4: Express mantissa using bits
011001100000
 Result:
0111011001100000
Sign bit
Exponent
Mantissa
Error in Floating Point Numbers
 In our example …



The base (b) is 2
There are 3 significant digits (s)
The range of exponents [m, M] is [-22, 221]
Error in Floating Point Numbers
 5 characteristics …





Number of representable numbers
Number with largest magnitude
Number with smallest magnitude
Largest gap between successive numbers
Smallest gap between successive numbers
FYI
Representable Numbers
2  ((M  m)  1)  (b 1)  b
s 1
1
Sign bit
Number of exponents
First digit of fraction
Remaining digits of fraction
Zero
FYI
Largest Magnitude
 Largest exponent

bM
 Largest fraction




All 1’s, or …
(1 - b-s)
Largest magnitude is …
bM x (1 - b-s)
FYI
Smallest Magnitude
 Smallest exponent

bm
 Smallest non-zero normalized fraction

Which is 1, or …

b-1
 Smallest magnitude is …

bm  b-1 = bm-1
FYI
Largest Gap
 Largest exponent, and …
 Least significant bit changes
 bM x b-s = bM-s
FYI
Smallest Gap
 Smallest exponent, and …
 Least significant bit changes
 bm x b-s = bm-s
FYI
In our example …
 Largest magnitude

bM x (1 - b-s) =

21 x (1 - 2-3) = 7/4
 Largest gap

 Smallest gap
 Smallest magnitude

bM-s = 21-3 = 1/4

bm-s = 2-2-3 = 1/32
bm-1 = 2-2-1 = 1/8
 Representable numbers



2 x ((M - m) + 1) x (b - 1) x bs-1 + 1
= 2 x ((1 - (-2)) + 1) x (2 - 1) x 23-1 + 1
= 33
FYI
Error in Floating Point Numbers
 Relative error is
approximately the
same for all numbers
b M s

M
s
b  (1  b )
ms
b

m
s
b  (1  b )
s
b

s
1 b
1
s
b 1
Unsigned Multiplication
x
1
0 0
1 1 0
1 0 0 0
1
1
1
1
0
1
1
1
0
1
0
0
0 1
1 1
0 1
1
Add
Shift, then add
Shift
Shift, then add
1 1 1
Unsigned Multiplication
m3 m2 m1 m0
4-bit Adder
c
a3 a2 a1 a0
Shift & Add
Control Logic
q3 q2 q1 q0
Unsigned Multiplication
C
A
Q
0
0 0 0 0
1 0 1 1
0
0
1 1 0 1
0 1 1 0
1 0 1 1
1 1 0 1
Add M to A
Shift
1
0
0 0 1 1
1 0 0 1
1 1 0 1
1 1 1 0
Add M to A
Shift
0
0 1 0 0
1 1 1 1
Shift
1
0
0 0 0 1
1 0 0 0
1 1 1 1
1 1 1 1
Add M to A
Shift
Multiplicand
1 1 0 1
Product
Initial
values
Unsigned Division
 How would you do this?
 Could you do this via multiplication?
 Break into teams of three and spend 15
minutes discussing how you would
accomplish this
Signed Multiplication
x
0
0 0
0 0 0
0 0 0 0
1
0
1
0
0
0
1
1
0
1
0
0
1 1
0 1
1 1
0
1 1 1
(-1)10
(+1)10
X
(+15)10
Signed Multiplication
?
1 1 1 1
x
1 1 1 1
0 0 0 0
0 0 0 0
0 0 0 0
1 1 1 1
1
0
1
0
0
0
1
1
0
1
0
0
1 1
0 1
1 1
0
1 1 1
Sign extended
(-1)10
(+1)10
(-1)10
What about overflow?

Floating Point:
Addition & Subtraction
 Virtue of using sign bit, exponent in
excess notation, magnitude …


Numbers can be logically compared
without unpacking
Why?
Floating Point:
Addition & Subtraction
 Adjust exponents (and magnitudes) so
both operands are set to higher
exponent
 Add or subtract signed magnitudes
 Normalize
Floating Point:
Multiplication & Division
 Sign


Same? Set to 0
Different? Set to 1
 Exponents


Add for multiplication
Subtract divisor exponent from dividend exponent
 Magnitude

Multiply/Divide unsigned magnitudes
 Normalize
Floating Point:
Multiplication & Division
 Use this approach to perform …

(+.110 x 25) / (+.100 x 24)
 Any problems?
 What should the answer be?
 How could you modify the previous
method to account for this?
IEEE 754 Floating Point Standard
 Single & Double Precision
 Denormalized
 Single & Double Extended
Single & Double Precision
32 bits
Single
Precision
8 bits
23 bits
Exponent
Fraction
Sign
(1 bit)
Double
Precision
64 bits
11 bits
52 bits
Single & Double Precision
Sign
(1 bit)
Single
Precision
32 bits
8 bits
23 bits
Exponent
Fraction
 Sign bit
 8-bit excess 127 exponent

00000000 and 11111111 for special cases
 23-bit normalized fraction with hidden bit
Single & Double Precision
 Sign bit
 11-bit excess 1023 exponent

00000000000 and 11111111111 for special
cases
 Sign
52-bit normalized fraction with hidden bit
(1 bit)
Double
Precision
64 bits
11 bits
52 bits
Five Basic Number Types
 Nonzero normalized
 “Clean zero”


All 0’s in exponent and fraction
Sign bit can be 0 or 1
 Infinity



All 1’s in exponent
All 0’s in fraction
Sign bit can be 0 or 1
Five Basic Number Types
 Not a Number (NaN)



Sign bit is 0 or 1
Exponent all 1’s
Fraction non-zero
 Denormalized “Dirty zero”




Sign bit is 0 or 1
Exponent all 0’s
Fraction actual magnitude
No hidden bit
Single & Double Extended
 Extend width of exponent and fraction
 Depends upon implementation
FYI
Character Codes
 ASCII

American Standard Code for Information
Interchange
 EBCDIC

Extended Binary Coded Decimal
Interchange Code
 Unicode