Topic 3: Karnaugh map and other combinational system refinements

Lecture 10 (2/12)

3 to 8 decoder: Behavior described from inputs, outputs and truth table (Mano's Table 2-1.) Implementation (figure 2-1). Implementation with 2 2 to 4 decoders (figure 2-3). Implementing a 4 to 16 decoder with two 3 to 8 decoders with enable.
Applications of decoders:

Decode opcode (of machine instuctions. Knowledge of what an opcode is prerequisite!) to generate signals on separate lines for each kind of machine instruction. See Mano's fig. 5-6.
Decode high order bits of a memory address to activate different memory units for different parts of memory. (Knowledge of addresses in assembly language is prerequisite!) See Mano's fig. 12-4.

Octal to binary encoder: See Mano's table 2-2.
Priority encoder: Mano's figure 11-14 gives an application.

Truth Table for 4 input priority encoder: 4 inputs and 3 outputs.

D3	D3	D1	D0	A1	A0	V
0	0	0	0	0	0	0
0	0	0	1	0	0	1
0	0	1	X	0	1	1
0	1	X	X	1	0	1
1	X	X	X	1	1	1

A read-only memory (ROM) is just a combinational system: k inputs are address lines, 1 enable line input, n data outputs when n is the memory word size. The truth table is for n Boolean functions of k variables. See Mano's section 2-7.

Lecture 11 (2/14)

"don't care" conditions

How they result from applying excitation tables for JK flip-flops to the sequential circuit design method.

Remarks about engineering tradeoffs between D flip-flops and JK flip-flops

D flip-flops are simpler and smaller inside but require more outside combinational logic.

JK flip-flops are more complex and bigger inside but sometimes allow less outside combinational logic.

JK flips-flops used to be popular (for MSI designs) but today D flip-flop cells are most popular for LSI designs.

mark corresponding K-map squares with X

leave each X covered or not, independantly, to obtain an optimal covering.

Dual may be better.

Compare OR of AND implementation to AND of OR implementation for the same map, in a case when AND of OR uses fewer gates.

AND of OR form: One AND subformula for each group of 0's. The ouput will be 0 when at least one of the subformulas has a 0 value. Explaining and understanding it English is a challenge!

Boolean duality principle: Replacing 0 by 1 and 1 by 0 transforms boolean relationships into new boolean relationships.

Under the duality transformation, applied to tables analogous to elementary school addition or multiplication tables.

The OR operator table is transformed to the AND operator table.

The AND table is transformed to the OR table.

The NOT table is transformed to the NOT table.

The relationship X=1 is transformed to X=0.

Karnaugh map structure revisited.

Review of K-map procedure.
Numbering and bit string labels for the squares.
The bit code of each square differs from the code of each up, down, left or right neighbor by ONE bit. (Wrap-around is included in the neighborhood relationship).
Example of "bad" choices of covering group
How a Gray code is obtained from a Karnaugh map. What a Gray code is. See Mano's table 3-5.
Picture of the 4 dimensional boolean cube.

The edges represent pairs of bit strings that differ in exactly one bit.

Midterm 1 syllabus break!!

Lecture 12 (2/16)

A n-bit Gray code is a Hamiltonial circuit of the Boolean n-cube's edge graph.
Practice problem: Generate table 3-5 yourself by using the recursive reflected Gray code generation algorithm:

The Dual transformation exchanges 0s and 1s in the truth table.

Example of a K-map and its dual.

Binary Decision Trees:

Symbolic Boolean Manipulation with Ordered Binary Decision Tree Diagrams, paper by Prof. Randal E. Bryant

Slides taken from pages 4, 5 and 6

Local link(.ps) (.pdf)
decision tree representation of a function given by a truth table.
"Binary decision diagrams have been recognized as abstract representations of Boolean functions for many years. Under the name "branching programs" ... . The key idea of OBDDs [ordered binary decision diagrams] is that by restricting the representation, Boolean manipulation becomes much simpler computationally."
What is a BDD? "A binary decision diagram represents a Boolean function as a rooted, directed acyclic graph.
... Each non-terminal vertex v is labeled by a variable var(v) and has arcs directed toward two children: lo(v) shown as a dashed line) corresponding to the case where the variable is assigned 0, and hi(v) (shown as a solid line) corresponding to the case where the variable is assigned 1.
"For an ordered BDD (OBDD), we impose a total ordering < over the set of variables and require that for any vertex u, and either nonterminal child v, their respective variables must be ordered var(u) < var(v)."
(Explanation of what a total ordering is: from CSI210).
Reductions of a decision tree to an OBDD illustrated by Fig. 2. The three reductions:

Remove Duplicate Terminals
Remove Duplicate Nonterminals
Remove Redundant tests

It it is mathematically proved (in say Anderson's paper below) that "The OBBD representation is canonical-for a given ordering, two OBBDs for a [THE SAME!] function are isomorphic.
Some consequences of this are described in the paper.

(2/19-President's day)

Lecture 13 (2/21) Midterm exam 1

Lecture 14 (2/23)

More on BDDs.

How different (total) orderings (on the variables) of the same boolean function give different BDDs with sometimes different sizes. (Illustrated by figures in the thesis below:)

Techniques for Efficient Formal Verification Uning Binary Decision Diagrams, Ph.D. thesis by Dr. Alan Hu

Link to Binary Decision Tree Diagram (applications) http://sprout.stanford.edu/dill/bdd.html
A paper(.ps) on BDDs by Henrik Reif Anderson

Local link(.ps) (.pdf)

Introduction to Register Transfer Language: What p: R1 <- R2 means, from Mano's book.