Transcript Document

Chapter 1
The Big Picture
QUIZ
Explain the abstractions we normally apply when
using the following systems:

DVD player

Registering for classes on DuckTrax

Walking
In each case, explain what is the internal view
and what is the abstract view.
2
5
QUIZ
Explain the abstraction applied in browsing the
WWW:
• What is the internal view?
• What is the abstract view?
3
QUIZ
Connect each generation of computer hardware
with its defining technology:
1st Gen.
2nd Gen.
3rd Gen.
4th Gen.
5th Gen.
ICs
Multi-core processors
LSI, VLSI
Vacuum tubes
Transistors
4
Practice Flashcards on the text website
5
Chapter 2
Binary Values and Number
Systems
Converting Binary to Decimal
What is the decimal equivalent of the binary
number 1101110?
11011102 = ???10
7
13
Converting Binary to Decimal
What is the decimal equivalent of the binary
number 1101110?
1 x 26 = 1 x 64 = 64
+ 1 x 25 = 1 x 32 = 32
+ 0 x 24 = 0 x 16 = 0
+ 1 x 23 = 1 x 8 = 8
+ 1 x 22 = 1 x 4 = 4
+ 1 x 21 = 1 x 2 = 2
+ 0 x 2º = 0 x 1 = 0
= 110 in base 10
8
13
QUIZ:
100110102 = ???10
9
Converting Hexadecimal to Decimal
What is the decimal equivalent of the
hexadecimal number DEF?
D x 162 = 13 x 256 = 3328
+ E x 161 = 14 x 16 = 224
+ F x 16º = 15 x 1 = 15
= 3567 in base 10
10
QUIZ:
2AF16 = ???10
11
Converting Octal to Decimal
What is the decimal equivalent of the octal
number 642?
6428 = ???10
12
11
Converting Octal to Decimal
What is the decimal equivalent of the octal
number 642?
6 x 82 = 6 x 64 = 384
+ 4 x 81 = 4 x 8 = 32
+ 2 x 8º = 2 x 1 = 2
= 418 in base 10
13
11
QUIZ: Convert to decimal
1101 00112 = ???10
AB716
= ???10
5138
= ???10
6928
= ???10
14
Addition QUIZ
1010110
+1 0 0 0 0 1 1
Carry values
go here
Check in base ten!
15
14
Subtraction QUIZ
Borrow values
1011000
- 110111
Check in base ten!
16
15
Repeated division QUIZ
Convert 4210 to binary
42  2 =
4210 =
rem.
2
17
19
Converting Binary to Octal
• Mark groups of three (from right)
• Convert each group
10101011
10 101 011
2 5 3
10101011 is 253 in base 8
18
17
Converting Binary to Hexadecimal
• Mark groups of four (from right)
• Convert each group
10101011
1010 1011
A
B
10101011 is AB in base 16
19
18
Counting
Count from 5 to 17 in binary.
Place the numbers in a table.
20
Converting Octal to Hexadecimal
Convert octal 253 into hex.
21
18
Converting Octal to Hexadecimal
Convert octal 253 into hex.
10 101 011
2 5 3
253 in base 8
1010 1011
A
B
= AB in base 16
22
18
Quiz on Ch.2
Convert 201023 to decimal
Chapter 03
Data Representation
Quiz
A video file is originally 3.5 GB long.
We compress it to 490 MB. What is the
compression ratio?
25
Quiz
A digital thermometer has a scale from 50 to
100 degrees (F). The temperature is represented
on 7 bits. What is the smallest temperature
difference that it can measure?
26
QUIZ
How many bits are needed to represent all the
courses you’re planning to take in college?
27
QUIZ
Given the following representations, find in each
case what actual number is being represented:
51
52
96
47
28
EXTRA-CREDIT QUIZ
If the representation is 76, what actual number
is being represented?
29
QUIZ
What is the representation for each of these
actual numbers?
-48
-40
-30
-5
30
Let’s use ten’s complement!
To perform addition, add the numbers and discard any
carry
Now you try it
48
-1
47
(signed-magnitude)
How does it work in
the new scheme?
31
Adding two negative numbers
Try these:
4 - 4 -4
- 3 +3 + -3
32
QUIZ
What is the 8-bit two’s complement
representation of these numbers?
-13
40
33
QUIZ
Perform the following operation in 8-bit two’s
complement:
40 – 13
34
Trick QUIZ
What decimal number does this binary number
represent?
1001 1110
35
Converting fractions from binary to
decimal
Easy! Just multiply with the powers of 2, as we
did for unsigned binary. Only difference is that
now the powers are negative.
Example: .10012 = 0.
10
36
QUIZ
Convert:
.10112 = 0.
10
37
Converting fractions from decimal
to binary
Remember the repeated division algorithm?
We apply it for the integer part of the number.
To covert the fractional part, we use the
repeated multiplication algorithm!
Example: 0.43510 = 0.
2
38
QUIZ
Convert:
0.310 = 0.
2
39
QUIZ
Finite decimal fractions may have infinite
binary representation!
0.310 = 0. 0100110011
2
Stop after 8 bits!
40
QUIZ
Convert to floating point and to scientific notation:
123.332 =
-0.0034 =
0.0
=
41
QUIZ
Encode “Hello, world!” in ASCII
Decode 67 83 32 49 49 48 from ASCII
42
Huffman decoding QUIZ
Decode:
1011111001010
43
QUIZ
Explain the similarities and differences
between 00FF00 and 008800
44
Extra-credit question
TrueColor
A 24-bit color depth: eight bits used for each number in
an RGB value
How many different colors can be represented
in TrueColor?
Please show your work.
45
QUIZ
Are these HiColor
or TrueColor?
46
Extra-credit question
How many bits are
needed to represent
this palette?
Please show your
work.
47
3.6 Representing Video
The problem: huge amount of data!
Example: In HDTV, the Frame size is defined as the
number of horizontal pixels × number of vertical pixels:
1280 × 720
1920 × 1080
Calculate:
1] Data rate (bits per second) for 25 fps
2] Size (bytes) of 2-hour movie
48
All hail the HARDWARE!
Chapter 4
Gates and Circuits (with
some transistors thrown in for
good measure)
QUIZ: recognize the gate!
50
QUIZ: elementary properties
A AND 0 = ?
A AND 1 = ?
Etc.
51
Quiz
What are the 3 ways we use to describe gates
and circuits?
Use the 3 ways to describe the NAND gate
Hint: Describe AND first!
52
QUIZ
Draw the gate symbols for:
4-input OR
5-input NAND
3-input NOR
4-input XOR
Figure 4.7 Various representations of a three-input AND gate
53
QUIZ
Draw the gate symbols for:
4-input OR
5-input NAND
3-input NOR
4-input XOR
How many lines does each of the truth tables have?
Figure 4.7 Various representations of a three-input AND gate
54
QUIZ
Draw the gate symbols for:
4-input OR
5-input NAND
3-input NOR
4-input XOR
How many lines does each of the truth tables have?
Describe in your own words each of the truth tables.
Figure 4.7 Various representations of a three-input AND gate
55
QUIZ
A computer represents numbers in 8-bit two’s complement.
Design a circuit that will detect the number zero (the output of
the circuit becomes 1 if and only if all 8 bits are 0):
0
0
0
0
0
0
0
0
Figure 4.7 Various representations of a three-input AND gate
56
Extra-credit QUIZ
A computer represents numbers in 8-bit two’s complement.
Design a circuit that will detect the number -128
Hint: -128 is 1000 0000 in two’s comp.
1
0
0
0
0
0
0
0
Figure 4.7 Various representations of a three-input AND gate
57
From gates to circuits
Find the logic diagram of the circuit described by the following
truth table:
1
0
Hint: The table is similar to which of the fundamental gates presented last
time?
58
SOLUTION
Having only one 0 in the output column, the circuit most resembles the
OR gate!
It is different from the OR gate only in this respect: …
Write the Boolean expression:
Draw the diagram:
59
QUIZ
The AND gate is obtained as a NAND followed by an
inverter. Draw its transistor diagram!
60
QUIZ
Draw its switch diagram.
Show the states of all switches for V1 = 0 and V2 = 1.
61
DeMorgan’s law QUIZ
Apply DeMorgan’s Law directly on the gate
diagrams below to obtain equivalent circuits:
62
QUIZ
The XOR operation can be implemented
with AND, OR and NOT gates:
=A’B+AB’
How many transistors are
required for the XOR gate?
63
QUIZ
Connect the MUX input to implement a prime number
detector (i.e. the output F is 1 iff S2S1S0 are the binary
code of a prime number)
64
S – R latch “forbidden” inputs
What happens if both S and R
are activated (made 0) at
the same time?
65
Use a MUXes as “lookup
tables” to implement the
1-bit adder
66
Show how a MUX with only 4 data inputs works
Assume S1 = 0, S0 = 1. Draw the equivalent circuit in this
case and explain the value of the output q.
67
Extra-credit
How many transistors are needed to build this
MUX?
68