Transcript and x +

2IC30-2IC05: Computer systems
Introduction
Rob Hoogerwoord
([email protected])
2IC05: Schedule
4 hours of Lectures per week:
•
monday 8:45 – 10:30 in AUD5
• wednesday 8:45 – 10:30 in PT 1.05
• lectures start at 8:45 sharp: be on time!
4 hours Practicum per week; location: PT 9.05
- Group Tuesday: Tuesday, 5th until 8th hour;
- Group Thursday: Thursday, 5th until 8th hour;
- Group Wednesday/Friday: Wednesday & Friday, 3rd
and 4th hour (on both days).
2IC30-2IC05: Practicum Registration
Registration is Mandatory:
• NOT registered? => NO access!!!
• WHY are we so strict?
(1) The capacity of the Practicum room is limited;
(2) To streamline the administration of your work.
2IC30-2IC05: Practicum Tutors
Practicum Tutors:
• Tuesday: Rob Hoogerwoord, [email protected]
• Thursday: Gerard Zwaan, [email protected]
• Wednesday/Friday: Sebastiaan de Hoogh,
[email protected]
2IC30: Assessment 5 ECTS
Composition of the final grade:
• your work in each Practicum session is graded:
‘‘completed’’ , or: ‘‘not completed’’;
• each ‘‘completed’’ result: 5 % , with a maximum of
30 % in total --the best 6 results out of 7 are used--;
• grade for the final examination: 70 %
2IC05: Assessment 6 ECTS
Composition of the final grade:
• your work in each Practicum session is graded:
‘‘completed’’ , or: ‘‘not completed’’;
• each ‘‘completed’’ result: 5 % , with a maximum of
30 % in total --the best 6 results out of 7 are used--;
• homework assigment: 15 %, for the extra ECTS;
• grade for the final examination: 55 %
2IC30-2IC05: Theory and practice
Lectures: theory will be explained. This can also
be found (mostly) in the book.
Practicum: you will create designs, implement
and test them, both in hardware and software.
NOTE: Being able to complete the exercises does
not guarantee you will also be able to pass the
exam. The exam will test both theory and
practical knowledge.
2IC30-2IC05: Self Study
Self Study --homework-- is REQUIRED to prepare for the
Practicum sessions. This entails:
• studying the sheets of the relevant lectures and parts of the
book;
• working out those parts of the exercises that can be worked
out in advance;
• advantage: you will learn more and have more fun;
• advantage: the better prepared you are the quicker you finish
a Practicum session (and the earlier you can leave… );
• advantage: better preparation for the final examination.
2IC30-2IC05: More information
Course homepage:
Visit the OASE space for 2IC30 regularly! All
announcements and material will be placed there.
No E-mails will be sent, except in urgent cases.
Course Material:
 Sheets (after the Lectures)
 Study guide
 Handouts for the Practicum
 Software
(please download & install before the exercise session)
Book:
A.S. Tanenbaum
“Structured Computer Architecture"
4th or 5th edition (Dutch or English)
Questions?
prehistory (±1835) of electrical data
processing: the Morse telegraph
Morse’s telegraph sending key (±1835)
Morse’s telegraph receiver (±1835)
The Relay (±1835):
an electrically operated switch
Digital versus Analogue
t
Digital:
 discrete in value and time
 Complex, exact processing is
cheap
 Storing information is simple
and cheap
 Converting and presenting in
different versions is simple
 Very reliable and immune
against corruption and noise
 Simple development
(faster and cheaper)
t
Analogue:
 continuous in value and time
Digital signals
Binary is an extreme form of digital with just two
values:
on
off
true
false
1
0
If it is dark
and something moves
then turn on the light
Light sensor
Movement detector
(true/false)
(true/false)
(true/false)
System
Systeem
x
X
light
Switching circuits
a
a
a
b
a
negated switch:
NOT
b
serial:
Q
Q
Q
i=0: switch is not pressed
i=1: switch is pressed
o=0: light is off
o=1: light is on
Q
AND
parallel: OR
Switching circuits
Digital switches:
a
Q
Q
a
NOT
Switching circuits
a
b
Q
a
Q
b
AND
OR
Logical gates
These standard circuits are called logical gates:
a
Q
NOT
a
b
Q
AND
a
Q
b
OR
a Q
0 1
1 0
a
0
0
1
1
b
0
1
0
1
Q
0
0
0
1
a
0
0
1
1
b
0
1
0
1
Q
0
1
1
1
Q = a’
Q = a•b
Q = a+b
Truth tables!
Gates in practice
Gates are implemented by analogue circuits:
 As long as the output voltage
fits within the limits of the
required input voltage, this is no
V
problem.
 The margins ensure that small
v out
signal error and loss of voltage

are corrected automatically by
each gate
 Hence, errors due to noise and
