Transcript CS 110 – Lecture 2

CS 300 – Lecture 3
Intro to Computer Architecture
/ Assembly Language
Digital Design
Text
The chapter we'll work out of is available in
my pickup folder – hardware.pdf.
How Logic Gates Work
A gate has “inputs” and “outputs” (wires). The
outputs are determined by the inputs.
For a relay: input is voltage on the coil, outputs are
connections between terminals
Transistors are similar except a lot smaller
Key characteristics:
• Delay: how soon the output has the “right”
answer
• Power dissipation: how much heat is generated
• Size: how much silicon is needed on the chip
Building Logic Gates
Many different sorts of
logic gates are used in
computing
A Pentium has about 50,000,000 transistors
Combinatorial Circuits
We'll start with "Combinatorial" circuits –
these are ordinary functions over booleans.
This is the "expression" part of the hardware
programming language.
A combinatorial circuit is a function from a
set of boolean inputs to a set of boolean
outputs.
Truth Tables
We can specify the behavior of a combinatorial
circuit using a "Truth Table" that enumerates the
output for all possible inputs (note that this isn't
how we usually specify functions – there is no way
to enumerate all integers or reals, for example)
A truth table for a circuit with N inputs and M
outputs has 2N rows and M output columns.
Two circuits compute the same function if they
have the same truth table (but these circuits are
not necessary equivalent – why?)
Adding Two Numbers
Truth table for 2-bit addition:
x y Sum Carry
0 0
0
0
0 1
1
0
1 0
1
0
1 1
0
1
Inputs
Outputs
Gates and Boolean Expressions
We have two ways of expressing a
combinatorial circuit:
* As boolean expressions that define each
output in terms of the inputs (and maybe a
temp or two)
* As a circuit diagram, expressed in gates
and wires.
These are equivalent – you can go back and
forth between these representations.
Boolean Expressions
Variables are either true or false
X ·Y = the 'and' of X , Y (also just XY)
X+Y = the 'or' of X a, Y
X' = the inverse of X (also overbar)
This is no different than a programming
language expression over booleans
involving and, or, and not.
Boolean Algebra
X(Y+Z) = XY + XZ
Distribution
X+X' = 1 (True)
Inverse law
X+(Y+Z) = (X+Y)+Z Associativity
XY = YZ, X+Y = Y+X Commutivity
X+X = X, XX = X
Absorption
X+0 = X, X+1 = 1, X0 = 0, X1 = X Removal of constants
X+Y = (X'Y')'
DeMorgans Law
And many others!
It's very easy to rewrite boolean equations to make them
easier to understand or more efficient when implemented in
hardware.
A Canonical Representation
All boolean equations can be converted to "sum of
products" form. That is, a term in which all of the or
operators are at the top, all ands are below, and all nots are
at the leaves. Repeated application of DeMorgan and
distributivity put any term in this form.
There is a direct link between truth tables and SOP form.
Note that:
* You can remove all constants (unless the expression
collapses completely)
* You can remove repeated terms
* Ordering within a + or * is unimportant
Examples
Convert these to SOP:
X(Y+Z')
(A+B)'
(A+B)'(C+D)'
(A+0)(B+1)
Truth Table
Every line of a truth table corresponds to a
product of the inputs – if the input is 1, use
the input variable. If 0, use the inverse of
the variable. The result is a sum of all
products that correspond to a "1".
Example: Turn the adder into SOP
equations.
Circuit Diagrams
We can express equations graphically as
lines (wires) and gate symbols.
And: AB
Or: A+B
Not: A'
Why Wires?
The visual depiction of boolean function directly
corresponds to the physical circuit. From the
diagram, we can easily see:
* Number of gates
* Overall delay (depth)
* Fan out (number of inputs connected to an
output)
* Layout (sort of!)
We'll generally use diagrams instead of equations.
Exercises
Convert the boolean equations from the
previous exercise into diagrams
Create a circuit for the adder (actually a
"Half Adder")
Essential Skills
* Rewriting of boolean equations
* Creating SOP equations
* Conversion between truth tables,
equations, and circuits