EE 552 Advanced Switching
Theory and Logic Design
Course Content and Outline
Administrivia and review
Special Topics in Synchronous
Systems
We consider special topics in combinational logic, selected either because
of their strategic value in broadening the designer's perspective, perceptions
and practical arsenal of design tools or for their role in modern large scale
logic design.
Decomposition of
Boolean functions and Binary decision diagrams (BDDs)
Function decomposition: canonical vs. Boolean, simple vs. complex,
completely vs. incompletely specified, disjunctive vs. nondisjunctive.
Ordered BDDs. Reduced
BDDs. Operations on BDDs.
BDD-based logic design. BDDs and VLSI design. Additional
topics in BDDs. Applications.
Linear logic
Combinational linear circuits. Sequential vs. polynomial domains. Feed-forward circuits. Impulse response.
Transfer functions. Series/parallel networks.
Feedback/shift register circuits. Applications
to digital communications.
Reduction
methodology
Equivalence, compatibility and covering; paircharts;
maximal and prime compatibles; applications to state minimization
Metastability
Stable vs metastable
states; effects of metastability; common problems;
practical solutions
Asynchronous
Systems
Introduction to asynchronous sequential circuits
Overview of asynchronous methods: unbounded-delay models –
speed-independent, quasi-delay insensitive, and delay-insensitive design;
bounded-delay models – Huffman, locally clocked, burst mode, and extended burst
mode design. Fundamental mode operation; classification of asynchronous
networks; single input change restriction; total states; normalization; primitivization; row reduction
Races and
asynchronous state assignments
Examples. Karnaugh state
and flow maps. Critical/noncritical
races. Transition time; code sharing. High speed assignments. Special assignments: connected row
set, one hot, "one shot", Hamming and universal. Liu and Tracey
algorithms
Combinational
hazards: detection & elimination
Stray vs. inserted delays. Pure vs. inertial delays. Static vs. dynamic
transitions. Logic vs. function hazards. Boolean
reduction. Generalized substitution. 8-valued algebra.
Sequential hazards:
detection & elimination
Examples. Relevant transitions. Steady state and
output hazards. Subspace mapping. Sequential hazard
detection algorithm.
Essential hazards;
alternative delay models
Why delays are inserted and when
they can be eliminated; back-and-forth test; introduction to burst mode
networks. How to design without inserted delays when line delays are negligible
– the
restricted delay assumption
Speed independent
logic design
How to
succeed, whatever the speed. Handshaking
and circuit completion logic. Two-rail encoded logic. Two-phase
processing.
Advances in
asynchronous logic - an overview
Motivations,
goals, and payoffs. Traditional concepts and delay models.
Classifying design methodologies: by delay model, by environmental model, by
design style. Practical achievements.
Asynchronous micropipelines
Two and four-phase handshaking, C-elements, asynchronous FIFOs, asynchronous micropipeline
operation,
Extended burst-mode
circuits
Extended
burst-mode circuits - a unifying generalization of synchronous and
bounded-delay asynchronous logic design.
Selected topics in
modern asynchronous design
Supporting Material Availability
Course Text: Ellison, Techniques in Advanced Switching Theory,
2002, 5th printing From instructor
Miscellaneous required
readings Handouts: sets 1 - 4
Recommended, optional, and
reference material learn.usc.edu
Background material learn.usc.edu