CSI404:Lecture Notes and Log for Topic 1
Readings: Mano 1-1 to 1-5; Mano 2-2 and 2-3.
Lecture 01 (1/22/01)
Two aspects of computer architecture:
-
Instruction Set Architecture: How the bits represent different kinds of
data or instructions.
Data representation is covered by Mano's chapter 3, and is taught
in Albany's Assembly Language course.
Instructions are also taught in Assembly Language. Albany uses
MIPS. You will be doing the machine and assembly language for Mano's
basic computer which is covered in Mano's chapter 6.
-
How computer hardware is organized and built to do the operations specified
by its instruction set architecture.
-
Computer Organization: "High level " components: what they do and how they
are connected together. Examples of these components are memories,
arithmetic/logic units, control units, caches, etc.
-
Computer Design: Implementing high level components using low level digital
components called gates. The word gate is used because
Why are late 20th to early 21st century computers digital and use binary?
-
Live class participatory demonstration of how a "yes" or "no" message can
be propagated without error from the professor to all the students in a
full lecture room. How the same thing can be done at a noisy party,
so long as each person shouts the message he or she hears louder
than he or she heard it.
-
The digital circuit components (parts) in the computer perform logic
restoration: The electrical signals they output are amplified
so that other components can unambiguously interpret the signal as either
a "yes" (also known as "on", "true", "high", or 1) or a "no" (also known
as "off", "false", "low", or 0) . (The same applies to the optical
or magnetic signals that are the also used in today's digital computer,
communication and information storage technologies.)
-
Generally (for a given level of technology), faster digital processing
requires more power (energy used per unit time) than slower processing.
-
Carver Mead (an electrical engineering research scientist who wrote a book
on chip design for software oriented computer scientists and did research
on mixed analog and digital electronic systems) said brains do digital
processing for some things for accuracy and analog processing when speed
is more important than accuracy.
-
The other critical function of a digital component is to generate an output
signal from the input signals according to a rule.
Introduction to a combinational circuit and its application.
-
Application: Addition of unsigned integers represented in binary.
Review of binary addition: place value (significance of each place),
numeric interpretation is the sum of the contributions from each place,
each contribution is 2^k, where k is the index of the bit, adding by using
carries.
-
The AND gate
Symbol used to express it.
Explanation of the AND function.
Application to generate the carry from adding 2 bits.
-
The OR gate
Symbol used to express it.
OR function defined by a truth table.
How to systematically write all the rows of a truth table:
-
First write all the rows for which the value of first input bit 0.
-
Finish by writing all the rows for which the value of the first input bit
is 1.
-
That way, you will be sure to get all 2^n combinations, where n is the
number of input bits.
Lecture 02 (1/24/01)
Numerals (Roman, Decimal, binary) compared to numbers. Numbers
are abstract mathematical entities. Numerals express numbers.
Numerals belong to diverse systems that vary with culture and technology:
compare Roman to modern, compare stone carving, paper writing, bead counting
on an abacus, computer RAM chips, computer magnetic disks, etc.
Definitions and notations for AND, OR, NOT and buffer (amplifiers which
are used solely for logic restoration on wires driving many inputs).
-
Truth tables for AND, OR, and NOT.
-
Circuit diagram notation: Nodes, crossings, wires.
Verifying a few of the simulated components on Alan Mill's MMLogic software:
-
Demonstration of drawing a circuit.
-
Demonstration of the toggle switch, light emitting diode (LED), OR gate
and logic probe.
-
Verification of the OR gate against its truth table specification.
-
Link to .lgi file from the
lecture (ORandSwitchDemo.lgi)
(You may have to SHIFT-click to download this as a file).
Tracing the operation of a circuit that realizes the half-adder function
using 3 AND gates, 1 OR gate and 2 NOT gates.
Adders
-
The half adder has 2 input bits and 2 output bits. When the
inputs represent 2 numbers in binary, each in the 0-1 range, the outputs
represents their SUM in binary.
-
The full adder has 3 input bits and 2 output bits. When the
inputs represent 3 numbers in binary, each in the 0-1 range, the outputs
represent their SUM in binary. Notice that the sum can be 0, 1, 2
or 3 and these four numbers are precisely the four numbers that can be
represented in unsigned binary with two bits.
-
See Mano p. 21 for the truth table for the full adder.
Lecture 03 (1/26/01)
-
Announcements:Tutorial/review/TA office hours Wednesday morning 8:30-10:00
AM, LC-6
Homeworks 2 and later will be due 10:13AM Friday mornings.
USENET
newsgroup/discussion formum(server cscnews.albany.edu, sunya.class.csi404)
-
Outline:
-
Introduction to Boolean (after Geog Boole) algebra: Related to named signals
in our circuit for the half-adder.
-
Half-adder function expressed in Boolean algebra and realized by a better
(smaller) circuit.
-
Operators (NOT, AND, OR) and their precedences.
-
Truth table, English description and Boolean algebra formulas for the full-adder
functions.
-
Remark on the universality of {AND,NOT}, {OR,NOT}, {NAND}, {NOR}, {AND,OR,NOT}.
-
Full-adder sum bit S(X,Y,Z)=XY'Z'+X'YZ+X'Y'Z+XYZ. synthesized by an OR
of AND logic array.
-
Combinational logic (Mano 1-5, Figure 1-15)
-
Block diagram: Names the inputs and outputs.
-
Combinational circuit: Output values depend only on input values
now (after generally very short delays), not on past history.
-
Analysis: Given circuit diagram or other expression for a circuit, figure
out its truth table.
-
Design: Given some statement of the problem, draw a circuit diagram or
other expression for a circuit that solves the problem.
-
Languages to specify, manipulate, analyze and synthesize (means
"create a circuit or formula whose function is specified") combinational
logic circuits:
-
Carefully written natural language (English, French, Chinese, etc.) description.
-
For example, the full adder is the function with 3 single bit inputs whose
2 outputs represent the numeric sum of the 3 input values with both the
inputs and the output using unsigned binary representation.
-
Logic circuit diagrams (Lectures 1 and 2)
-
Truth tables (Lectures 1 and 2)
-
Each truth table row is for one combination of input values.
-
Each truth table output column specifies a value (0 or 1) for each row.
-
For n input variables, there are 2n rows.
-
Boolean algebra (Today, Mano 1-3)
-
Karnaugh maps (Lecture 04, Mano 1-4)
-
Binary Decision Diagrams (BDD).
-
Hardware specification languages.
-
Mano's boolean algebra notation: + for OR, . (dot) or "" (null string)
for AND, ' (prime) for NOT.
-
Truth table, logic diagram, boolean algebra expression compared (Mano
figure 1-3).
-
Two logic diagrams or two boolean algebra formulas are equivalent means
they have the same truth table. Another example: Mano's figure 1-6.
-
The truth table tabulates the function given by the diagram or formula.
A boolean function (from CSI210) is a relation R with the special property
that for every combination of inputs there is one and only one tuple in
R with that combination.
-
Many different logic diagrams and formulas can have the SAME function,
that is, the same truth table.
-
Illustration of an OR of AND logic array for synthesizing S(X,Y,Z)=XY'Z'+X'YZ+X'Y'Z+XYZ.
Lecture 04 (1/29/00)
-
Completeness of {AND,OR,NOT}
-
Sum of products form.
-
Every boolean function, that is every truth table, can be synthesized by
a formula that is an OR of one or more AND formulas where each AND formula
is the AND of one or more variables or NOT of variables. This form
is called "sum of products".A variable or the NOT of a variable is called
a literal.
-
A product of literals in which ALL the n variables appear:
-
Is true for exactly ONE of the 2n combinations
of variable values.
-
Example: Let n = 4. WX'Y'Z is 1 exactly when W=1, X=0, Y=0, and Z=1.
For all the other 15 combinations, WX'Y'Z=0.
-
Is called a minterm.
-
It corresponds to, and can be identified with, one truth table row.
-
You can synthesize any boolean function you want by OR-ing together all
the minterms that correspond to truth table rows for which the output value
is 1.
If a lot of rows have output value 1, a lot of OR gates will be used.
-
Smaller complete sets: 2-input ANDs and ORs only; {OR,NOT}, {NOR}.
-
Associative law for AND discussed (OR is associative too, and both are
commutative. It therefore doesn't matter in which order operands
to AND are combined nor in what order they are written. Same for
OR.)
-
DeMorgan's laws discussed. Please verify them yourself by truth table
and by thinking!
-
Logic array to realize arbitrary logic functions. (illustration with C
output of the full adder)
-
Sometimes a term can be omitted: C=XY+XZ+YZ+XYZ=XY+XZ+XY, since whenever
XYZ=1, at least one of the other terms equal 1.
-
Programmable (pre-layed out) logic arrays. Role of diodes (A
diode conducts electricity in only one direction.)
-
Building larger circuits from smaller: n-bit full adder. How it implements
elementary addition of binary numerals.
-
What's a combinational circuit
Comments on how outputs depend on inputs: time delay is assumed to
be negligable
Block diagrams, inside and outside views compared, the subsystem
boundary.
Lecture 05 (1/31/01)
-
Implementation and functional specification contrasted.
-
Handling realistic combinational design problems:
-
Higher level of abstactions: Combine solutions to
simpler problems. Produce hierarchical designs. Handle great
complexity.
-
Lower level of abstraction: Logic minimization.
Find gate arrangement or array programming to
-
minimize count of gates or connections
Goal: reduce chip "real estate" costs.
-
minimize maximum path length
Goal: increase chip speed.
-
Another hierarchical design example: MUX of problem
4 of Homework 1.
-
What's a MUX? (inputs, outputs, functional specification)
-
Example application.
-
Solution requirements:
-
Name the inputs and output(s) of your solution.
-
Name the parts your solution uses; label their inputs
and outputs.
-
Draw interconnection wires and "glue gates"
-
Analysis, Design, Verify: what they mean.
-
Logic minimization problems: Find a circuit that minimizes (say) the number
of gates among all equivalent circuits.
-
Dually, every boolean function can be synthesized by a product of sums:
AND together all ORs of literals with all variables, for each truth table
row with output value 0.
-
Karnaugh map method for logic minimization of sum of products type formulas
or circuits (really the same thing). It's for single bit boolean
functions with up to 4 input variables.
-
Draw a SPECIALLY LAID OUT rectangular array. Each square corresponds
to one minterm. Note that each minterm corresponds to one combination of
input values. The layout is created so horizontally or vertically adjacent
squares correspond to input value combinations that are different
in ONLY one bit. Furthermore, each distinct pair of squares at the
ends of each row, or at the ends of each column, are considered adjacent.
Make sure the rows and columns are clearly labelled so you can figure out
what combinations of input values corresponds to each square.
-
Plot the given truth table on this "K-map". Write 1's in the squares
for which the output should be 1, 0's in the squares where the output
should be 0. If there are any situations where the output doesn't
matter, write a * (wildcard character). We'll see later how these
"don't care" cases can lead to smaller solution circuits than if you made
an arbitrary choice of 0 or 1.
-
A group is a rectangular set of squares that corresponds to
the condition that some AND of literals is true. An AND expression
of one or more literals is called a term .The number of squares
in each group is a power of 2: 1=20, 2=21, 4=22,
8=23, 16=24
-
Let n be the number of variables. The number of variables
in the a term corresponding to 2k squares is n-k.
-
MAIN OPERATION of the K-map method. This operation is easy to do
quickly after you practice it on a few problems. Find a set of groups
that
-
Covers all the 1s.
-
Does not cover any 0s.
-
Might or might not cover *s.
-
Uses as few groups as possible. (This minimizes the NUMBER
of AND gates.)
-
Uses for each group one that is large as possible. (This minimizes
the number of INPUTS to each AND gate.) Since a larger group certainly
covers all the squares that are contained in every smaller group within
it, this rule to use groups that are as large as possible does not defeat
the previous rule to use as few groups as possible.
-
It's OK to use groups that overlap, and overlapping groups must sometimes
be chosen to conform to the above two rules.
-
Write out the formula or ciruit diagram from your choice of groups.
-
Each group corresponds to one AND gate. The outputs of the AND gates
all go into one OR gate (which can be omitted if there's only one AND gate.
Similarly, any AND gate with only one input can be eliminated.
-
Each AND gate is driven by an input or an inverter driven by an input.
-
Each group corresponds to a formula term, which is an AND of literals.
The formula is the OR of the terms corresponding to the groups.
-
K-map square numbering: Sometimes it's convenient to refer to K-map
squares by number. Given a particular ordering of the variables
so the sequence of their bit values represents a number using unsigned
binary, the number of the K-map square is the number represented in by
the bit combination corresponding to that K-map square. See Mano's
text for examples and the notation of a boolean function by the sequence
of numbers corresponding to the K-map squares for which the function value
is 1. Observe that this K-map square numbering does not always
use consecutive numbers for consecutive squares!
-
Implicants and prime implicants: Given the boolean function F(X,Y,Z,..)
-
An implicant is a term I(X,Y,Z,...) such that if
the inplicant is 1 (true) then the function value is 1 (true).
The word "implicant" means "something that implies".
For example, each square on the K-map containing a 1 is corresponds to
a term that is an implicant.
-
The implicants of F correspond to the K-map groups that cover only squares
filled with 1. The bigger the group, the smaller is the number
of literals ANDed together in the corresponding term. Thus if a group can
be enlarged to a group that also covers only 1s, the term corresponding
to the smaller group can be factored into another implicant
ANDed with other literals. The implicants that correspond to groups
that cover only squares filled with 1 and cannot be enlarged to a larger
group that without the larger group covering some square with a 0 are therefore
terms that cannot be factored into an implicant with fewer literals ANDed
with other literals. Such an implicant, which corresponds to the
kind of group we should choose in the K-map method, is called a prime
implicant by analogy with prime integers, which cannot be factored.
-
Thus, the K-map method is to find a minimal set of prime implicants for
F by manual placement of groups on the diagram.
-
The K-map method is practical for realizing optimal circuits for up to
4 inputs, but cannot be extended to more. The are other methods that
are programmed into software that digital design engineers use that is
practical for larger numbers of variables.
-
Basic identities (Mano's table 1-1).
-
Many are analogous to identies true in algebra over numbers, with:
-
boolean OR analogous to numeric addition (+)
-
boolean AND analogous to numeric multiplication (dot or "")
-
boolean 1 (true) analogous to number 1 (one)
-
boolean 0 (false) analogous to number 0 (zero).
-
A few are not analogous: x+(yz) = (x+y)(x+z) is not an identity of numbers
but is an identity of logic values.
-
You can prove them by figuring out 2 truth tables and verifying they are
equal.
-
Identities can be used to simplify digital circuits.
Copyright (C) S.Chaiken, 2001. All rights reserved.
$Id: Topic01.html,v 1.4 2001/01/29 18:35:35 sdc Exp $