Transcript 01_Chapter 1 - Number Systems Base

Number Systems
Decimal, Binary, and Hexadecimal
1
Positional Notation
2
Positional Notation
A positive number N can be written as:
N  (an1an2 .....a1a0 .a1a2 .....am )r
Where:
3
Definitions
Where:
. = radix point
r = radix or base of number system
n = number of integer digits to the left of radix point
m = number of fractional digits to the right of radix point
ai = integer digit i
aj = fractional digit j
an-1 = most significant digit
a -m = least significant digit
4
Examples
(1920)10  1920


Base 10 or decimal number
Unless otherwise noted, assume base 10
(10010101)2  100101012

Base 2 or binary number
(95)16  9516

Base 16 or Hex number
5
Online HW Assignments
(1920)10  1920

Base 10 or decimal number
(10010101)2  %10010101

Base 2 or binary number
(95)16  $95

Base 16 or Hex number
6
Polynomial Notation
A positive number N can also be written as:
N
n 1
ar
i  m
Example:
i
i
1325  1x10  3x10  2 x10  5x10
1325  1x1000  3x100  2 x10  5x1
1325  1000  300  20  5
3
2
1
0
7
Common Number
Systems
8
Decimal Number System
Radix or Base 10
Digits: 0, 1,2,3,4,5,6,7,8,9
Example: 104510
First 17 positive integers
0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16
9
Binary Number System
Radix or Base 2
Digits: 0, 1
Example: 10101102
First 17 positive integers
0,1,10,11,100,101,110,111,1000,1001,1010,1
011,1100,1101,1110,1111,10000
10
Hexadecimal Number System
Radix or Base 16
Digits: 0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F
Example: EF5616
First 17 positive integers
0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F,10
11
Summary
Dec
Bin
Hex
Dec
Bin
Hex
0
1
2
3
0000
0001
0010
0011
0
1
2
3
8
9
10
11
1000
1001
1010
1011
8
9
A
B
4
0100
4
12
1100
C
5
0101
5
13
1101
D
6
0110
6
14
1110
E
7
0111
7
15
1111
F
12
Decimal Arithmetic
Addition
Subtraction
Multiplication
Division
13
Decimal Addition Table
+
0
1
2
3
4
5
6
7
8
9
10
0
0
1
2
3
4
5
6
7
8
9
10
1
1
2
3
4
5
6
7
8
9
10
11
2
2
3
4
5
6
7
8
9
10
11
12
3
3
4
5
6
7
8
9
10
11
12
13
4
4
5
6
7
8
9
10
11
12
13
14
5
5
6
7
8
9
10
11
12
13
14
15
6
6
7
8
9
10
11
12
13
14
15
16
7
7
8
9
10
11
12
13
14
15
16
17
8
8
9
10
11
12
13
14
15
16
17
18
9
9
10
11
12
13
14
15
16
17
18
19
10
10
11
12
13
14
15
16
17
18
19
20
14
Example
Add the following decimal numbers
199
+ 73
15
Solution
Add the following decimal numbers
1 1
199
+ 73
27 2
16
Solution
Subtract the following decimal numbers
123
- 77
17
Solution
Subtract the following decimal numbers
1
123
- 77
6
18
Solution
Subtract the following decimal numbers
1 1
113
- 77
46
19
Solution
Subtract the following decimal numbers
1 1
013
- 77
04 6
20
Decimal Multiplication Table
*
0
1
2
3
4
5
6
7
8
9
10
0
0
0
0
0
0
0
0
0
0
0
0
1
0
1
2
3
4
5
6
7
8
9
10
2
0
2
4
6
8
10
12
14
16
18
20
3
0
3
6
9
12
15
18
21
24
27
30
4
0
4
8
12
16
20
24
28
32
36
40
5
0
5
10
15
20
25
30
35
40
45
50
6
0
6
12
18
24
30
36
42
48
54
60
7
0
7
14
21
28
35
42
49
56
63
70
8
0
8
16
24
32
40
48
56
64
72
80
9
0
9
18
27
36
45
54
63
72
81
90
10
0
10
20
30
40
50
60
70
80
90
100
21
Example
Multiply the following decimal numbers
72
x 23
22
Solution
Multiply the following decimal numbers
72
x 23
216
1440
1656
Multiplicand
Multiplier
Partial Products
Product
23
Example
Divide the following decimal numbers
3
23
24
Example
Divide the following decimal numbers
07
Divisor
3
23
0
23
21
2
Quotient
Dividend
Remainder
25
Binary Arithmetic
26
Binary Addition
•Single Bit Addition Table
0 + 0 = 0
0 + 1 = 1
1 + 0 = 1
1 + 1 = 10
Note “carry”
27
Example
Add the following binary numbers
1101
+0 1 1 1
28
Solution:
Add the following binary numbers
1 1
1101
+0 1 1 1
10100
29
Binary Subtraction
•Single Bit Subtraction Table
0 - 0 = 0
1 - 0 = 1
1 - 1 = 0
0 - 1 = 1 with a “borrow”
30
Example
Subtract the following binary numbers
1101
-0111
31
Solution:
Subtract the following binary numbers
1
1 1
00
1
101
-0111
0110
32
Collaborative Learning
Learning methodology in which
students are not only responsible
for their own learning but for the
learning of other members of the
group.
33
Think - Pair - Share (TPS)
Quizzes
Think – Pair – Share




