ECE 59500 - Digital Logic Systems: Design Automation

Course Details

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

Assessment Method:

Homework assignments and exams.