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


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

Background material