Think individually for one time units
Pair with partner for two time units
Share with group for one and half time units
Report results
34
TPS Quiz
THINK
One Unit
(e.g. 30 Seconds)
35
TPS Quiz
PAIR
Two Units
(e.g. 60 Seconds)
36
TPS Quiz
SHARE
1.5 units
(e.g. 45 Seconds)
37
TPS QUIZ
Report
38
TPS Quiz
#1-2-3
39
Binary Multiplication
•Single Bit Multiplication Table
0
1
0
0
0
1
0
1
40
Binary Multiplication
•Single Bit Multiplication Table
0 x 0 = 0
0 x 1 = 0
1 x 0 = 0
1 x 1 = 1
41
Example
Multiply the following binary numbers
1101
x0111
42
Solution
Multiply the following binary numbers
1101
x0111
1101
11010
110100
0000000
1011011
Partial Products
43
Binary Division
•Single Bit Division Table
0 / 0 = N/A
0 / 1 = 0
1 / 0 = N/A
1 / 1 = 1
44
Example
Divide the following binary numbers
111
1101
45
Solution
Divide the following binary numbers
Quotient
0 0 01
Divisor
111
1101
Dividend
0
11
00
110
000
1101
111
110
Remainder
46
Hexadecimal Arithmetic
47
Hexadecimal Addition Table
+
0
1
2
3
4
5
6
7
8
9
A
0
0
1
2
3
4
5
6
7
8
9
A
1
1
2
3
4
5
6
7
8
9
A
B
2
2
3
4
5
6
7
8
9
A
B
C
3
3
4
5
6
7
8
9
A
B
C
D
4
4
5
6
7
8
9
A
B
C
D
E
5
5
6
7
8
9
A
B
C
D
E
F
6
6
7
8
9
A
B
C
D
E
F
10
7
7
8
9
A
B
C
D
E
F
10
11
8
8
9
A
B
C
D
E
F
10
11
12
9
9
A
B
C
D
E
F
10
11
12
13
A
A
B
C
D
E
F
10
11
12
13
14
48
Example
Add the following hexadecimal numbers
AF
+ 1B
49
Solution
Add the following hexadecimal numbers
1
AF
+ 1B
CA
50
Example
Subtract the following hexadecimal
numbers
AB
- 1D
51
Solution
Subtract the following hexadecimal
numbers
AB
- 1D
9 1
AB
- 1D
E
9 1
AB
- 1D
8E
10-D+B=3+B=E
52
TPS Quiz
#4-5-6
53
Conversion Methods
54
Series Substitution
Expand number in original base using
N
n 1
 ar
i  m
N  an1r n1  an2r n2 
i
i
 a1r  a0 
 amr m
55
Binary to Decimal
Example – Convert N  10102 to Base 10
n1
N  an1 2
n 2
 an2 2

 a1 2  a0
N  1x2  0 x2  1x2  0 x2
3
2
1
0
N  810  0  210  0  1010
N  1010
56
Hex to Decimal
Example – Convert N  CD16 to Base 10
n1
N  an116
n 2
 an216

 a116  a0
