Transcript ppt - K.f.u.p.m ocw

Dr. Alaaeldin A. Amin
Computer Engineering
Department
E-mail:
[email protected]
http://www.ccse.kfupm.edu.sa/~
amin
Review - Outline
•
•
•
•
Machine Number Systems (Fixed radix
Positional)
Fixed Point Number Representation
Base Conversion
Representation of Signed Numbers
– Signed Magnitude (Sign and Magnitude)
– Complement Representation
* Radix Complement (2`s Complement)
* Diminished Radix Complement
•
•
Precision Extension
Arithmetic Shifts
COE 522
Dr. A. Amin
Machine Number Systems?
Fractional Part
Integral Part
X = xk-1 xk-2 ... x1 x0 . x-1 x-2 ... x-m
k 1
=
 xi r
i
i m
• Since Numbers Are Stored in Registers of
Fixed Length
– There is a Finite Number of Distinct Values that
Can be Represented in a Register
– Let Xmax & Xmin Denote The Largest &
Smallest Representable Numbers
– Xmax = rk-1 For an Integral # of k-Digits
– Xmax = 1 - r -m For a Fractional # of m-Digits
– Xmax = rk - r -m For a # of k- Integral Digits and
m- Fractional Digits
– Xmin = 0
– Number of Possible Distinct Values = r k+m
COE 522
Dr. A. Amin
Number Radix Conversion
• Let X be an Integer  XB in Radix B System
 XA in Radix A System
•
Assumptions
• XB has n digits
XB = (bn-1………..b2 b1 b0)B ,
where bi is a digit in radix B system,
i.e. bi  {0, 1, ….. , “B-1”}
• XA has m digits
XA =(am-1………..a2 a1 a0)A
where ai is a digit in radix A system,
i.e.
ai  {0, 1, ….., “A-1”}
Problem Statement
XB =(bn-1………..b2 b1 b0)B  (am-1………..a2 a1 a0)A
Unknowns
Knowns
COE 522
Dr. A. Amin
XB = am-1*Am-1+……+ a2*A2 + a1*A1 + a0*A0
Divisible by A
Not Divisible by A
•
Where ai  {0-(A-1)}
•
Accordingly, dividing XB by A, the remainder will be
a0.
XB = Q0.A+a0
Where, Q0 = am-1*Am-2 +…+ a2*A1
Divisible by A
Likewise 
+ a1*A0
Not Divisible by A
Q0 = Q1A+a1
 Get a1
Q1 = Q2A+a2
 Get a2
…………………………………
Qm-3 = Qm-2A+am-2  Get am-2
Qm-2 = Qm-1A+am-1  Get am-1
Where Qm-1= 0  Stopping Criteria
COE 522
Dr. A. Amin
Representation of Signed Numbers
Three Main Systems
1. Signed Magnitude (Sign and Magnitude)
2. Complement Representation
–
–
Radix Complement (2`s Complement)
Diminished Radix Complement
Signed Magnitude
Sign
Digit
0 +ive
1 -ive
• Independent Representation of The Sign and
The Magnitude
• Symmetric Range of Representation
{ -(2n-1 -1) : +(2n-1 -1) }
• Two Representations for 0  {+0 , -0}
 Nuisance for Implementation
• Addition/Subtraction Harder To Implement
• Multiplication & Division Less Problematic
• For Base R Sign Digit May Be
– 0  +ive Numbers
– R-1  -ive Numbers {Inefficient Space
Utilization}
COE 522
Dr. A. Amin
Representation of Signed Numbers
• Alternatively
– 0, 1, …, (R/2 - 1)  +ive Numbers
– R/2, R/2+1, …., (R-1)  -ive Numbers  More
Complex Sign Detection if r not power of 2
COE 522
Dr. A. Amin
Representation of Signed Numbers
Complement Representation
• Positive Numbers (+N) Are Represented in
Exactly the Same Way as in Signed Magnitude
System
• Negative Numbers (-N) Are Represented by
the Complement of N (N`)
Define the Complement of a number N (N`) as:
N` = M -N
Where M= Some Constant
• This representation satisfies the Basic
Requirement That:
-(-N ) = ( N` )` = M- (M-N) = N
Adding 2 Numbers; X (+ive) and Y (-ive) :
IF Y > X
• Result Z is -ive, i.e. Complement Represented:
Z = X + (M-Y) =
= M -(Y-X) = Correct Answer
in Complement Form
+ive
COE 522
Dr. A. Amin
Representation of Signed Numbers
IF Y < X
• Result Z is +ive:
Z = X + (M-Y)
= M +(X-Y)
+ive
Correct Answer = X - Y
M Chosen To
Eliminate/Simplify
Correction Step
Requirements of M:
1- Simple Complement Calculations
2- Simplify/Eliminate Addition Correction
Steps
• Let xi be the Complement of a single Digit xi
xi  ( r  1 )  xi
• IF
X = xk-1 xk-2 ... x1 x0 . x-1 x-2 ... x-m
• Define X = xk-1 xk-2 ... x1 x0 . x-1 x-2 ... x-m
COE 522
Dr. A. Amin
X
x
+X
x
k -1
k -1
x
x
k -2
k -2
...
x
...
x
1
1
x
x
0
0
Representation of Signed Numbers
Radix Complement:
M= r k
N`= rk-N
= N + ulp
(Simple Computation)
– Computing N ` is independent of k
– Computing the Previous Addition Requires No
Corrections
Z = M + (X-Y) = r k + (X-Y)
Discard End Carry
(Beyond Word Size)
Diminished Radix Complement: M= r k - ulp
N ` = r k - ulp - N
= N
(Simplest Computation)
– Computing the Previous Addition Requires
Simple Correction of Adding ulp
Z = M + (X-Y) = r k + (X-Y) - ulp
End Around Carry
Discarded & Added as
ulp
Should Add ulp
for Correction
COE 522
Dr. A. Amin
Representation of Signed Numbers
2`s Complement
Sign
Digit
0 +ive
1 -ive
• Asymmetric Range of Representation
{ -(2k-1) : +(2k-1 -ulp) }
- Negation Can Lead to OverFlow
COE 522
Dr. A. Amin
2`s Complement Numbers System
Integral Part
Fractional Part
X = xk-1 xk-2 ... x1 x0 . x-1 x-2 ... x-m
Sign Bit
k 1
=  xk 1 2

