ECE 462

• Computer Engineering

This course teaches methods for design and synthesis of hardware at the logic level. It covers optimizations for designing low power, low cost and high performance multi-level logic. It covers design verification, manufacturing test and technology mapping. Multi-level combinational logic theory, sequential logic models, binary decision diagrams, finite state machines and unate function theory are covered. The course includes exposure and experience with CAD tools that do synthesis, verification and test.

Same as: CS 462 and MATH 491

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

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:

• 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

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

• 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.

Engineering Science: 2 credits
Engineering Design: 1 credit

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.

A. By half-way through the semester (roughly after 7 weeks), students will be able to do the following with respect to combinational logic synthesis.

1. Generate different types of canonical representations of Boolean functions, namely, Sum of Products, Product of Sums, Minimal and Complete Sum of Prime Implicants. (1, 6, 4)

2. Execute the Quine-McCluskey logic minimization algorithm involving generation of prime implicants and minimal cover for single and multiple output functions. (1, 6, 2)

3. Generate implicants, prime implicants, essential prime implicants and minimal sums using K-maps for single and multiple output functions (1)

4. Formulate and solve the unate covering problem using row and column dominance and compute the minimal sum of a Boolean function (1)

5. Identify problems that are of a complex (NP-hard) nature and apply exact algorithmic solutions like Branch and Bound method to them (1, 6, 7)

6. Determine if an exact algorithmic solution to an NP-hard problem is not scalable and apply heuristic, greedy algorithms instead (1, 6, 7)

7. Compute minimal sums for incompletely specified functions (1)

8. Derive and prove several practical properties of Unate functions and Symmetric functions in relation to prime implicants and minimal sums. (1, 6, 4)

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. (1)

10. Represent logic functions with Binary Decision Diagrams (BDDs) (1, 6)

11. Determine the equivalence of two Boolean functions using their Reduced Ordered BDDs (1, 6, 7)

12. Apply the ITE algorithm for efficient and scalable BDD computation (1, 6, 7)

13. Synthesize combinational logic circuits using a combination of multiple techniques (1, 6, 7)

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

1. Analyze faults, fault models, fault collapsing, fault minimization, fault dictionary and fault based diagnosis in combinational circuits (1, 6)

2. Derive a test vector for single and multiple stuck-at faults in a circuit using combinational automatic test pattern generation (ATPG) methods (1, 6)

4. Identify redundancies in circuits based on untestable faults, and add or elimimate redundancy in a design based on requirements (1, 2, 6, 7)

5. Analyze and design finite state machine (FSM) models of sequential systems (1)

6. Analyze an FSM for reachability from an initial state to a given state, using a fixpoint based search algorithm and BDDs (1, 6, 7)

7. Determine if two states in an FSM are equivalent using the Partition Refinement algorithm (1, 6)

8. Determine equivalence between two FSMs using product machines and reachability analysis (1, 6, 7)

9. Minimize incompletely specified FSMs with a covering problem formulation (1, 2, 7)

10. Represent multi level logic circuits as algebraic and Boolean factored forms and design multi level logic from sum of product representations (1, 2, 6)

11. Determine the value of a factorization and equivalent, maximal and optimum factorizations for a factored form (1, 6)

10. Compute division, kernels and co-kernels for decomposition and restructuring in a multi level logic circuit (1, 2, 6)

11. Map a given combinational Boolean circuit into a library of gates provided by its underlying implementation technology (1, 2, 4, 6, 7) for optimal area using heuristics

13. Perform technology mapping using an optimal dynamic programming algorithm (1, 2, 4, 6, 7)

14. Learn and apply concepts of dynamic programming for graph/tree covering problems (1, 6)

15. Map a given logic function to a technology library for optimizing area and delay (1, 2, 6, 7)