Transcript No Slide Title

Lecture 4: Number Systems (Chapter 3)
(1) Data Types
Section 3-1
(2) Complements
Section 3-2
(3) Fixed Point Representations
Section 3-3
(4) Floating Point Representations
Section 3-4
(5) Other Binary Codes
Section 3-5
(6) Error Detection Codes
Section 3-6
Data Types
Information that a Computer is dealing with:
Data
Numeric Data
Numbers (Integer, real)
Non-numeric Data
Letters, Symbols
Relationship between data elements
Data Structures
Linear Lists, Trees, Rings, etc
Program (Instructions)
Data Types: Numeric Data Representation
Nonpositional number system
Roman number system
Positional number system
Each digit position has a value called a weight associated
with it
Examples: Decimal, Octal, Hexadecimal, Binary
Base (or radix) R number
Uses R distinct symbols for each digit
Example A R = a n-1 a n-2 ... a 1 a 0 .a -1 …a -m
V(A R) = SUM (a k * R k)
for k = -m to n-1
R = 10
R=2
R=8
R = 16
Decimal number system
Binary
Octal
Hexadecimal
Data Types: Numeric Data Representation
Why a Positional Number System for Digital Computers???
Major Consideration is the COST and TIME
Cost of building hardware
Arithmetic and Logic Unit, CPU,Communications
Time to processing
Arithmetic - Addition of Numbers - Table for Addition
Non-positional Number System
Table for addition is infinite
--> Impossible to build, very expensive even if it
can be built
Positional Number System
Table for Addition is finite
--> Physically realizable, but cost wise the smaller
the table size, the less expensive
--> Binary is favorable to Decimal
Positive (Unsigned) Binary Numbers
Unsigned binary numbers are typically used to represent computer
addresses or other values that are guaranteed not to be
negative.
An n-bit unsigned binary integer A = an-1 an-2... a1 a0
1 n
has a value of
2  ia
i

0 i
For example,
1011 = 1 x 23 + 0 x 22 + 1 x 21 + 1 x 20
= 8 + 2 + 1 = 11
An n-bit unsigned binary integer has a range from 0 to 2n - 1.
Octal and Hexadecimal Numbers
Octal, base-8, numbers were used in the early days of computing to
represent binary numbers
Octal numbers are made by grouping binary numbers
together three bits at a time
Hexadecimal, base-16, numbers are the representation of choice
today
Hex numbers are made by grouping binary numbers
together four bits at a time
For example:
Octal: 7
2
5
1
7
5
2
2 .
Binary: 1 1 1 0 1 0 1 0 1 0 0 1 1 1 1 1 0 1 0 1 0 0 1 0
Hex:
E
A
9
F
5
2
Negative (Signed) Binary Numbers
Positional representation using n bits
X = X n X n-1 X n-2 … X 1 X 0 . X -1 X -2 ... X -m
Sign-magnitude format
Left most bit position (X n) is the sign bit
-- only bit that is complemented
0 for positive number
1 for negative number
Remaining n-1 bits represent the magnitude
Min:
- (2 n - 2 -m)
= 1111 1111 . 1111 1111
Max: + (2 n - 2 -m)
= 0111 1111 . 1111 1111
Zero: - 0
= 1000 0000 . 0000 0000
Zero: +0
= 0000 0000 . 0000 0000
Complements of Numbers
Two types of complements for base R number system:
R’s complement
(R-1)’s complement
The (R-1)’s Complement
Subtract each digit of a number from (R-1)
Examples:
9’s complement of 835 10 is 164 10
1’s complement of 1010 2 is 0101 2
(bit by bit complement operation)
The R’s Complement
Add 1 to the low-order digit of its (R-1)’s complement
Examples:
10’s complement of 835 10 is 164 10 + 1 = 165 10
2’s complement of 1010 2 is 0101 2 + 1 = 0110 2
Negative (Signed) Binary Numbers
Ones complement format
Negative numbers are represented by a bit-by-bit
complementation of the (positive) magnitude (the process of
negation)
Sign bit interpreted as in sign-magnitude format
Examples (8-bit words):
+42
= 0 00101010
-42
= 1 11010101
Min:
Max:
Zero:
Zero:
- (2 n - 2 -m)
+ (2 n - 2 -m)
-0
+0
= 1111 1111 . 1111 1111
= 0111 1111 . 1111 1111
= 1111 1111 . 1111 1111
= 0000 0000 . 0000 0000
Negative (Signed) Binary Numbers
Twos complement format
Negative numbers, -X, are represented by the pseudopositive number:
2n - |X|
An n-bit unsigned binary integer A = an-1 an-2... a1 a0 has a
2n
value of
2  ia
i
1 n

2  1  na