N  12 x16  13
1
N  20510
57
Radix Divide Method
Convert N in base A to base B
Note: N can be expanded in base B using
NA 
OR
N A  bn1B
n1
n 1
bB
i  m
 bn2 B
i
i
n 2

 b1B  b0
We know B, but how do we find the bi’s
58
Radix Divide Method
We can divide N by B to find
N A bn 1 B

B
n 1
 bn 2 B
n2

 b1B  b0
B
NA
n2
n 3
Q1 
 bn 1 B  bn  2 B 
B
Remainder
b0
 b1 
B
Quotient
59
Radix Divide Method
So
b0
NA
B
is the remainder of
We can repeat the division to find
Q1 bn 1 B
Q2 

B
Q2  bn 1 B
Or
b1
n 3
n2
 bn  2 B
 bn 2 B
B
n4

is the remainder of
n 3

 b1
b1
 b3 B  b2 
B
Q1
B
60
Radix Divide Method
We can repeat the division until
Qn  0
The remainder is
bn 1
61
Example
Decimal to Binary Conversion
782
2 156410
391
2 78210
195
2 39110
97
2 19510
R0
R0
R 1
R 1
48
2 9710
24
2 4810
12
2 2410
6
2 1210
3
R 1
R0
R0
2 610 R  0
1
2 310 R  1
0
2 110
R 1
R0
110000111002
62
Example
Decimal to Hex Conversion
N  156410
97
16 156410 R  12  C
6
16 9710 R  1  1
0
16 610 R  6  6
N  156410  61C16
63
Hex to Binary Conversion
Binary to Hex Conversion
Use the conversion table
Bin
0000
Hex
0
Bin
0100
Hex
4
Bin
1000
Hex
8
Bin
1100
Hex
C
0001
0010
0011
1
2
3
0101
0110
0111
5
6
7
1001
1010
1011
9
A
B
1101
1110
1111
D
E
F
64
Binary to Hex Conversion
1. Divide binary number into 4-bit groups
01 1 0 0 0 0 1 1 1 0 0
Pad with 0’s if
unsigned number
2. Substitute hex digit for each group
Pad with sign bit
if signed number
61C16
65
Hex to Binary Conversion
Convert each hex digit into equivalent binary
number
1E3F16
00011110001111112
66
TIP
Binary to decimal conversions
1. Convert binary to hex
2. Convert hex to decimal
Example: Convert 101010102 to Dec
(assume unsigned numbers)
101010102  $AA = 16*10+10=170
Check
27+25+23+21=128+32+8+2=170
67
TPS Quiz
#7-8-9
68
Signed Numbers
69
Signed Numbers
Two methods:

Signed-magnitude
Use one digit (character) to represent the sign

Example: + = positive, - = negative
Remaining bits are used to represent the magnitude
Ex: +109 or -234
Digital arithmetic circuitry would be large and slow.

Signed-complement
Use the radix complement of N to represent –N
This method is used in digital logic design
70
Radix Complements
71
Definition
Radix Complements
 N r  r   N r
n
Where
 N r
 N r
r
n
= Radix Complement of N
= Original Number, N
= radix or base
= number of digits
72
Definition
Note:
 N r   N r  r   N r   N r  r
n
n
Or,
N added to its complement is equal to rn
But this is just 0, if we ignore the Most
Significant Digit (MSD)
73
Radix Complements
Two’s Complement
 N 2  2   N 2
n
Ten’s Complement
 N 10  10   N 10
n
74
Radix Complements
16’s Complement
 N 16  16   N 16
n
75
Example
Calculate the 10’s complement of
N= 3 Let n=1
 N 10  10  310
 N 10  10  3  7
1
 N    N   3  7  10  10
1
76
Example
Calculate the two’s complement of
N= 00100110. Let n=8
 N 2  2  001001102
8
 N 2  1000000002   001001102
 N 2  11011010
77
Properties
 N 2   N 2  2   N 2   N 2
n
*
 N 2   N 2  2  0
n
 N 2    N 2
Or, the two’s complement of N is the same as -N
* Ignoring the most significant digit which will always be 1
78
Properties
 N 2   2   2  N 
2
 N 2      N   N
n
n
2
 N 2   N
2
The two’s complement of the two’s complement of N is just N.
Recall
 N 2    N 2 ,SO
 N 2      N   N
79
Example
 N 2  001001102  N 2  11011010
