==============================================================
                            SPRING 2009

     CSEE E6861:  COMPUTER-AIDED DESIGN OF DIGITAL SYSTEMS
==============================================================

Instructor:  Prof. Steven Nowick

Class Time:	Thursday, 4:10-6:00pm
Place:		825 Mudd Building
Credits:	3 points


--------------
PREREQUISITES:
--------------

(i) one semester of digital logic
  	(CSEE4823 or other course equivalent, or permission of the instructor)

(ii) a basic course in data structures and algorithms, and 
		familiarity with programming
		 (CS 3133/3134/3137/3139 or 3157 or equivalent).


NOTE:  *NO VLSI or EE circuits background is required!*


-------------------
COURSE DESCRIPTION:
-------------------

Introduction to modern CAD tools and algorithms for the design of
digital systems.

The course is a nice blend of three areas:  (i) digital design,
(ii) optimization algorithms, and (iii) software tools and applications.
It is suitable for students with a range of interests:  from 
those more interested in applied theory and algorithms, to those more
interested in digital design.

The course systematically covers the various automated synthesis steps
used in modern CAD tools:   starting from a user's high-level specification of 
an entire digital system, down to optimized low-level digital hardware.

When you have completed the course, you will have a good handle on 
modern research aspects of digital CAD (i.e., the underlying optimization 
algorithms used to automatically design digital systems), as well as gain 
some practical hands-on experience in using existing CAD packages.

NOTE: This is *not* primarily a project/lab course; while you will 
use real CAD tools, the focus will be on the algorithms and digital
optimization techniques behind them.  Also, you do *not* need to be 
an experienced digital designer to take this course:  you should simply 
have a basic background in digital logic.

---------
SYLLABUS:
---------

Introduction to modern digital CAD synthesis and optimization techniques.  
Topics include:  modern system-level design and optimization (high-level 
synthesis, register-transfer level modeling, optimal scheduling algorithms, 
resource allocation and binding, retiming of register placement); 
controller synthesis and optimization; modern exact/heuristic two-level 
logic minimization (espresso, mincov); advanced techniques for multi-level 
logic optimization (algebraic scripts, ODC's/CDC's, redundancy addition
and removal); optimal technology mapping to library cells (for delay, power, 
area minimization); combinational circuit equivalence verification; advanced 
compact Boolean data structures (ordered binary decision diagrams [OBDD's]); 
SAT solvers and their applications; static timing analysis; and 
synthesis for testability.  Includes written and hands-on assignments 
using and creating CAD tools. 

A small project is included, with choice of either software programming
or design tool application.

-------------------
REQUIRED TEXTBOOK:
-------------------
Giovanni De Micheli, "Synthesis and Optimization of Digital
Circuits", McGraw-Hill (1994).

This book is available at the Columbia University Bookstore
on Broadway and W.~115th Street.
Additional reading material and xeroxes will be available
on the class web page, and from the professor and TA.

----------
CLASS URL:
----------
(under construction, available shortly:)
       http://www1.cs.columbia.edu/~cs6861

------------------------------------------------------------------------