Transcript Chapter_02.Wakerly.Number Systems

Number Systems
• Stone Age: knots, some stone marks
• Roman Empire: more systematic notation I,
II, III, IV, V, VI, VII.VIII, IX, X, C=100,
D=500, M=1000, L=50
• Concept of zero by
– Maya- I century, Hindu-V century
• Positional-value systems: decimal, binary,
octal, etc..
Positional-Value System
• The value of a digit (“digit” from Latin word
for finger) depends on its position
Positional values
2 1 0
(weights)
10 10 10
-1
-2
-3
10 10 10
5 6 7 . 9 1 4
MSD
Decimal
point
We will write ( 5 6 7. 9 1 4)10
LSD
Binary:
Base-2 Number System
5 4 3 2 1 0
2 2 2 2 2 2
-1 -2 -3
2 2 2
1 0 1 1 1 1 . 0 0 1
base point or radix
We write: ( 1 0 1 1 1 1 . 0 0 1 )2
Digits are called bits
Binary Representation
• The basis of all digital data is binary representation.
• Binary - means ‘two’
–
–
–
–
1, 0
True, False
Hot, Cold
On, Off
• We must be able to handle more than just values for
real world problems
–
–
–
–
1, 0, 56
True, False, Maybe
Hot, Cold, LukeWarm, Cool
On, Off, Leaky
Number Systems
• To talk about binary data, we must first talk about
number systems
• The decimal number system (base 10) you should
be familiar with!
– A digit in base 10 ranges from 0 to 9.
– A digit in base 2 ranges from 0 to 1 (binary number
system). A digit in base 2 is also called a ‘bit’.
– A digit in base R can range from 0 to R-1
– A digit in Base 16 can range from 0 to 16-1
(0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F). Use letters A-F to
represent values 10 to 15. Base 16 is also called
Hexadecimal or just ‘Hex’.
Positional Number Systems
• The traditional number
system is called a
positional number system.
• A number is represented
as a string of digits.
• Each digit position has a
weight assoc. with it.
• Number’s value = a
weighted sum of the digits
6354  6 *1000  3*100  5 *10  4
p 1
D   di 10i
i 0
Positional Notation – more examples
Value of number is determined by multiplying each digit by a
weight and then summing. The weight of each digit is a
POWER of the BASE and is determined by position.
953.78 = 9 x 102 + 5 x 101 + 3 x 100 + 7 x 10-1 + 8 x 10-2
= 900 + 50 + 3 + .7 + .08 = 953.78
decimal
% 1011.11 = 1x23 + 0x22 + 1x21 + 1x20 + 1x2-1 + 1x2-2
= 8
+ 0 + 2 + 1 + 0.5 + 0.25
= 11.75
binary
$ A2F = 10x162 + 2x161 + 15x160
= 10 x 256
+ 2 x 16 + 15 x 1
= 2560 + 32 + 15 = 2607
hex
Base 10, Base 2, Base 16
The textbook uses subscripts to represent different
bases (ie. A2F16 , 953.7810, 1011.112 )
We will use special symbols to represent the different bases.
The default base will be decimal, no special symbol for
base 10.
The ‘$’ will be used for base 16 ( $A2F)
The ‘%’ will be used for base 2 (%10101111)
If ALL numbers on a page are the same base (ie, all in base
16 or base 2 or whatever) then no symbols will be used and
a statement will be present that will state the base (ie, all
numbers on this page are in base 16).
Common Powers
2-3 = 0.125
2-2 = 0.25
2-1 = 0.5
20 = 1
21 = 2
22 = 4
23 = 8
24 = 16
25 =32
26 = 64
27 = 128
28 = 256
29 = 512
210 = 1024
211 = 2048
212 = 4096
160 = 1 = 20
161 = 16 = 24
162 = 256 = 28
163 = 4096 = 212
210 = 1024 = 1 K
220 = 1048576 = 1 M (1 Megabits) = 1024 K = 210 x 210
230 = 1073741824 = 1 G (1 Gigabits)
Octal and
Hexadecimal
(“Hex”) Numbers
• Octal = base 8
• Hexadecimal = base 16
– Use A – F to represent the values 10 through 16 in each
position.
Usefulness of Octal and Hex Numbers
• Useful for representing multi-bit binary numbers because their
radices are integer multiples of 2.
10 0101 1010 1111 . 1011 1112 = 2 5 A F . B E16
Decimal
Binary
Octal
Hex
5
101
5
5
6
110
6
6
7
111
7
7
8
1000
10
8
9
1001
11
9
10
1010
12
A
11
1011
13
B
12
1100
14
C
13
1101
15
D
14
1110
16
E
15
1111
17
F
Comparison of binary, decimal, octal
and hexadecimal numbers
examples
of octal
and hex
numbers
Decimal to Hex Conversions
Convert 53 to Hex
53/16 = 3, rem = 5
3 /16 = 0 , rem = 3
53 = $ 35
= 3 x 161 + 5 x 160
= 48 + 5 = 53
Hex (base 16) to Binary
Conversion
Each Hex digit represents 4 bits. To convert a Hex number to
Binary, simply convert each Hex digit to its four bit value.
Hex Digits to binary:
$ 0 = % 0000
$ 1 = % 0001
$2 = % 0010
$3 = % 0011
$4 = % 0100
$5 = % 0101
$6 = % 0110
$7 = % 0111
$8 = % 1000
Hex Digits to binary (cont):
$ 9 = % 1001
$ A = % 1010
$ B = % 1011
$ C = % 1100
$ D = % 1101
$ E = % 1110
$ F = % 1111
Conversions: Hex to Binary, Binary
to Hex
$ A2F = % 1010 0010 1111
$ 345
Hex to Binary
conversion
= % 0011 0100 0101
Binary to Hex is just the opposite, create groups of 4 bits
starting with least significant bits. If last group does not
have 4 bits, then pad with zeros for unsigned numbers.
% 1010001 = % 0101 0001 = $ 51
Padded with a zero
Binary to hex
conversion
A Trick!
If faced with a large binary number that has to be
converted to decimal, we first convert the binary number
to HEX, then convert the HEX to decimal. Less work!
% 110111110011 = % 1101 1111 0011
= $ D
F 3
= 13 x 162 + 15 x 161 + 3x160
= 13 x 256 + 15 x 16 + 3 x 1
= 3328 + 240 + 3
= 3571
Of course, you can also use the binary, hex conversion feature
on your calculator. You can use calculators on exam
Bah! I thought we were talking
about Binary DATA!!!
Yah, we were!
How many binary DIGITS does it take
to represent our data??
Binary Codes
One Binary Digit (one bit) can take on values 0, 1.
We can represent TWO values:
(0 = hot, 1 = cold), (1 = True, 0 = False),
(1 = on, 0 = off).
Two Binary digits (two bits) can take on values of
00, 01, 10, 11. We can represent FOUR values:
(00 = hot, 01 = warm, 10 = cool, 11 = cold).
Three Binary digits (three bits) can take on values of
000, 001, 010, 011, 100, 101, 110, 111. We can
represent 8 values
000 = Black, 001 = Red, 010 = Pink, 011 = Yellow,
100 = Brown, 101 = Blue, 110 = Green , 111 = White.
Binary Codes (cont.)
N bits (or N binary Digits) can represent 2N different values.
(for example, 4 bits can represent 24 or 16 different values)
N bits can take on unsigned decimal values from 0 to 2N-1.
Codes usually given in tabular form.
000
001
010
011
100
101
110
111
black
red
pink
yellow
brown
blue
green
white
Code
Conversions
( )2
( )4
( )8
( )16
• To convert a binary number to a system
which is base-2z, group digits together by
z and convert each group separately
• 100111.1010 ---> ( )16
2
7
. A
Converting from
binary base hex as
an example of base
2Z
Conversion of Any Base to
Decimal
Converting from ANY base to decimal is done by multiplying
each digit by its weight and summing.
Binary to Decimal
% 1011.11 = 1x23 + 0x22 + 1x21 + 1x20 + 1x2-1 + 1x2-2
= 8
+ 0 + 2 + 1 + 0.5 + 0.25
= 11.75
Hex to Decimal
$ A2F = 10x162 + 2x161 + 15x160
= 10 x 256
+ 2 x 16 + 15 x 1
= 2560 + 32 + 15 = 2607
Conversion ( ) I
( )10
• express number as a power series in I,
and add all terms using decimal addition
Converting from
base I to decimal
Decimal-to-Radix-r
Conversions
• Radix-r-to-decimal conversions are easy
since we do arithmetic in decimal.
• However, decimal-to-radix-r conversions
using decimal arithmetic is harder.
• To do the latter conversion, we convert the
integer and fractional parts separately and
add the results afterwards.
Convert ( ) 10
( )r
• Integer part:
– Divide the number and all successive
quotients by r
– accumulate the remainders
• Fractional part:
– Multiply the number and successive fractions
by r
– accumulate the integers
Conversion of Decimal Integer
To ANY Base
Divide Number N by base R until quotient is 0. Remainder at
EACH step is a digit in base R, from Least Significant digit to
Most significant digit.
Convert 53 to binary
Least Significant Digit
53/2 = 26, rem = 1
26/2 = 13, rem = 0
13/2 = 6 , rem = 1
6 /2 = 3, rem = 0
3/2 = 1, rem = 1
1/2 = 0, rem = 1
Most Significant Digit
53 = % 110101
= 1x25 + 1x24 + 0x23 + 1x22 + 0x21 + 1x20
= 32 + 16 + 0 + 4 + 0 + 1 = 53
Decimal-to-Radix-r Conversions:
Integer Part
• Successively divide number by r, taking remainder as
result.
• Example: Convert 5710 to binary.
57 / 2 = 28 remainder 1 (LSB)
/2 = 14 remainder 0
Answer: 1110012
/2 = 7 remainder 0
/2 = 3 remainder 1
/2 = 1 remainder 1
/2 = 0 remainder 1 (MSB)
Decimal-to-Radix-r Conversions:
Fractional Part
• Successively multiply number by r, taking integer part as
result and chopping off integer part before next iteration.
• May be unending!
• Example: convert .310 to binary.
.3 * 2 = .6 integer part = 0
.6 * 2 = 1.2 integer part = 1
.2 * 2 = .4 integer part = 0
.4 * 2 = .8 integer part = 0
.8 * 2 = 1.6 integer part = 1
.6 * 2 = 1.2 integer part = 1, etc.
Answer = .01001
More
Conversion
methods for
common
radices
Least Significant Digit
Most Significant Digit
53 = % 110101
Most Significant Digit
(has weight of 25 or
32). For base 2, also
called Most Significant
Bit (MSB). Always
LEFTMOST digit.
Least Significant Digit
(has weight of 20 or 1).
For base 2, also called
Least Significant Bit
(LSB). Always
RIGHTMOST digit.
Binary Data in your life
The computer screen on your Win 98 PC can be configured for
different resolutions. One resolution is 600 x 800 x 8, which means
that you have 600 dots vertically x 800 dots horizontally, with each
dot using 8 bits to take on 256 different colors. (actually, a dot is
called a pixel).
Need 8 bits to represent 256 colors ( 28 = 256). Total number of
bits needed to represent the screen is then:
600 x 800 x 8 = 3,840,000 bits (or just under 4 Mbits)
Your video card must have at least this much memory on it.
1 Mbits = 1024 x 1024 = 210 x 210 = 220 .
1 Kbits = 1024 = 210.
Addition and
Subtraction
• Use same technique as decimal
• Except that the addition and subtraction
tables are different
• Already seen addition table
– Truth table for Sum and Cout function
Examples of decimal and
corresponding binary additions
Examples of decimal and
corresponding binary subtractions
Binary Addition and Subtraction Table
Subtraction table
borrow in
borrow out
bin
x
y
bout
d
0
0
0
0
0
0
0
1
1
1
0
1
0
0
1
0
1
1
0
0
1
0
0
1
1
1
0
1
1
0
1
1
0
0
0
1
1
1
1
1
Discuss this method in comparison with previous method from the class
to create a subtractor
Addition and Subtraction of Octal
and Hexadecimal Numbers
• Not really too different
• But the addition and subtraction tables must
be developed.
The concept of 10’s
complement
digit
complements
in binary,
octal, decimal
and
hexadecimal
Representation of Negative
Numbers
• More accurately: representation of signed
numbers
– Signed-magnitude representation
– Radix-complement representation
• 2’s-complement representation
– Diminished radix-complement representation
– Ones’ complement representation
– Excess representations
Comparison of decimal and 4-bit numbers.
Complements
Decimal numbers,
their two’s
complements,
ones’
complements,
signed magniture
and excess 2m-1
binary codes
EXPLAIN
Existence of two
zeros!
Signed-magnitude
representation
• Also called, “sign-and-magnitude representation”
• A number consists of a magnitude and a symbol
representing the sign
• Usually 0 means positive, 1 negative
– Sign bit
– Usually the entire number is represented with 1 sign bit
to the left, followed by a number of magnitude bits
Machine arithmetic with signedmagnitude representation
• Takes several steps to add a pair of numbers
– Examine signs of the addends
– If same, add magnitudes and give the result the same
sign as the operands
– If different, must…
• Compare magnitude of the two operands
• Subtract smaller number from larger
• Give the result the sign of the larger operand
• For this reason the signed-magnitude
representation is not as popular as one might think
because of its “naturalness”
Complement number systems
• Negates a number by taking its complement
instead of negating the sign
• Exact meaning of taking its complement is defined
in various ways – will see
• Not natural for humans, but better for machine
arithmetic
• Will describe 2 complement number systems
– Radix complement – very popular in real computers
– Diminished radix-complement – not very useful, may
skip or not spend much time on it
Radix-complement number
representation
• Must first decide how many bits to represent the
number – say n.
• Complement of a number = rn – number
• Example: 4-bit decimal:
– Original number = 3524
– 10’s complement = 10000-3524 = 6476
• 0 and positive numbers: 0000-4999
• Negative numbers: 5000-9999, where 9999 is
‘minus 1.’
Two’s-complement
representation
• Just radix-complement when radix = 2
• Used a lot in computers and other digital
arithmetic circuits
• 0 and positive numbers: leftmost bit = 0
• Negative numbers: leftmost bit = 1
• To find a number’s complement – just flip
all the bits and add 1
• See graphical view – Fig. 2.3, p. 40.
Two’s-Comp Addition and
Subtraction Rules
• Starting from 1000 (-8) on up, each successive 2’s
comp number all the way to 0111 (+7) can be obtained
by adding 1 to the previous one, ignoring any carries
beyond the 4th bit position
• Since addition is just an extension of ordinary
counting, 2’s comp numbers can be added by ordinary
binary addition!
• No different cases based on operands’ signs!
• Overflow possible
– Occurs if result is out of range
– To detect – happens if operands are the same sign but sum is
a different sign of that of the operands
Modular Counting representation
of Two’s Complements
Unsigned Numbers
Modular Counting representation of unsigned numbers
Rules for addition and subtraction
DECIMAL
CODES
Codes for Decimal Digits
There are even codes for representing decimal digits. These
codes use 4-bits for EACH decimal digits; it is NOT the same
as converting from decimal to binary.
BCD Code
0 = % 0000
1 = % 0001
2 = % 0010
3 = % 0011
4 = % 0100
5 = % 0101
6 = % 0110
7 = % 0111
8 = % 1000
9 = % 1001
In BCD code, each decimal digit simply
represented by its binary equivalent.
96 = % 1001 0110 = $ 96 (BCD code)
Advantage: easy to convert
Disadvantage: takes more bits to store a number:
255 = % 1111 1111 = $ FF (binary code)
255 = % 0010 0101 0101 = $ 255 (BCD code)
takes only 8 bits in binary, takes 12 bits in BCD.
Binary code for decimal numbers
•
•
•
•
Any encoding needs at least 4 bits/decimal digit
BCD (8421), a weighted code
Packed BCD
2421 code
– Self-complementing: the code for the 9s’ comp of any
digit may be obtained by complementing the individual
bits of the digit’s code word
• Excess 3
– Not a weighted code, but is also self-complementing
– Since code follows standard binary counting sequence,
standard binary counters can easily be made to count in
excess-3
Biquinary code
• Uses more than 4 bits
• First 2 bits indicate whether the number is in the
range 0-4 or 5-0
– One-hot
• Last 5 bits indicate which of the five numbers in the
selected range is represented
– Also one-hot
• Advantage: error-detection property. If any 1 bit in a
code word is accidentally changed to the opposite
value, the resulting code word doesn’t represent a
decimal digit at all – flagged as error.
Codes for Characters
Also need to represent Characters as digital data.
The ASCII code (American Standard Code for
Information Interchange) is a 7-bit code for Character
data. Typically 8 bits are actually used with the 8th bit
being zero or used for error detection (parity checking).
8 bits = 1 Byte.
‘A’ = % 01000001 = $41
‘&’ = % 00100110 = $26
7 bits can only represent 27 different values (128). This
enough to represent the Latin alphabet (A-Z, a-z, 0-9,
punctuation marks, some symbols like $), but what about
other symbols or other languages?
UNICODE
UNICODE is a 16-bit code for representing alphanumeric data.
With 16 bits, can represent 216 or 65536 different symbols.
16 bits = 2 Bytes per character.
$0041-005A A-Z
$0061-4007A a-z
Some other alphabet/symbol ranges
$3400-3d2d
$3040-318F
$4E00-9FFF
Korean Hangul Symbols
Hiranga, Katakana, Bopomofo, Hangul
Han (Chinese, Japenese, Korean)
UNICODE used by Web browsers, Java, most software these
days.
0+3=3.
1+3=4 etc
Always
two 1’s
Decimal codes
GRAY CODES
and mechanical
encodings
A mechanical
Encoding Disk
Two bits change in
natural binary code
Gray Code for decimal Digits
Gray Code
0 = % 0000
1 = % 0001
2 = % 0011
3 = % 0010
4 = % 0110
5 = % 1110
6 = % 1010
7 = % 1011
8 = % 1001
9 = % 1000
A Gray code changes by only 1 bit for
adjacent values. This is also called a
‘thumbwheel’ code because a thumbwheel
for choosing a decimal digit can only
change to an adjacent value (4 to 5 to 6,
etc) with each click of the thumbwheel.
This allows the binary output of the
thumbwheel to only change one bit at a
time; this can help reduce circuit
complexity and also reduce signal noise.
Binary vs Gray Codes
You should be able
to design binary to
Gray code
converter in both
directions
Always one bit
changes only
A mechanical
disk for Gray
Code
7 bit
ASCII
code
You should be able
to design a
converter in both
directions from any
code to any other
code!
Example of sequence generator machine
with controlling counter machine
Controlling many devices with binary and
one-hot codes
Error
Correcting
Codes
The concept of a hypercube
Even-parity and odd-parity codes
Space of codes for 7 bits with code words and non-code words
8-bit,
distance
4 codes
Hamming
Codes
Examples of
Hamming
Codes
7 bit
Hamming
codes
Extended Hamming Codes
Two
dimensional
codes
Error-correcting code for a RAID system
Serial data transmission
Well-known codes for serial data
transmission
Multiplication
and Division
Intro
Binary multiplication
• Grammar school method for decimal: add a list of
shifted multiplicands computed according to the
digits of the multiplier
• Same method can be used in binary
• For two unsigned operands, the only possible
values of the multiplier digits are 0 and 1
– Thus it’s trivial to form the shifted multiplicands
Binary multiplication in binary
on a machine
• More convenient to add each shifted multiplicand
as it is created to a partial product
• Will do an example.
• In general when we multiply an n-bit number by an
m-bit number, the result requires at most n+m bits
to express
• The shift-and-add algorithm requires m partial
products and additions to obtain result, but the 1st
addition is trivial (adding to 0)
Long Division
Homework problem 1
Convert the following binary numbers to
decimal:
•1011011.0110
•00110.11001
Homework problem 2
Convert from decimal to binary:
•0.5
•73.426
•290.9
Homework problem 3
Convert from Binary to Octal:
•1 101 011 110 111
•11 011.101 1
Homework problem 4
• Calculate 191+141 (Let’s first convert these
to binary as an exercise.) Verify in decimal
• 210 – 109, calculate first binary numbers.
Verify.
Homework problem 5
1. Discuss how to convert hex, binary integers
to Decimal
2. Discuss how to convert decimal integers to
hex, binary
3. Discuss how to convert hex to binary, binary
to Hex
4. Explain why N binary digits can represent 2N
values, unsigned integers 0 to 2N-1.
sources
• Bob Reese
• Wakerly
• Other from internet