ECE 697B - Synthesis and Verification of Digital Systems

The following exams/projects will be scheduled during the course:

• Midterm Exam - Wednesday, April 05, 2006, at 6:00 pm in ELAB 305.
  • High Level Synthesis:
    - Basic concepts (sequencing graphs, DFG, phases of synthesis process).
    - Scheduling (ASAP, ALAP, List scheduling, ILP)
    - Allocation, resource binding; exact (ILP) and heuristic methods.

  • Boolean Functions, basics
    - Representations (SOP, factored forms, BDDs), canonicity, features.
    - Two-level vs multi-level functions, implementations.
    - Basic definitions: cofactors, Shannon expansion, primes, covers,
    - Tautology check, complementation, unateness, irredundancy.

  • Two-level Logic minimization:
    - Basics theory and heuristic minimization.
    - Exact, Quine-McCluskey method, unate covering; techniques to solve it
    - Unate recursive paradigm, heuristic optimization.

  • Binary Decision Diagrams
    • basic theory, reduction rules
    • construction, composition (Apply operation)

  ---

• Final Exam - Tuesday, May 23, at 8:00 am, MRST 211.

  The exam will be comprehensive for the quiz questions. The remaining questions will concentrate on the second (post-midterm) part of the course. Specifically, th following material will be covered.

  • Binary Decision Diagrams
    • Construction, composition,
    • Applications: functional decomposition, verification, SAT, etc.

  • Functional decomposition
    • Ashenhurst-Curtis (AC) decomposition, theory
    • AC decomposition using BDDs

  • Multi-level minimization
    • Algebraic transformation methods, factored forms
    • Algebraic division, kernel generation
    • Gain computation (extraction, factorization)

  • Technology mapping
    • Tree-based mapping, dynamic programming
    • General knowledge about other methods (binate covering)

  • Retiming
    • Clock period minimization, theory, constraints
    • Register minimization, LP formulation

  • Satisfiability (SAT)
    • BDD-based SAT for combinational
    • Formulating CNF formulas for gate level circuits

  • Formal verification
    • Combinational equivalence checking
    • Sequential equivalence checking, basics
    • FSM traversal, product machine, reachability analysis

  ---

  Students can elect to do project instead of the final exam. The project will be due by May 23, the day of final exam.

  No INCOMPLETE grades will be issued in the course, so please plan accordingly.

  ---