ECE 462 - Logic Synthesis

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. 3 graduate hours. Prerequisite: ECE 220 or CS 233.

Subject Area

Computer Engineering

Course Director

Description

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.

Notes

Same as: CS 462 and MATH 491

Goals

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

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:

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

  • 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

Texts

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 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)

Last updated

5/7/2019by Shobha Vasudevan