cumulative imperfections to not
occur!
0
low input
voltage
high input
voltage
 vin
V
Larger circuits
a
b
Q
c
a
b
c
Q
Design techniques are needed!
Questions?
Combinatorial circuits
A circuit is combinatorial if:
- Every component is itself a combinatorial circuit
- Each connection starts at a primary input or exactly one
output
- The circuit does not contain any cycles
(an input of a component never depends directly or
indirectly on an output of this component)
NOTE: this is a recursive definition!
(circuits may be hierarchical)
Designing combinatorial
circuits
truth table
A
0
0
1
1
B
0
1
0
1
S
0
1
1
0
C
0
0
0
1
testing
implementing
with gates
Boolean
expressions
A
S
B
S = AB + AB
C = AB
C
design trajectory
Truth tables
We start designing circuits separately for each
output
A truth table has one column for each primary
input
The possible input combinations double with each
primary input. Hence, for n inputs you get 2n
lines in your truth table
The output column denotes signals. Therefore, n
n)
(2
inputs can create 2 different functions
Can probably be done automatically!
Even for 4 inputs, this yields 65536 functions
Truth tables
Truth table for 64 inputs
(e.g. adding two 32 bit numbers)
Computer processes 1 billion lines / second (about
doable nowadays)
Hence, processing the truth table takes over 500
years !!!
regularity (repeating patterns), abstraction and
hierachical principles are needed to control this
complexity
George Boole en Claude Shannon
1847: G. Boole,
"Mathematical analysis of logic"
1854: G. Boole,
"An investigation in
the laws of thought"
1854: A. De Morgan,
"Formal logic"
1904: E.V. Huntington,
"Sets of independent postulates
for the algebra of logic"
1910: P. Ehrenfest,
"Review of L.Couturat's
L'algèbre de la logique"
1938: C.E. Shannon,
"A symbolic analysis of
relay and switching circuits"
George Boole
(1815-1864)
Claude E.
Shannon
Boolean algebra
A set B with two operations + and • is a Boole algebra if
and only if:
- It contains at least two different elements.
- For each x and y from B operations x•y and x+y yield an
element from B.
- There exists a 1 in B such that 1•x equals x•1 equals x.
- There exists a 0 in B such that 0+x equals x+0 equals x.
- + and • are commutative (i.e. x•y=y•x and x+y=y+x)
- Every x has a complement x' such that x+x'=1 and x•x'=0.
- • and + distribute over one another:
x • (y + z) = (x • y) + (x • z) and
x + (y • z) = (x + y) • (x + z).
NOTE: There are several ways to accomplish this!
Switching algebra
If B has exactly two elements, such an algebra is
called a switching algebra.
B = { 0,1 } , with 0’ = 1and 1’ = 0 .
x+y = 1 if and only if x = 1 or y = 1 (or both).
x•y = 1 if and only if x = 1 and y = 1 .
Operations ’ , • and + correspond to the gates
NOT, AND and OR respectively.
Rules for switching algebra (1)
x+x=x
Idempotence
x•x=x
x+1=1
Zero elements
x•0=0
x+0=x
Identity elements
x•1=x
( x’ )’ = x
(x + y) + z = x + (y + z)
Associativity
(x • y) • z = x • (y • z)
(x + y)’ = (x’) • (y’)
De Morgan
(x • y)’ = (x’) + (y’)
Rules for switching algebra (2)
x+y = y+x
Communitativity
x•y = y•x
x + (x • y) = x
Absorption
x • (x + y) = x
x + (x’ • y) = x + y
Complement Absorption
x • (x’ + y) = x • y
Duality principle
Once you prove a theorem in Boole algebra, you
have also proved the theorem where + and • and 0
and 1 are exchanged
x • 0 = (x • 0) + 0 =
(x • 0) + (x • x') =
(x • x') + (x • 0) = x • (x'+0) = x • x' = 0
and hence x + 1 = 1
Another example: absorption
x • (x + y) = (x + 0) • (x + y) = x + (0 • y) = x + 0 = x
and hence x + (x • y) = x
Proof using truth tables
Proof of de Morgan with a truth table:
x
0
0
1
1
y
0
1
0
1
x+y
0
1
1
1
(x+y)'
1
0
0
0
x'
1
1
0
0
y'
1
0
1
0
x'y'
1
0
0
0
=
Duality provides the other rule of de Morgan!
Questions?
production of chips:
What if a chip is defective?
Since during production a dustpiece may fall onto
the wafer, not all chips work. The bigger the chip,
the smaller the chance of a working chip and
hence, it will be more expensive.
Some chips works slower than others, because the
layers do not match as well. These will just be
sold as ‘slower’ chips.
Sometimes, things get even worse: for example
Intel’s 486SX, 486DX and 487 processors.