ECE 462
Logic Synthesis
Menu: Course View Options
Section  Type  Times  Days  Location  Instructor 

D  DIS  1100  1220  T R  1015 ECE Building  Shobha Vasudevan 
Web Page  http://courses.engr.illinois.edu/ece462/ 

Official Description  Unate function theory, unate recursive paradigm, synthesis of twolevel logic, synthesis of incompletely specified combinational logic, multilevel 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. Topics:
Same as: CS 462 and MATH 491 
Computer Usage 
It is suggested (but not mandatory) that a highlevel language implementation of a minimization technique (McCluskey, Tison, etc.) be produced. 
Topical Prerequisities 

Texts 
Hachtel and Somenzi, Logic Synthesis and Verification Algorithms. 
ABET Category 
Engineering Science: 2 credits 
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 finitestate machine theory. 
Instructional Objectives 
A. By halfway 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 ReedMuller Canonical (RMC) forms. (a,b,j) 2. Execute by hand the QuineMcCluskey 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 twolevel combinational circuits that are minimal and hazardfree. (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 stuckat fault on a node. (a) 10. Derive a test vector for stuckat 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 clockbar 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 flipflops and analyze them for essential hazards. (c) 5. Analyze pulse mode circuits designed using edgetriggered flipflops. (a,b) 6. Explore sequential circuit design alternatives, doublelatch and singlelatch twophase designs, and singlelatch singleclock 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) 