Transcript Introduction: Number Systems

0907231 Digital Logic
Dr. Walid Abu-Sufah
Based on notes by A. Lastra and slides provided by the text publisher
Instructor (Sections 2 & 3)
•
•
•
•
Instructor: Dr. Walid Abu-Sufah
Office: CPE 10
Email: [email protected]
Office Hours: Monday 11-12, Tuesday 121 and by appointment.
• Course web site:
http://www1.ju.edu.jo/ecourse/abusufah/
cpe231_spr12/index.html
CPE 432 Computer
2
Prerequisite
• 1900100 Computer Skills
3
Textbook
• Logic and Computer Design
Fundamentals, M. Morris Mano and
Charles R. Kime (4th edition, 2008).
Prentice Hall.
4
Grading Policy
• Quizzes
• Homeworks
• Mid-term Exam
16%
4%
30%
♦ Saturday, March 31; 2-3:15
• Final Exam
50%
♦ Tuesday, May 22; 2-4 PM
• Visit course website for updates on
dates of exams, quizzes, and
homeworks
5
Policies: The Course Web Site
• Class announcements, such as
homework/quizzes dates and changes in
assignments, will be posted on the Web.
• You are therefore responsible for checking the
course web site. If you make an error because
you did not check the Web, I will hold you fully
responsible.
6
Policies: Homework and Quizzes
• Four homeworks
• Due at the beginning of the first lecture in
the weeks indicated in the course calendar
on the website.
• No late homework will be accepted.
• One quiz will be given at the beginning of
the same lecture when each of the four
homeworks is collected. The quiz will be
based on the homework.
• For each student, the lowest of the 4 grades
of quizzes will be dropped.
• As a result, there will be no make-up quizzes
for any reason.
7
Policies: Makeup Midterm
 There will be no make-up for the midterm. In
case of medical/ or other DISABLING
emergencies, the instructor should be notified
BEFORE the midterm and his approval for
missing the midterm should be obtained
before the midterm. If for any reason the
instructor could not be reached, the
department secretary should be notified
before the midterm. The phone number is 5355000 Extension 23000.
8
Policies: Grading
Corrections
 Ask the instructor for any grading
correction requests within a week of
returning the exam/quiz papers. After
that, your grade will not be
adjusted. If you find any mistake in
grading, please let the instructor
know. Your grade will not be
lowered.
9
Policies: Class Attendance
 Class attendance will be taken.
University regulations regarding
attendance will be strictly enforced. If
you miss class, you must obtain the
covered material from a willing
classmate and/or the course web
site. The instructor will not be
available (during office hours or
other times) to repeat material
covered.
10
Policies: Academic Honesty
• Your work in this class must be your
own.
• Penalties for excessive
collaboration and cheating are
severe.
• Sharing homework answers is
forbidden
11
Today’s Topics
• Material from Chapter 1
♦
♦
♦
♦
What is digital logic?
Binary signaling
Number systems
Codes
12
What’s Course About?
• Digital logic focusing on the design of
computers
• Stay above transistor level
• High-level Hardware Description
Language, HDL
♦ Allows Staying above logic gate level
♦ Will be covered in the lab course
13
How Can We Do This?
• Field Programmable Gate Arrays
♦ Chips with a lot of circuits
• Tens of thousands to millions of transistors
♦ Programmable
• We write “programs” describing
design
• Tools translate to gates/wires
• Download pattern to chip
14
Schematic Diagram
15
Discrete Data
• Some data inherently discrete
♦ Names (sets of letters)
• Some quantized
♦ Music recorded from microphone
♦ Note that other examples like music from CD
or electronic keyboard already quantized
16
INFORMATION REPRESENTATION - Signals
 Information variables represented by physical
quantities.
 For digital systems, the variables take on discrete
values.
 Two level, or binary values are used in digital systems
 Binary values are represented by:
