From Found. of C.S., Aho and Ullman Ch. 13 (Reserve) and On Line.
Gates (primitive circuits for logic operations)
Each one does a Boolean function:
AND, OR, NOT, NOT-AND (NAND), NOT-OR (NOR).
Number of Boolean Functions on
A B AND NAND OR NOR
0 0 0 1 0 1
0 1 0 1 1 0
1 0 0 1 1 0
1 1 1 0 1 0
In the literature we write
e.g.:
Build other functions out of gates:
Combinatorial (gate's output cannot reach its input -- no cycles in gate-connection graph.)
Opposite is Sequential, which correspond directly (in a formal, provable sense) to deterministic finite automata. The circuit's output is 1 for an input if and only if automaton accepts corresponding input.
E.g. of combinatorial circuit to compute
Given Logic expression: using Structural Induction (very FOCSy!): Circuit will be a tree (as expected). Consider the expression as a tree (say fully parenthesized).
Basis: if expression tree is a single node, the expression
can only be an input, say
Induction Otherwise the expression has a logical operator
Our inductive hypothesis applies to the subexpressions (subtrees), so
there is a circuit
Note this is a super-literal approach to circuit design that doesn't notice shared subexpressions or other simplifying transformations.
Know circuit must be a tree, so we can pick a topological order of its
nodes
(gates) such that if the output of the
Two of many Topological Orders: A B C D E, C B D A E
Induction again, this time on variable
Basis: at
Induction: for
Then expression for gate
Sum of Products Expressions (Disjunctive normal form) From truth-table to minterms, sum (OR) of which is what we want.
One-bit adder TT
x y c d z d minterms (1 if each
var matches row values)
0 0 0 0 0
0 0 1 0 1
0 1 0 0 1
0 1 1 1 0 x'yc
1 0 0 0 1
1 0 1 1 0 xy'c
1 1 0 1 0 xyc'
1 1 1 1 1 xyc
Take sum (OR) of minterms of rows with value 1. This expression
is 1 when inputs match one of rows for which function is 1.
KMs find sum-of-product expressions for Boolean functions, tend to be simple (efficient) solutions.
KM is
Note if we have two minterms differing by one variable's negation, can
forget (delete, pitch) that variable!
An implicant for Boolean function
An implicant covers the points for which it has value 1. So
a logical expression for a Boolean function could be the OR of a set
of implicants that together cover all points where function value is 1.
A prime implicant for
A rectangle corresponding to an implicant can either be a single point, (corresponding to a minterm). OR a row or column (corresponding to pair of points that agree in one variable and disagree in the other). This reduces to the single variable they both share. OR the entire map, in which case the product reduces to the constant 1, and function is TRUE, which has 1's at every point.
The bigger the rectangle, the fewer literals in the product. We generally like fewer literals, which means fewer operators, which means simpler. So we might want to consider only prime implicants to cover a map.
Map the cube onto 2-D in such a way that adjacent columns correspond to assignments of truth values that differ in only one variable. Also columns ``wrap around.'' The carry-out function looks like
Which rectangles can represent implicants? Must be product of literals. In a product, variable appears negated, not negated, or not at all. When it appears (negated or not) it cuts in half the number of points in corresponding implicant So number of points always a power of 2.
Each permissible implicant is collection of points that, for each variable, either includes only points with that variable equal to 0, or includes only points with that variable equal to 1, or does not discriminate on the basis of that variable.
So in 3-D we get 1) any point; 2) any column; 3) any pair of
horizontally adjacent points, including wrap-arounds in cols 1,4;
4) any row; 5) any
Prime implicants are really the point of the Karnaugh Map: they are the shortest way to represent a chunk of the truth table.
Below also a 4-D Karnaugh Map.
Do the 2-variable trick on rows as well. Use same row order for
pairs as col. order in 3-D for same reason. Define both row and
col. adjacency with wrap-arounds. NOTE implication: 4 corner points
are a
Rectangles corresp. to products of literals: 1) Any point; 2) Any two
horiz. or vert. adj. points, including wrap-arounds; 3) any row;
4) any column; 5) any 2x2 square including wrap-arounds; 6) any
To get the product of literals that is TRUE
for just the points in an implicant rectangle,
let
Multiple inputs and outputs. Inputs
x y c d z d
0 0 0 0 0
0 0 1 0 1
0 1 0 0 1
0 1 1 1 0 yc
1 0 0 0 1
1 0 1 1 0 xc
1 1 0 1 0 xy ⇒ yc ∨ xy ∨ xc
1 1 1 1 1 xyc
Turns out this is a really bad and brainless idea, but it is clearly possible.
Just implement the truth-table for the one-bit adder: expect both
Create the NOT versions of all inputs with inverters, then create AND
gates for each minterm needed in any output. Number gates 1-7 (000
not needed) and think of labels as binary for the
For interest's sake, going the other way is easy.
Getting the logic from the circuit means selecting a topological
order: what is natural and works is NOTs, ANDs, ORs. Clearly
NOT of
And for d:
Which you can prove is same as the KM expression (how?):
Gate delay and circuit speed: speed goes with the number of gates on the longest path in the circuit: analgous to program running time. Technology dictates absolute time.
Dollar cost about proportional to number of gates. Circuits on large areas need longer wires, get more propagation delay. Also imperfections are more likely with larger areas.
Large fan-in and fan-out (inputs and outputs) slow down a gate in practice.
So circuits can be optimized over several criteria.
Algorithm design techniques affect circuits, too ("basic ideas keep cropping up"...CB).
Could build an adder for integers from the one-bit, delay-3 example
adder. It's not bad design (can get delay two if we do all
complementing outside). This gives a ripple-carry adder. So
delay of
OR Design
The glue is a problem for the adder. This won't work:
Let the left half adder compute two answers, one each for 0 and 1
carry-in. When RH completes, know which answer to choose.
In fact delay for
We want
Note
If
(As usual, work thru cases to see these are right).
s: 0 t: 1 g: - p: 1
x x x x
y y y y
----- --- ---- -----
1 1 1- 1-
Here's our plan for the D and C adder: the FIX circuit must:
If carry into R of entire
Thus
If no carry in on R, get carry-out at L if either
R half bits unchanged from output of R
See Next Diagram!
Pick a case depending on g:
L half depends on how R can generate carry. If no carry in from R end
of
Pick a case depending on p:
If carry-in at R half. What about
Inside FIX we have circuits (depth at most 3, it turns out) for
E.g. for
D and C Adder:
Super-simple recurrence: Base-case 1-adder has delay 3, so does the
FIX.
So
Ripple Adder:
This goes like 1:9, 2:30, 4: 78: 8: 186 or in general
If
If