Let’s find
 N r   N r
11011010
Throw this away
So,
00100110
1000000002
 N r
 N r
 N r   N r  00000000
80
Definition
Diminished Radix Complements
 N r 1  r   N r 1
n
where
r = radix or base
n = number of digits
Note:
ai  r 1  ai
ai = digit to convert
81
One’s Complement
One’s complement (Diminished)
So
Or,
 N 1  2   N r 1
n
ai  2 1  ai  1  ai
But, 1-0=1 and 1-1=0, or to calculate the 1’s
complement of a binary number just “flip” or
complement each bit of the original binary number.
E.g. 0  1 and 1  0
Example:
01010100100  10101011011
82
Two’s Complement
We have,
 N 2  2   N 2
n
But this is just
 N 2  2   N 2 11
 N 2   N 1 1
n
Or,
83
Two’s Complement
Two’s complement calculation method #2

To calculate the 2’s complement just calculate
the 1’s complement and add 1.
Example: With N= 001001102 , we found
 N 2  11011010
Let’s calculate the 2’s complement of N using its 1’s complement
N  00100110  N 1  11011001
 N 2   N 1 1  11011010
84
Two’s Complement
Two’s complement calculation method #3

Leave all of the least significant 0’s and first 1
unchanged and then “flip” or complement the bits for
all other digits.
Example: Calculate the 2’s complement of
N  00100110
Leave these bits alone
Complement these bits
We have
 N 2  11011010
85
Summary
Two’s complement calculations
Method 1
 N 2  2   N 2
n
Method 2
 N 2   N 1 1
Method 3
Leave all of the least significant 0’s and
first 1 unchanged and then “flip” or
complement the bits for all other digits
86
16’s Complement
The 16’s complement of a 16 bit (or 4
digit) hexadecimal number is:
 N 16  16   N 16
 N 16  10000   N 16
4
Example, let N= $B2CE
 N 16  $10000  $B2CE  $4D32
87
Signed Binary Numbers
88
Signed Binary Numbers
Use 2’s complement of N to represent –N

Signed binary  2’s complement
If MSB of N is 0, N is positive
If MSB of N is 1, N is negative
Range of signed binary numbers is:
n1
2
n1
1 to  2
Range of unsigned binary numbers is:
2 1 to 0
n
89
Binary Numbers – 4-bit example
Binary
Signed
Decimal
Unsigned
Decimal
Binary
Signed
Decimal
Unsigned
Decimal
0000
0
0
1000
-8
8
0001
1
1
1001
-7
9
0010
2
2
1010
-6
10
0011
3
3
1011
-5
11
0100
4
4
1100
-4
12
0101
5
5
1101
-3
13
0110
6
6
1110
-2
14
0111
7
7
1111
-1
15
90
Procedure to Convert 2’s
complement to decimal
To convert a 2’s complement number (or
signed binary) into its decimal equivalent. We
first check the MSB

If MSB=0, the number is positive and we
a) calculate its decimal equivalent as before.

If MSB=1, the number is negative, we
a) calculate its 2’s complement to obtain its magnitude
b) calculate its decimal equivalent as before
c) Add the minus sign (-) to the decimal result to indicate it is
negative.
91
Example
Assume signed 2’s complement numbers,
let N=4,
What is the decimal equivalent of
N  1111
Since MSB=1, this is a negative number.
We need to calculate its 2’s complement to
determine its magnitude
Let’s use all three methods to calculate
 N 2
92
Example
N  1111
Method 1
 N 2  2   N   10000 1111  0001
4
Method 2
 N 2   N 1 1  0000 1  0001
Method 3
 N 2  0001
Leave LSB 0’s and first 1 alone, flip all other bits.
93
Example
So, as a signed 2’s complement number
N  11112  110
94
Example
Assume signed 2’s complement numbers,
let n=8,
What is the decimal equivalent of
N  11011011
Since MSB=1, this is a negative number,
we need to calculate its 2’s complement to
determine its magnitude
 N 2  001001012  2516  3710
So,
N  110110112  3710
95
Very Important!!! – Unless otherwise stated
assume signed-complement numbers for all
problems, quizzes, HW’s, etc.
96
Binary Subtraction
97
Binary Subtraction
Note:




A – (+B) = A + (-B)
A – (-B) = A + (-(-B))= A + (+B)
In other words, we can “subtract” B from A by
“adding” –B to A.
However, -B is just the 2’s complement of B,
so to perform binary subtraction, we
1. Calculate the 2’s complement of B
2. Add A + (-B)
98
Binary Subtraction - Example
Let n=4, A=01002 (410), and B=00102 (210)
Let’s find A+B, A-B and B-A
A+B
0 1 0 0  (4)10
+ 0 0 1 0  (2)10
0110
6
99
Binary Subtraction - Example
A-B
A+ (-B)
0 1 0 0  (4)10
- 0 0 1 0  (2)10
0 1 0 0  (4)10
+ 1 1 1 0  (-2)10
10 0 1 0
2
“Throw this bit” away since n=4
100
Binary Subtraction - Example
B-A
B + (-A)
0 0 1 0  (2)10
- 0 1 0 0  (4)10
0 0 1 0  (2)10
+ 1 1 0 0  (-4)10
1110
-2
1 1 1 02 = - 0 0 1 02 = -210
101
Sign Extension
102
Sign Extension
Assume a signed 2’s complement system
Let A = 0101 (4 bits) and B=010 (3 bits)
What is A+B?


To add these two values we need A and B to
be of the same bit width.
Do we truncate A to 3 bits or add an
additional bit to B?
103
Sign Extension
A = 0101 and B=010
Can’t truncate A!! Why?




A: 0101  101
But 0101 <> 101 in a signed system
0101 = +5
101 = -3
104
Sign Extension
Must “sign extend” B,
so B becomes 010  0010
Note: Value of B remains the same
So
0101 (5)
+0010 (2)
Sign bit is extended
-------0111 (7)
105
Sign Extension
What about negative numbers?
Let A=0101 (+5) and B=100 (-4)
Now B = 100  1100
0101
+1100
------10001
Sign bit is extended
(+5)
(-4)
(1)
Throw away
106
TPS Quiz
# 10-11-12
107
Computer Codes
108
Binary Coded Decimals
(BCDs)
Dec
Use a 4-bit code to represent
each decimal digit.
Example: 123410


%0001001000110100
In hex, $1234
Note: As a signed decimal,
$1234 is not equal to 123410
but 466010
0
1
2
3
Bin
0000
0001
0010
0011
4
0100
5
0101
6
0110
7
0111
8
1000
9
1001
109
ASCII
American Standard Code for
Information Interchange
7-bit character code used in computer
applications. (8-bit code called extended
ASCII) See Table 1.11
For Example,



‘1’ = %0110001 = $31
‘A’ = %1000001 = $41
‘a’ = %1100001 = $61
110
Important!!
The logic designer determines what a
binary number represents?
For example,

What is “10010111” in the following
connotations?
As a unsigned binary = 151
As a signed binary = -104
As a BCD (Binary Coded Decimal) = 97
As an ASCI Character = “—”
Em dash
111
Fractional Numbers
112
Fractional Numbers
Recall 20=1, 21=2, 22=4, ….
But, we can also go the other way

2-1=0.5, 2-2=0.25, 2-3=0.125, 2-4=0.0625,…
In general, we have 2-n=1/2n
So, for example, to represent


2.5 = 10.102 = %1010 and
5.25 = 101.012 = %10101
Check: 2+0+0.5+0=2.5
Check: 4+0+1+0+0.25=5.25
113
Fractional Numbers
We have

2.5 = %10.10 and 5.25 = %101.01
As 8 bit numbers, these become

%000010.10 and %000101.01
Now, we really DON’T have a way to represent the
binary point in our numbers, so we have to remember
where it is located.
So really, we have
2.5 = %00001010 = $0A
5.25 = %00010101 = $15
And we remember that we are using 2 bits for the
fractional part.
114
Fractional Numbers
Let’s use 16-bit numbers where 4-bits are
reserved for the fractional part
So, Y = $NNN.N
Example, What is 375.875 in Hex?
375  $177
0.875 = 1*0.5+1*0.25+1*0.125+0*0.0625

= %1110 = $E
Or, 375.875 = $177E
115
Fractional Numbers
Example, What is $24E3 as a fractional
decimal?
$24E  59010
$3 =
0*0.5+0*0.25+1*0.125+1*0.0625=0.1875
Or, $24E3 = 590.1875
116