•
•
•
•
digits 0 and 1
words (symbols) False (F) and True (T)
words (symbols) Low (L) and High (H)
and words On and Off.
Chapter 1
17
Signal Example – Physical Quantity: Voltage
Threshold
Region
18
Signal Examples Over Time
Time
Analog
Digital
Asynchronous
Synchronous
Continuous in
value & time
Discrete in
value &
continuous
in time
Discrete in
value & time
19
Numbers and Arithmetic
• Review of binary numbers,
• Hexadecimal numbers,
• Arithmetic
20
Binary Numbers
• Strings of binary digits (“bits”)
♦ One bit can store a number from the set (0 , 1)
♦ n bits can store numbers from 0 to 2n-1
21
Binary – Powers of 2
• Positional representation
• Each digit represents a power of 2
So 101 binary is
1 • 22 + 0 • 21 + 1 • 20
or
1•4 + 0•2 + 1•1=5
22
Converting Binary to Decimal
• Easy, just multiply digit by power
of 2
• Just like a decimal number is
represented
• Example follows
23
Binary  Decimal Example
7
6
5
4
3
2
1
0
27
26
25
24
23
22
21
20
128 64
32
16
8
4
2
1
1
0
0
What is 10011100 in decimal?
1
0
0
1
1
128 + 0 + 0 + 16 + 8 + 4 + 0 + 0 = 156
24
Decimal to Binary
• A little more work than binary to
decimal
• Some examples
♦ 3 = 2 + 1 = 11 (that’s 1•21 + 1•20)
♦ 5 = 4 + 1 = 101 (that’s 1•22 + 0•21 + 1•20)
25
Algorithm – Decimal to Binary
1. Find largest power-of-two smaller
than decimal number
2. Make the appropriate binary digit
a ‘1’
3. Subtract the “power of 2” from
decimal
4. Do the same thing again
26
Decimal  Binary Example
• Convert 28 decimal to binary
32 is too large, so use 16
Binary  10000
Decimal  28 – 16 = 12
Next is 8
Binary  11000
Decimal  12 – 8 = 4
Next is 4
Binary  11100
Decimal  4 – 4 = 0
27
Hexadecimal
• Strings of 0s and 1s too hard to write
• Use base-16 or hexadecimal – 4 bits
Dec
Bin
Hex
Dec
Bin
Hex
0
0000
0
8
1000
8
1
0001
1
9
1001
9
2
0010
2
10
1010
?
3
0011
3
11
1011
?
4
0100
4
12
1100
?
5
0101
5
13
1101
?
6
0110
6
14
1110
?
7
0111
7
15
1111
?
28
Hexadecimal
• Letters to represent 10-15
Dec
Bin
Hex
Dec
Bin
Hex
0
0000
0
8
1000
8
1
0001
1
9
1001
9
2
0010
2
10
1010
a
3
0011
3
11
1011
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
Why use
base 16?
•Power of 2
•Size of byte
29
Hex to Binary
• Convention – write 0x before number:
0x2ac or (2ac)16
• Hex to Binary – just convert digits
0x2ac
0010
1010 1100
(2ac)16 = 0x2ac = 001010101100
No magic – remember hex digit = 4 bits
Bin
Hex
0000
0
0001
1
0010
2
0011
3
0100
4
0101
5
0110
6
0111
7
1000
8
1001
9
1010
a
1011
b
1100
c
1101
d
1110
e
1111
f
30
Binary to Hex
• Just convert groups of 4 bits
101001101111011
0101  0011  0111  1011
5
3
7
b
101001101111011 = 0x537b = (537b)16
Bin
Hex
0000
0
0001
1
0010
2
0011
3
0100
4
0101
5
0110
6
0111
7
1000
8
1001
9
1010
a
1011
b
1100
c
1101
d
1110
e
1111
f
31
Hex to Decimal
• Just multiply each hex digit by a
decimal value which is its
positional weight, and add the
results.
0x2ac
2 • 256
+ 10 • 16 + 12 • 1 = 684
   
163
162
161
160
4096
256
16
1
Dec Hex
0
0
1
1
2
2
3
3
4
4
5
5
6
6
7
7
8
8
9
9
10
a
11
b
12
c
13
d
14
e
15
f32
Decimal to Hex
1.
2.
3.
4.
Analogous to decimal  binary.
Find largest power-of-16
smaller than decimal number
Divide by power-of-16. The
integer result is hex digit.
The remainder is new decimal
number.
Do the same thing again
33
Dec Hex
Decimal to Hex
684
684/256 = 2
0x2__
684%256 = 172
0x2a_
172/16 = 10 = a
172%16 = 12 = c 0x2ac
   
163
162
161
160
4096
256
16
1
0
0
1
1
2
2
3
3
4
4
5
5
6
6
7
7
8
8
9
9
10
a
11
b
12
c
13
d
14
e
15
f34
Octal
• Octal is base 8
• Similar to hexadecimal
♦ Conversions
• Less convenient for use with 8-bit
bytes
35
In General:
NUMBER SYSTEMS – Representation
 Positive radix, positional number systems
 A number with radix r is represented by a
string of digits:
An - 1An - 2 … A1A0 . A- 1 A- 2 … A- m + 1 A- m
in which 0 Ai < r and . is the radix point.
 The string of digits represents the power series:
(
i=n-1
(Number)r =
i=0
Ai
r )+( 
j=-1
i
Aj
r)
j
j=-m
(Integer Portion) + (Fraction Portion)
Chapter 1
36
Number Systems – Examples
Radix (Base)
Digits
0
1
2
3
Powers of 4
Radix
5
-1
-2
-3
-4
-5
General
Decimal
Binary
r
10
2
0 => r - 1
0 => 9
0 => 1
r0
r1
r2
r3
r4
r5
r -1
r -2
r -3
r -4
r -5
1
10
100
1000
10,000
100,000
0.1
0.01
0.001
0.0001
0.00001
1
2
4
8
16
32
0.5
0.25
0.125
0.0625
0.03125
Chapter 1
37
Special Powers of 2
 210 (1024) is Kilo, denoted "K"
 220 (1,048,576) is Mega, denoted "M"
 230 (1,073, 741,824)is Giga, denoted "G"
 240 (1,099,511,627,776 ) is Tera, denoted “T"