k 2
 xi 2
i
i  m
=X
if X is +ive
= -2k-1 + (2k-1 - X ) = X
if X is -ive
Precision/Range Extension of 2`s Comp #`s
• Extending # N from n-bits to k`-bits (k`> k)
 +ive N Pad with 0`s to the Left of the integral
part And/Or to the right of Fractional Part.
 -ive N Pad with 0`s to the right of Fractional
Part And/Or Extend Sign Bit to the Left of the
integral part.
• In General
• Pad with 0`s to the right of Fractional Part
And/Or Extend Sign Bit to the Left of the
integral part.
...xk-1 xk-1 xk-1 xk-2 ... x1 x0 . x-1 x-2 .... x-m 000…..
COE 522
Dr. A. Amin
2`s Complement System
-ive N
N`k = 2k - N
N`k` = 2k` - N
N`k` - N`k = 2k` - 2k = 2k (2k`-k - 1 )
Shift Left k-bits
(k`-k) 1`s
1111..111000..0
Sign Extension
(k`-k) 1`s
k 0`s
Features
• Leftmost Bit indicates Sign
• The Sign Bit is Part of a Truncated  -String
• Asymetric Range(-2k-1 : +(2k-1 -ulp) )
– Overflow may result on Complementing
• Single Zero Representation 0000000 (+0)
COE 522
Dr. A. Amin
Representation of Signed Numbers
1`s Complement
Sign
Digit
0 +ive
1 -ive
• Symmetric Range of Representation
{ -(2k-1 -ulp) : +(2k-1 -ulp) }
- 2 Representations of 0
(+0 = 0000000 and -0 = 1111111)
COE 522
Dr. A. Amin
1`s Complement Numbers System
Integral Part
Fractional Part
X = xk-1 xk-2 ... x1 x0 . x-1 x-2 ... x-m
Sign Bit
k 1
=  xk 1 ( 2
 ulp ) 
k 2
 xi 2
i
i  m
=X
for +ive X
= -(2k-1-ulp) + X ) = X`
for -ive X
Precision/Range Extension of 2`s Comp #`s
• Extending # N from n-bits to k`-bits (k`> k)
 +ive N Pad with 0`s to the Left of the integral
part And/Or to the right of Fractional Part.
 -ive N
Pad with Sign Bit to the right of
Fractional Part And/Or to the Left of the integral
part.
• In General
• Pad with Sign Bit to the right of Fractional Part
And/Or to the Left of the integral part.
..xk-1 xk-1 xk-1 xk-2 .. x1 x0 . x-1 x-2 .. x-m xk-1 xk-1 …..
COE 522
Dr. A. Amin
1`s Complement Numbers System
Features
• Leftmost Bit indicates Sign
• The Sign Bit is Part of a Truncated  -String
• Symetric Range(-(2k-1 -ulp) : +(2k-1 -ulp) )
• Two Zero Representation (+0 , -0 )
Arithmetic Shifts
Effect
• Left Shift Multiply Number by radix r
• Right Shift Divide Number by radix r
(a) Shifting Unsigned or +ive Numbers
• Shift-In 0`s (for both Left & Right Shifts)
(b) Shifting -ive Numbers
• Depends on the Representation Method
Signed Magnitude:
– Sign Bit is maintained (Unchanged)
– Only The Magnitude is shifted and 0`s are
Shifted-In for both Directions (Left & Right)
COE 522
Dr. A. Amin
Arithmetic Shifts
2`s Complement:
– Left Shifts: 0`s are Shifted-In
– Right Shifts: Sign Bit Extended (Shifted Right)
1`s Complement:
– Left & Right Shifts: Sign Bit is Shifted-In
Right Shifts
Left Shifts
COE 522
Dr. A. Amin