ECE 59500 - Digital Logic Systems: Design Automation

Lecture Hours: 3 Credits: 3

Counts as:

Experimental Course Offered: Spring 2010

Catalog Description:
This course will provide an introduction to the tools used to design and analyze circuits at the logic level of abstraction (where circuits are composed of gates and flip-flops). Most digital chips used in computing and electronic systems (including microprocessors, graphics processors, chips used in network routers, cell phones, digital audio/video appliances, automotive electronics) are entirely or largely designed using EDA tools. ECE595Z will focus on the foundations of logic-level EDA tools, including the design of exact and heuristic algorithms that form the basis for VLSI Computer-Aided Design. Topics covered include an overview of the IC design flow and levels of abstraction, synthesis of two-level (AND-OR / PLA) circuits, multi-level logic synthesis and technology mapping, sequential circuit synthesis, Logic-level verification using Boolean Satisfiability and BDDs, Timing Analysis, Power analysis and Reduction, and design techniques for emerging nanoscale technologies.

Required Text(s): None.

Recommended Text(s):
  1. Logic Synthesis, S. Devadas, A. Ghosh, K. Keutzer, McGraw-Hill, 1994, ISBN No. 9780070165007.
  2. Logic Synthesis and Verification, G.D. Hachtel and F. Somenzi, Kluwer Academic, 2006, ISBN No. 9780387310046.
  3. Synthesis and Optimization of Digital Circuits, G. De Micheli, Kluwer Academic, 2006, ISBN No. 9780387310046.

Learning Outcomes:

A student who successfully fulfills the course requirements will have demonstrated:
  1. an ability to design minimal combinational logic circuits.. [a,c,k]
  2. an ability to design minimal finite-state machines.. [a,c,k]

Lecture Outline:

Week(s) Major Topics
1 Introduction to EDA, Overview of VLSI Design flow and levels of abstraction in IC design, Quick tour through design automation at the logic level.
1 Advanced Boolean Algebra: Representations of Boolean functions, operations on Boolean functions, Co-factors and their applications, Unate functions and unate-recursive paradigm.
3 Two-level logic synthesis: Re-cap of K-maps and Quine McCluskey method, Covering as a core problem in EDA, exact and heuristic covering algorithms, efficient generation of prime implicants, ESPRESSO.
3 Multi-level logic synthesis: Boolean networks, transformations on Boolean networks, factoring, algebraic and Boolean division, Kernel-based factoring, Efficient factoring using 0-1 matrices, Satisfiability and Observability don't cares, optimization using don't cares, exact and heuristic algorithms for technology mapping, multi-level synthesis in practice.
1 Sequential optimization (Finite-State Machine Synthesis - State minimization and Encoding); Retiming
1 Timing Analysis: Clocking models for sequential circuits, delay models for gates, topological timing analysis, functional timing analysis and the false path problem,
1 Timing Optimization: Collapsing and Re-structuring, Generalized Bypass and Select Transforms, Eliminating false paths, technology mapping for minimum delay.
1 Binary Decision Diagrams, ROBDDS, efficient function manipulation and analysis using BDDs. Use of BDDs for verification.
1 Boolean Satisfiability - Algorithms and Applications to Verification.
2 Low power design - power estimation, technology mapping for low power, clock gating, power management at the logic level (operand isolation, guarded evaluation and pre-computation)
1 Current topics - variation-aware design, design for nanoscale technologies

Engineering Design Content:

Establishment of Objectives and Criteria
Synthesis
Analysis
Construction
Testing
Evaluation

Engineering Design Consideration(s):

Economic
Manufacturability