Chapter 1
38
Conversion Between Bases
 Method 2
 To convert from one base to another:
1) Convert the Integer Part
2) Convert the Fraction Part
3) Join the two results with a radix point
39
Example: Convert 46.687510 To Base 2
 Convert 46 to Base 2
 Convert 0.6875 to Base 2:
 Join the results together with the
radix point:
40
Conversion Details
 To Convert the Integral Part:
Repeatedly divide the number by the new radix
and save the remainders. The digits for the new
radix are the remainders in reverse order of their
computation.
 To Convert the Fractional Part:
Repeatedly multiply the fraction by the new radix
and save the integer digits that result. The digits
for the new radix are the integer digits in order of
their computation.
 If the new radix is > 10, then convert all integers >
10 to digits A, B, …
41
Additional Issue - Fractional Part
 Note that in this conversion, the fractional part
became 0 as a result of the repeated
multiplications.
 In general, it may take many bits to get this to
happen or it may never happen.
 Example: Convert 0.6510 to N2
• 0.65 = 0.1010011001001 …
• The fractional part begins repeating every 4
steps yielding repeating 1001 forever!
 Solution: Specify number of bits to right of
radix point and round or truncate to this
number.
42
Arithmetic -- addition
• Binary similar to decimal arithmetic
No carries
1 0 1 1 0 0
0 1 1 0 0
1 0 1 1 0
+ 1 0 0 0 1
+ 1 0 1 1 1
1 1 1 0 1
1 0 1 1 0 1
Carries
1+1 is 2 (or 102), which results in a carry
43
Arithmetic -- subtraction
No borrows
0 0 1 1 0
1 0 1 1 0
1 1 1 1 0
- 1 0 0 1 0
- 1 0 0 1 1
0 0 1 0 0
0 1 0 1 1
Borrows
0 - 1 results in a borrow
44
Arithmetic -- multiplication
multiplicand
1 0 1 1
multiplier
X
1 0 1
1 0 1 1
0 0 0 0
1 0 1 1
Successive additions of
multiplicand or zero,
multiplied by 2 (102).
Note that multiplication
by 102 just shifts bits
left.
1 1 0 1 1 1
45
Hexadecimal Arithmetic
• Similar
• If you’re doing by hand, easiest to
convert each set of digits to decimal
and back
46
DECIMAL CODES - Binary Codes for Decimal
Digits
 There are over 8,000 ways that you can chose 10 from the
16 binary numbers of 4 bits. A few are useful:
Decimal
8,4,2,1
0
1
2
3
4
5
6
7
8
9
0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
Excess3 8,4,-2,-1
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
0000
0111
0110
0101
0100
1011
1010
1001
1000
1111
Gray
0000
0100
0101
0111
0110
0010
0011
0001
1001
1000
Chapter 1
BCD
• Binary Coded Decimal
• Decimal digits stored in binary
♦ Four bits/digit
♦ Like hex, except stops at 9
♦ Example
931 is coded as 1001 0011 0001
48
Warning: Conversion or Coding?
 Do NOT mix up conversion of a decimal
number to a binary number with coding
a decimal number with a BINARY
CODE.
 1310 = 11012 (This is conversion)
 13  0001|0011 (This is coding)
Chapter 1
Other Codes Exist
• Non positional
• Example: 3-bit Gray Code
♦ 000,001,011,010,110,111,101,100
• Binary Gray code for octal digits
♦ Only one bit changes at a time
♦ Actually there’s a family of Gray codes
50
GRAY CODE – Decimal
Decimal
8,4,2,1
Gray
0
1
2
3
4
5
6
7
8
9
0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
0000
0100
0101
0111
0110
0010
0011
0001
1001
1000
Chapter 1
51
Character Codes
• From numbers to letters
• ASCII
♦ Stands for American Standard Code for
Information Interchange
♦ Only 7 bits defined
• Unicode
52
ASCII table
53
Even Parity
• Sometimes high-order bit of ASCII
coded to enable detection of errors
• Even parity – set bit to make
number of 1’s even
• Examples
♦ A (100 0001) with even parity is
0100 0001
♦ C (100 0011) with even parity is
1100 0011
54
Odd Parity
• Similar except make the number of
1’s odd
• Examples
A (100 0001) with odd parity is 1100 0001
C (100 0011) with odd parity is 0100 0011
55
Error Detection
• Note that parity detects only simple
errors
♦ One, three, etc. bits
• More complex methods exist
• Some that enable recovery of
original info
♦ Cost is more redundant bits
56