Transcript 02-Data Types & Repr..

IKI10201
02-Data Types & Representations
Bobby Nazief
Semester-I 2005 - 2006
The materials on these slides are adopted from those in
CS231’s Lecture Notes at UIUC, which is derived from
Howard Huang’s work and developed by Jeff Carlyle.
Road Map
3
Boolean Algebra
Finite-State
Machines
Logic Gates & 3
Flip-flops
6
2
Binary Systems
& Data Represent.
8
Generalized FSM
Logic Design
Techniques
4
Combinatorial 5
Components
6
Sequential Design
Techniques
Storage
Components
7
8
Register-Transfer
Design
Processor
Components
9
2
Number Systems
•
To get started, we’ll discuss one of the fundamental concepts
underlying digital computer design:
Deep down inside, computers work with just 1s and 0s.
•
•
•
Computers use voltages to represent information. In modern CPUs the
voltage is usually limited to 1.6-1.8V to minimize power consumption.
It’s convenient for us to translate these analog
Volts
voltages into the discrete, or digital, values 1 and 0.
1.8
But how can two lousy digits be useful for anything?
1
– First, we’ll see how to represent numbers with
just 1s and 0s.
– Then we’ll introduce special operations
0
for computing with 1s and 0s, by treating them as
0
the logical values “true” and “false.”
3
Positional number systems: decimal
•
Numbers consist of a bunch of digits, each with a weight:
1
100
•
2
1
.
3
1/10
7
1/100
5
Digits
1/1000 Weights
The weights are all powers of the base, which is 10. We can rewrite the
weights like this:
1
102
•
6
10
6
101
2
100
.
3
10-1
7
10-2
5
10-3
Digits
Weights
To find the decimal value of a number, multiply each digit by its weight
and sum the products.
(1 x 102) + (6 x 101) + (2 x 100) + (3 x 10-1) + (7 x 10-2) + (5 x 10-3) = 162.375
4
Positional number systems: binary
•
•
We can use the same trick for binary, or base 2, numbers. The only
difference is that the weights are powers of 2.
For example, here is 1101.01 in binary:
1
23
•
1
22
0
21
1
20
.
0
2-1
1
2-2
Binary digits, or bits
Weights (in base 2)
The decimal value is:
(1 x 23) + (1 x 22) + (0 x 21) + (1 x 20) + (0 x 2-1) + (1 x 2-2) =
8
+
4
+
0
+
1
+
0
+ 0.25 = 13.25
Powers of 2:
20 = 1
21 = 2
22 = 4
23 = 8
24
25
26
27
=
=
=
=
16
32
64
128
28 = 256
29 = 512
210 = 1024
5
Base 8 - Octal
•
The octal system uses 8 digits:
01234567
•
•
•
Earlier in this history of computing, octal
was used as a shorthand for binary
numbers. (Now hexadecimal is more
common.)
Since 8 = 23, one octal digit is equivalent to
3 binary digits.
– Numbers like 67 are easier to work
with than 110111.
Still shows up in some places. For instance,
file access permissions in Unix file
systems.
Decimal
0
1
2
3
4
5
6
7
Binary
000
001
010
011
100
101
110
111
Octal
0
1
2
3
4
5
6
7
6
Base 16 is useful too
•
The hexadecimal system uses 16 digits:
0123456789ABCDEF
•
•
For our purposes, base 16 is most useful as
a “shorthand” notation for binary numbers.
– Since 16 = 24, one hexadecimal digit is
equivalent to 4 binary digits.
– It’s often easier to work with a number
like B4 instead of 10110100.
Hex is frequently used to specify things
like IPv6 addresses and 24-bit colors.
Decimal
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Binary
0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111
Hex
0
1
2
3
4
5
6
7
8
9
A
B
C
D
E
F
7
Converting decimal to binary
•
•
•
To convert a decimal integer into binary, keep dividing by 2 until the
quotient is 0. Collect the remainders in reverse order.
To convert a fraction, keep multiplying the fractional part by 2 until it
becomes 0. Collect the integer parts in forward order.
Example: 162.375:
162 / 2
81 / 2
40 / 2
20 / 2
10 / 2
5/2
2/2
1/2
•
= 81
= 40
= 20
= 10
=5
=2
=1
=0
rem 0
rem 1
rem 0
rem 0
rem 0
rem 1
rem 0
rem 1
0.375 x 2 = 0.750
0.750 x 2 = 1.500
0.500 x 2 = 1.000
So, 162.37510 = 10100010.0112
8
Why does this work?
•
•
This works for converting from decimal to any base
Why? Think about converting 162.375 from
decimal to decimal.
162 / 10 = 16
16 / 10 = 1
1 / 10 = 0
•
•
rem 2
rem 6
rem 1
Each division strips off the rightmost digit (the
remainder). The quotient represents the remaining
digits in the number.
Similarly, to convert fractions, each multiplication
strips off the leftmost digit (the integer part).
The fraction represents the remaining digits.
0.375 x 10 = 3.750
0.750 x 10 = 7.500
0.500 x 10 = 5.000
9
Binary and hexadecimal conversions
•
Converting from hexadecimal to binary is easy: just replace each hex
digit with its equivalent 4-bit binary sequence.
261.3516 =
2
6
1
.
3
516
= 0010 0110 0001 . 0011 01012
•
To convert from binary to hex, make groups of 4 bits, starting from the
binary point. Add 0s to the ends of the number if needed. Then, just
convert each bit group to its corresponding hex digit.
10110100.0010112 = 1011
=
B
0100 . 0010 11002
4
.
2
C16
Hex
Binary
Hex
Binary
Hex
Binary
Hex
Binary
0
0000
4
0100
8
1000
C
1100
1
0001
5
0101
9
1001
D
1101
2
0010
6
0110
A
1010
E
1110
3
0011
7
0111
B
1011
F
1111
10
Practice
•
•
•
Convert 32103.510 to hexadecimal.
Convert CAFE16 to decimal.
Convert 7038 to base-12.
11
Convert 32103.510 to hexadecimal.
1.
2.
3.
4.
5.
32103 / 16 = 2006
2006 / 16 = 125
125 / 16 = 7
7 / 16 = 0
.5 * 16 = 8.0
•
So 7D67.816.
rem 7
rem 6
rem 13
rem 7
12
Convert CAFE16 to decimal.
1.
2.
3.
4.
C: 12 * 163 = 49152
A: 10 * 162 = 2560
F: 15 * 161 = 240
E: 14 * 16- = 14
5.
49152+2560+240+14=51966
13
Convert 7038 to base-12.
1.
2.
3.
7: 7 * 82 = 448
0: 0 * 81 = 0
3: 3 * 80 = 3
4.
448+0+3 = 451
5.
6.
7.
451 / 12 = 37
37 / 12 = 3
3 / 12 = 0
•
So 31712.
rem 7
rem 1
rem 3
14
Number Systems Summary
•
•
Computers are binary devices.
– We’re forced to think in terms of base 2.
– Today we learned how to convert numbers between binary, decimal
and hexadecimal.
We’ve already seen some of the recurring themes of architecture:
– We use 0 and 1 as abstractions for analog voltages.
– We showed how to represent numbers using just these two signals.
15
Additional information
•
Assistants:
– Panca Novianto: [email protected]
– Evan Jonathan Winata: [email protected]
16
Review - Positional number systems: binary
•
•
We can use the same trick for binary, or base 2, numbers. The only
difference is that the weights are powers of 2.
For example, here is 1101.01 in binary:
1
23
•
1
22
0
21
1
20
.
0
2-1
1
2-2
Binary digits, or bits
Weights (in base 2)
The decimal value is:
(1 x 23) + (1 x 22) + (0 x 21) + (1 x 20) + (0 x 2-1) + (1 x 2-2) =
8
+
4
+
0
+
1
+
0
+ 0.25 = 13.25
Powers of 2:
20 = 1
21 = 2
22 = 4
23 = 8
24
25
26
27
=
=
=
=
16
32
64
128
28 = 256
29 = 512
210 = 1024
17
Review - Converting decimal to binary
•
•
•
To convert a decimal integer into binary, keep dividing by 2 until the
quotient is 0. Collect the remainders in reverse order.
To convert a fraction, keep multiplying the fractional part by 2 until it
becomes 0. Collect the integer parts in forward order.
Example: 162.375:
162 / 2
81 / 2
40 / 2
20 / 2
10 / 2
5/2
2/2
1/2
•
= 81
= 40
= 20
= 10
=5
=2
=1
=0
rem 0
rem 1
rem 0
rem 0
rem 0
rem 1
rem 0
rem 1
0.375 x 2 = 0.750
0.750 x 2 = 1.500
0.500 x 2 = 1.000
So, 162.37510 = 10100010.0112
18
Addition and Subtraction of Binary Numbers
•
•
•
Arithmetic is the most basic thing you can do with a computer, but it’s
not as easy as you might expect!
These next few lectures focus on addition and subtraction.
Computers were designed to compute, so arithmetic is at the heart of a
CPU.
19
Binary addition by hand
•
•
You can add two binary numbers one column at a time starting from the
right, just as you add two decimal numbers.
But remember that it’s binary. For example, 1 + 1 = 10 and you have to
carry!
The initial carry
in is implicitly 0
1
+
1
1
1
1
1
most significant
bit, or MSB
1
0
1
0
0
1
1
0
1
0
1
Carry in
Augend
Addend
Sum
least significant
bit, or LSB
20
Subtraction
•
Computers do subtraction by adding the minuend with the negative
representation of the subtrahend:
– The main problem is representing negative numbers in binary. We
introduce three methods, and show why one of them is the best.
– With negative numbers, we’ll be able to do subtraction using the
adders we made last time, because A - B = A + (-B).
21
Negative Numbers
22
Signed magnitude representation
•
•
•
Humans use a signed-magnitude system: we add + or - in front of a
magnitude to indicate the sign.
We could do this in binary as well, by adding an extra sign bit to the
front of our numbers. By convention:
– A 0 sign bit represents a positive number.
– A 1 sign bit represents a negative number.
Examples:
11012 = 1310 (a 4-bit unsigned number)
0 1101 = +1310 (a positive number in 5-bit signed magnitude)
1 1101 = -1310 (a negative number in 5-bit signed magnitude)
01002 = 410
0 0100 = +410
1 0100 = -410
(a 4-bit unsigned number)
(a positive number in 5-bit signed magnitude)
(a negative number in 5-bit signed magnitude)
23
Signed magnitude operations
•
•
•
Negating a signed-magnitude number is trivial: just change the sign bit
from 0 to 1, or vice versa.
Adding numbers is difficult, though. Signed magnitude is basically what
people use, so think about the grade-school approach to addition. It’s
based on comparing the signs of the augend and addend:
– If they have the same sign, add the magnitudes and keep that sign.
– If they have different signs, then subtract the smaller magnitude
from the larger one. The sign of the number with the larger
magnitude is the sign of the result.
This method of subtraction would lead to a rather complex circuit.
+3
+ -6
-2
7
4
6
9
7
8
because
-
5
6
3
2
13
4 17
7 9
6 8
24
One’s complement representation
•
•
•
A different approach, one’s complement, negates numbers by
complementing each bit of the number.
We keep the sign bits: 0 for positive numbers, and 1 for negative. The
sign bit is complemented along with the rest of the bits.
Examples:
11012 = 1310 (a 4-bit unsigned number)
0 1101 = +1310 (a positive number in 5-bit one’s complement)
1 0010 = -1310 (a negative number in 5-bit one’s complement)
01002 = 410
0 0100 = +410
1 1011 = -410
(a 4-bit unsigned number)
(a positive number in 5-bit one’s complement)
(a negative number in 5-bit one’s complement)
25
Why is it called “one’s complement?”
•
Complementing a single bit is equivalent to subtracting it from 1.
0’ = 1, and 1 - 0 = 1
•
•
1’ = 0, and 1 - 1 = 0
Similarly, complementing each bit of an n-bit number is equivalent to
subtracting that number from 2n-1.
For example, we can negate the 5-bit number 01101.
– Here n=5, and 2n-1 = 3110 = 111112.
– Subtracting 01101 from 11111 yields 10010:
1 1 1 1 1
- 01 1 01
1 00 1 0
26
One’s complement addition
•
•
To add one’s complement numbers:
– First do unsigned addition on the numbers, including the sign bits.
– Then take the carry out and add it to the sum.
Two examples:
0111
+
1011
1 0010
0010
+
1
0011
•
(+7)
+ (-4)
(+3)
0011
+
0010
0 0101
0101
+
0
0101
(+3)
+ (+2)
(+5)
This is simpler and more uniform than signed magnitude addition.
27
Two’s complement
•
•
Our final idea is two’s complement. To negate a number, complement
each bit (just as for ones’ complement) and then add 1.
Examples:
11012
0 1101
1 0010
1 0011
= 1310
= +1310
= -1310
= -1310
01002 = 410
0 0100 = +410
1 1011 = -410
1 1100 = -410
(a
(a
(a
(a
4-bit unsigned number)
positive number in 5-bit two’s complement)
negative number in 5-bit ones’ complement)
negative number in 5-bit two’s complement)
(a
(a
(a
(a
4-bit unsigned number)
positive number in 5-bit two’s complement)
negative number in 5-bit ones’ complement)
negative number in 5-bit two’s complement)
28
More about two’s complement
•
Two other equivalent ways to negate two’s complement numbers:
– You can subtract an n-bit two’s complement number from 2n.
1 00000
- 0 1 1 0 1 (+1310)
1 0 0 1 1 (-1310)
–
1 00000
- 0 0 1 0 0 (+410)
1 1 1 0 0 (-410)
You can complement all of the bits to the left of the rightmost 1.
01101
10011
= +1310 (a positive number in two’s complement)
= -1310 (a negative number in two’s complement)
00100
11100
= +410
= -410
(a positive number in two’s complement)
(a negative number in two’s complement)
29
Comparing the signed number systems
•
•
•
•
•
Here are all the 4-bit numbers
in the different systems.
Positive numbers are the same in
all three representations.
Signed magnitude and one’s
complement have two ways of
representing 0. This makes
things more complicated.
Two’s complement has
asymmetric ranges; there is one
more negative number than
positive number. Here, you can
represent -8 but not +8.
However, two’s complement is
preferred because it has only
one 0, and its addition algorithm
is the simplest.
Decimal
S.M.
1’s comp.
2’s comp.
7
6
5
4
3
2
1
0
-0
-1
-2
-3
-4
-5
-6
-7
-8
0111
0110
0101
0100
0011
0010
0001
0000
1000
1001
1010
1011
1100
1101
1110
1111
—
0111
0110
0101
0100
0011
0010
0001
0000
1111
1110
1101
1100
1011
1010
1001
1000
—
0111
0110
0101
0100
0011
0010
0001
0000
—
1111
1110
1101
1100
1011
1010
1001
1000
30
Converting signed numbers to decimal
•
Convert 110101 to decimal, assuming this is a number in:
(a) signed magnitude format
(b) ones’ complement
(c) two’s complement
31
Example solution
•
Convert 110101 to decimal, assuming this is a number in:
Since the sign bit is 1, this is a negative number. The easiest way to
find the magnitude is to convert it to a positive number.
(a) signed magnitude format
Negating the original number, 110101, gives 010101, which is +21 10 in
decimal. So 110101 must represent -2110.
(b) ones’ complement
Negating 110101 in ones’ complement yields 001010 = +1010, so the
original number must have been -1010.
(c) two’s complement
•
Negating 110101 in two’s complement gives 001011 = 11 10, which
means 110101 = -1110.
The most important point here is that a binary number has different
meanings depending on which representation is assumed.
32
Addition & Subtraction of 2’s complement numbers
•
Addition:
– Just add the two numbers
– Ignore the Carry-out from
MSB
– Result will be correct, provided
there’s no overflow
•
Subtraction:
– Form 2’s complement of the
subtrahend
– Add the two numbers as in
Addition
0 1 0 1 (+5)
+0 0 1 0 (+2)
0 1 1 1 (+7)
0 1 0 1 (+5)
+1 0 1 0 (-6)
1 1 1 1 (-1)
0 0 1 0 (+2)
0 1 0 0 (+4)
1 0 1 1 (-5)
+1 1 1 0 (-2)
11 0 0 1 (-7)
0 1 1 1 (+7)
+1 1 0 1 (-3)
10 1 0 0 (+4)
1 1 1 0 (-2)
1 0 1 1 (-5)
0010
+1 1 0 0 (-4)
1 1 1 0 (-2)
1110
+0 1 0 1 (+5)
10 0 1 1 (+3)
33
Overflow
Binary
Decimal
2’s Complement
0
0000
0
0000
1
0001
-1
1111
2
0010
-2
1110
3
0011
-3
1101
4
0100
-4
1100
5
0101
-5
1011
6
0110
-6
1010
7
0111
-7
1001
-8
1000
Decimal
•
Examples: 7 + 3 = 10 but ...
- 4 – 5 = - 9 but ...
0
+
1
1
1
1
0
1
1
1
7
0
0
1
1
3
1
0
1
0
–6
+
1
1
0
0
–4
1
0
1
1
–5
0
1
1
1
7
34
Binary Multiplication
+
•
•
x
1
0
1
1
0
1
1
0
Multiplicand
Multiplier
0
1
Partial products
0
0
0
1
0
1
0
1
1
0
0
1
0
0
1
0
0
1
1
1
0
Product
Since we always multiply by either 0 or 1, the partial products are
always either 0000 or the multiplicand (1101 in this example).
There are four partial products which are added to form the result.
35
Shifting the multiplicand
+
x
1
0
1
1
0
1
1
0
Multiplicand
Multiplier
+
0
0
0
0
0
0
0
0
first partial products
shifted zeros
+
1
0
1
0
0
0
1
0
second partial products
shifted multiplicand
+
1
1
1
1
0
0
1
1
0
third partial products
shifted multiplicand
1
0
0
0
0
0
1
0
1
1
0
fourth partial products
shifted zeros
1
0
0
1
1
1
0
Product
36
Binary Division
37
Floating-Point Numbers
38
Scientific notation review
mantissa
exponent
6.02 x 1023
decimal point
radix (base)
•
Normalized form: no leadings 0s
(exactly one digit to left of decimal point)
•
Alternatives to representing 1/1,000,000,000
– Normalized:
– Not normalized:
1.0 x 10-9
0.1 x 10-8,10.0 x 10-10
39
Scientific notation for binary numbers
Mantissa
exponent
1.0two x 2-1
“binary point”
•
radix (base)
Computer arithmetic that supports it called floating point, because it
represents numbers where binary point is not fixed, as it is for integers
– Declare such variable in C as float
40
Floating point representation
•
•
Normal format: +1.xxxxxxxxxxtwo*2yyyytwo
Multiple of Word Size (32 bits)
0 1
8 9
S Exponent
1 bit
•
•
8 bits
Significand
31
23 bits
S represents Sign
Exponent represents y’s
Significand represents x’s
Represent numbers as small as
2.0 x 10-38 to as large as 2.0 x 1038
41
BCD
42
Character Codes
43
Codes for Error Detection & Correction
•
Please read yourself.
44
Hamming Codes
•
Please read yourself.
45