0 i
For example:
1011
= -1 x 23 + 0 x 22 + 1 x 21 + 1 x 20
= -8 + 2 + 1 = -5
With 2n digits:
2 n-1 -1 positive numbers
2 n -1 negative numbers
Given the representation for +X, the representation for -X is
found by taking the 1s complement of +X and adding 1
Negative (Signed) Binary Numbers
Twos complement format
Most significant bit is the “sign bit”.
Number representation is not symmetric.
Only one representation for zero.
Easy to negate, add, and subtract numbers.
A little bit trickier for multiply and divide.
Min:
Max:
Zero:
- (2 n)
+ (2 n - 2 -m)
= 1000 0000 . 0000 0000
= 0111 1111 . 1111 1111
= 0000 0000 . 0000 0000
Signed 2’s Complement Addition
Add the two numbers, including their sign bit, and discard any carry
out of left-most(sign) bit
Examples:
6
+9
15
0 0110
0 1001
0 1111
-6=
+ 9=
3=
1 1010
0 1001
0 0011
6
+ -9
-3
0 0110
1 0111
1 1101
-9
1 0111
+ -9
1 0111
-18 (1) 0 1110
9
+9
18
0 1001
0 1001
1 0010
Detecting 2’s Complement Overflow
When adding two's complement numbers, overflow will only occur if
the numbers being added have the same sign the sign of the result
is different
If we perform the addition
an-1 an-2 ... a1 a0
+ bn-1bn-2… b1 b0
----------------------------------
= sn-1sn-2… s1 s0
Overflow can be detected as
V  cn  c n  1
where cn-1and cn are the carry in and carry out of the most
significant bit.
Signed 2’s Complement Subtraction
To subtract two's complement numbers we first negate the second
number and then add the corresponding bits of both numbers.
Examples:
3 = 0011
- 2 = 0010
-3 = 1101
- -2 = 1110
-3 = 1101
- 2 = 0010
3 = 0011
- -2 = 1110
3 = 0011
+ -2 = 1110
-3 = 1101
+ 2 = 0010
-3 = 1101
+ -2 = 1110
3 = 0011
+ 2 = 0010
1 = 0001
-1 = 1111
-5 = 1011
5 = 0101
become:
Sign-Extension / Zero-Extension
Sign-extension is used for signed immediates and signed values from
memory
To sign-extend an n bit number to n+m bits, copy the sign-bit m times.
For example, with n = 4 and m = 4,
1011
= -4
0101 = 5
11111011
= -4
00000101 = 5
Zero-extension is used for logical operations and unsigned values from
memory
To zero-extend an n bit number to n+m bits, copy zero m times.
For example, with n = 4 and m = 4,
1011
= 11
0101
=5
00001011
= 11
00000101
=5
Floating Point Number Representation
The location of the fractional point is not fixed to a certain location
--> The range of the representable numbers is wide
--> high precision
F = EM
mn
e k e k-1 ... e 0
sign
exponent
m n-1 m n-2 ... m 0 . m -1 ... m -m
mantissa
Mantissa
Signed fixed point number, either an integer or a fractional number
Exponent
Designates the position of the radix point
Floating Point Number Representation
Decimal Value:
V=M*RE
Where: M= Mantissa
E= Exponent
R= Radix (10)
Example (decimal):
1234.5678
Exponent
Sign
Value
0
4
==> 0.12345678 x 10 +4
Mantissa
Sign
Value
0
0.12345678
Floating Point Number Representation
Example (binary):
+ 1001.11
(= 9.75)
Make a fractional number, counting the number of shifts:
+ .100111
==> 4 shifts
Exponent
Sign
Value
0
100
Mantissa
Sign
Value
0
1001111
Or for a 16-bit number with a sign, 5-bit exponent, 10-bit mantissa:
0 00100 1001111000
Other Representations- Gray Codes
Characterized by having their representations of the binary integers
different in only one digit between consecutive integers
Useful in analog-digital conversion.
Decimal
0
1
2
3
4
5
6
7
Gray
0000
0001
0011
0010
0110
0111
0101
0100
Binary
0000
0001
0010
0011
0100
0101
0110
0111
Decimal
8
9
10
11
12
13
14
15
Gray
1100
1101
1111
1110
1010
1011
1001
1000
Binary
1000
1001
1010
1011
1100
1101
1110
1111
Other Representations- ASCII Characters
3LSBs
0 (hex)
1
2
3
4
5
6
7
8
9
A
B
C
D
E
F
4MSBs
0
NUL
SOH
STX
ETX
EOT
ENQ
ACK
BEL
BS
HT
LF
VT
FF
CR
SO
SI
1
DLE
DC1
DC2
DC3
DC4
NAK
SYN
ETB
CAN
EM
SUB
ESC
FS
GS
RS
US
1
SP
!
"
#
$
%
&
’
(
)
*
+
,
.
/
3
0
1
2
3
4
5
6
7
8
9
:
;
<
=
>
?
4
@
A
B
C
D
E
F
G
H
I
J
K
L
M
N
O
5
P
Q
R
S
T
U
V
W
X
Y
Z
[
\
]
^
_
6
‘
a
b
c
d
e
f
g
h
i
j
k
l
m
n
o
7
p
q
r
s
t
u
v
w
x
y
z
{
|
}
~
DEL
Error Detecting Codes- Parity
Parity System
Simplest method for error detection
One parity bit attached to the information
Even Parity and Odd Parity
Even Parity
One bit is attached to the information so that the total number
of 1 bits is an even number
1011001 0
1010010 1
==> B even = B n-1 (+) B n-2 (+) … B 0
Odd Parity
One bit is attached to the information so that the total number
of 1 bits is an odd number
1011001 1
1010010 0
==> B odd = B n-1 (+) B n-2 (+) … B 0 (+) 1
Error Detecting Codes- Parity
Even Parity Generator Circuit
B0
B1
B2
B3
B4
B5
B6
B even
Even Parity Checker Circuit
B0
B1
B2
B3
B4
B5
B6
B even
ERROR