ECE 462
Logic Synthesis

Section Type Times Days Location Instructor
D DIS 1100 - 1220 T R   1015 ECE Building  Shobha Vasudevan
Web Page
Official Description Unate function theory, unate recursive paradigm, synthesis of two-level logic, synthesis of incompletely specified combinational logic, multi-level logic synthesis, binary decision diagrams, finite state machine synthesis, automatic test pattern generation and design for test, equivalence checking and reachability analysis of finite machines, and technology mapping. Course Information: 3 undergraduate hours. 4 graduate hours. Prerequisite: ECE 220 or CS 233.
Subject Area Computer Engineering
Course Prerequisites Credit in ECE 220 or CS 233
Course Directors Shobha Vasudevan
Detailed Description and Outline

To provide a designer's understanding of realistic digital subsystems, including hazards, faults, and races. To appreciate design tradeoffs and the interdependence of design decisions.


  • Review of switching algebra and Karnaugh maps
  • Combinational network analysis
  • Combinational network design
  • Logic minimization
  • Sequence network analysis
  • Fault detection
  • Sequential network design
  • Finite state machine testing

Same as: CS 462 and MATH 491

Computer Usage

It is suggested (but not mandatory) that a high-level language implementation of a minimization technique (McCluskey, Tison, etc.) be produced.

Topical Prerequisities
  • Design of combinational networks by Karnaugh maps
  • Analysis and design of elementary synchronous sequential networks
  • Familiarity with basic discrete mathematics for computer science and engineering

Hachtel and Somenzi, Logic Synthesis and Verification Algorithms.

ABET Category

Engineering Science: 2 credits
Engineering Design: 1 credit

Course Goals

This course is a technical elective for electrical and computer engineering, computer science and mathematics majors. The goals are to impart advanced theoretical concepts in the design of digital logic circuits that will prepare a student for graduate research work in logic optimization, simulation and testing, asynchronous circuits, and finite-state machine theory.

Instructional Objectives

A. By half-way through the semester (roughly after 7 weeks), students will be able to do the following in relation to combinational circuits.

1. Generate four different types of canonical representations of Boolean expressions, namely, Sum of Fundamental Products, Complete Sum of Prime Implicants, Ordered Binary Decision Diagram (BDD) and Reed-Muller Canonical (RMC) forms. (a,b,j)

2. Execute by hand the Quine-McCluskey logic minimization algorithm involving generation of prime implicants and minimal cover. (a,b,c)

3. Generate by hand all prime implicants from a given Boolean sum of products expression using Iterative Consensus method. (a)

4. Formulate minimal cover problem into a Boolean algebraic form, using Petric's Method. (a)

5. Determine the existence of static logic hazard in combinational circuits using analytical and simulation methods. (a,k)

6. Design two-level combinational circuits that are minimal and hazard-free. (c)

7. Determine if a Boolean function is totally symmetric and express it in a compact notation. (a)

8. Derive several properties of Unate Boolean functions in relation to prime implicants and minimal sums. (a,j,k)

9. Compute Boolean Difference of a function with respect to a variable and derive a test vector for a stuck-at fault on a node. (a)

10. Derive a test vector for stuck-at fault in a network using path sensitization method. (a,b,j,k)

11. Perform a simple decomposition of a Boolean function into two disjoint functions (a)

12. Express a Boolean function as a Threshold Function (if one exists) by formulating a system of inequalities and solving it or prove that a solution does not exist. (a)

B. By the end of the second half of the semester (after another 7 weeks) students will be able to do the following in relation to sequential circuits.

1. Analyze a simple latch and express its behavior in equation and tabular forms. (a,b)

2. Identify a potential hazard problem in widely used clocked SR and D latches and construct three different solutions to eliminate this hazard using delay insertion in circuits, additional logic gate and constraining the clock and clock-bar signals. (a,c)

3. Analyze Fundamental Mode asynchronous circuits for state behavior, Critical Races and Essential Hazards. (a,j)

4. Design fundamental mode SR and D flip-flops and analyze them for essential hazards. (c)

5. Analyze pulse mode circuits designed using edge-triggered flip-flops. (a,b)

6. Explore sequential circuit design alternatives, double-latch and single-latch two-phase designs, and single-latch single-clock designs. (j)

7. Derive state tables from word description of finite state machine (FSM) behavior. (a,c)

8. Derive general capabilities of finite state machines (FSMs). (b)

9. Simplify a completely specified FSM by removing unreachable states and equivalent states. (a,c)

10. Derive state equivalence partition of a completely specified FSM. (a,c)

11. Determine if two FSMs are equivalent in their behavior. (a,b)

12. Reduce the number of states of an incompletely specified FSM by computing maximal compatibility classes of states. (a,c)

13. Derive a Synchronizing (Reset) Sequence for a given FSM, or show that such a sequence doesn't exist. (a,b)

14. Derive a Homing Sequence for a given FSM which when applied to the FSM can uniquely identify the final state by observing the outputs. (a,b)

15. Derive a Distinguishing Sequence for a given FSM which when applied to the FSM can uniquely identify the starting state by observing the outputs. (a,b)

16. Devise a Machine Identification Experiment for an FSM. (a,b)

17. Devise a Checking Experiment to check the malfunction of an FSM assuming the number of internal states do not increase as a result of the malfunction. (a,b)

18. Identify the cost and complexity of testing sequential circuits and devise Design for Test solutions to reduce the cost and complexity of testing. (a,c,j)

Last updated: 8/8/2014