Lecture Schedule
Date  Topics 
Jan 3 
Introduction, course logistics, a couple of realworld
problems to motivate a systematic study of digital system
design, truthtables and designing circuits from them,
introduction to Karnaugh maps (Kmaps) 
Jan 6 
More on Kmaps and optimizing inputs of AND/OR gates in
twolevel ANDOR circuits, design of some basic building
blocks: halfadder, fulladder, nbit ripplecarry adder,
nbit carry lookahead adder, nbit comparator, multiplexors
and their variants. Comparison of nominal delays through
ripple carry adder and carry lookahead adder. 
Jan 10 
Two's complement representation of numbers and it's use in
computer arithmetic
(see this
for some more details), design of a combined adder/subtractor
unit, design of demuliplexors, encoders and decoders.
Discussion on designing a divider: need to get to a circuit from
an algorithm, necessity of feedback and problems caused by
unfettered feedback in digital circuits, need for flipflops to
break feedback loops and allow sequencing of steps, a simple
device (latch) for use in breaking feedback loops

Jan 13 
More on Dlatches and Dflipflops, need for care in choosing
delays when implementing latches and flipflops with gates,
their use in breaking feedback loops in dataprocessing paths.
Implementing a sequential integer division algorithm using
a simple datapath and appropriately sequenced control signals.
Importance of good datapath design, and the sequential control
synthesis problem.

Jan 17 
Complete design of controller for a new integer division
algorithm with a new datapath (some slides), different ways of updating
values of registers: controlling the data input vs controlling
the clock input

Jan 20  Reduced Ordered Binary Decision Diagrams (ROBDDS)
for representing and manipulating Boolean functions: Shannon
decomposition, variable ordering and reduced forms, canonicity of
representation, constructing ROBDDs of "f op g" from those of "f"
and "g" (Slides  read only the part taught in class) 
Jan 24 
Quiz 1

Jan 27 
More about ROBDDs: binary operations, ifthenelse operation,
function composition, counting satisfying assignments, etc. and
their complexities

Jan 31 
Variable ordering problem in ROBDDs, static and dynamic
reorderin gof variables, swapping adjacent variables in an
ROBDD

Feb 3 
Don't cares and ROBDDs: representing don't care sets and
using them to simplify ROBDDs in a recursive way,
analyzing termination cases.

Feb 7 
Problem session, and discussion of Quiz 1 solutions

Feb 10 
Discussion of some solutions of Quiz 1; Quiz 2

Feb 14 
More usage of don't cares: satisfiability don't cares (SDC)
and observability
(some
slides from University of Maryland, although not
everything in the slides is relevant for us)

Feb 17 
Problem solving session on ROBDDs in preparation for midsem

Feb 23 
Mid semester exam 
Feb 28 
Discussion of some midsem questions; introduction to
AndInverter Graphs (AIGs): definition, boolean operations on AIGs and
complexities, illustration of compose operation, rewrite, fraig,
strash, importance of SAT solving when operating with AIGs
(Slides) 
Mar 3 
Discussion of midsem solutions

Mar 7 
More discussion on AIGs: random simulation based heuristic
to reduce fraiging times, converting an AIG to an
equisatisfiable CNF formula using Tseitin encoding,
illustration of Tseiting encoding on a sample AIG,
demonstration of AIG operations on
the abc
tool.

Mar 10 
Further demonstration of
the abc
tool; introduction to static timing analysis: formulating delay
calculation as finding longest/shortest paths in a directed
acyclic graph, simple timing constraints for correct operation
of a sequential circuit  relation between clock period,
clocktoq delays, and minimum and maximum combinational logic
delays between flipflops

Mar 14 
Timing constraints for correct operation of a sequential
circuit: effect of clock skew, setup and hold times. The
timing closure problem and definitions of required times and
arrival times, illustrating why some delays in a circuit may
have no effect on timing closure.
Some online resources for static timing analysis: a
nice blog
(you can ignore advanced topics in parts 7 onwards), a good set
of slides(not everything covered in class)

Mar 17 
Static timing analysis: formulating simple timing closure
as a constraint satisfaction problem (CSP) with boolean
combinations of linear inequalities, greedy heuristics with
required and arrival time intervals for timing closure

Mar 21 
Static timing analysis: calculating slacks, different
kinds of slacks, and using slacks to identify paths along
which delays need to be modified for timing closure

Mar 24 
Discussion on asynchronous reset and synchronous reset;
effect of increasing/delaying delays on different kinds of
slacks, slack based iterative heuristic for timing closure

Mar 27 
Need for testing and verification of circuits, motivation
for reachability analysis (slides)

Mar 31 
More on reachability analysis, explicit and symbolic reachability
analysis, basic steps of symbolic reachability analysis

Apr 3 
Symbolic unbounded reachability analysis, demonstration using
abc, bounded reachability as a SAT problem, kinductive reachability
as a SAT problem

Apr 7 
Solving practice problems on symbolic unbounded
reachability analysis, more on bounded reachability and kinductive
reachability; introduction to retiming


Lab Schedule
Date  Topics 
Jan 4 
Introduction, lab logistics, a quick introduction to VHDL
(Aniruddha's
slides on VHDL) Xilinx ISE related links:
download local copy,
installation and licensing ,
getting started with ISE

Jan 11  More on VHDL, use of Xilinx ISE for design entry in
VHDL, compilation and simulation using testbenches. Design of a simple,
hierarchical 3bit ripplecarry adder using halfadders and fulladders.

Jan 18  Implementing FindSmallestIndex module in VHDL and
mapping a simple design to the Atlys FPGA board (couldn't be completed).
Useful resources for FPGA mapping using Adept2: Windows pack, Ubuntu runtime, Linux utilities
A useful link for Linux users trying to install Adept2
Digilent Atlys master constraints file

Jan 25  Mapping a simple design all the way down to
an FPGA board using Xilinx ISE and Adept2 (go through
this document
carefully for instructions)
Lab Assignment 1: Designing encryption and
decryption modules of a simple ATM controller
(problem
statement, VHDL skeleton
files: Controller
top
module, debouncer
module, constraints file for mapping on Digilent Atlys board)

Feb 1  Evaluation of Lab Assignment1

Feb 8  Disscussion of problems in Lab Assignment1, and fixes

Feb 15  Lab Assignment 2: Communicating between the
Digilent Atlys board and a host machine (laptop) using FPGALink
Useful resources for using FPGALink:
FPGALink user
manual (the manual is for the 2012 edition of FPGALink and most of
it works for the 2014 edition that we will be using; however there are
a few changes to the command line
interface flcli), detailed
instructions to build FPGALink (2014 edition) libraries and get a
small VHDL demo "cksum" working (the Linux installation works
perfectly and is preferred).

Mar 1  Updated problem statement for implementing
communication between Digilent Atlys board and a host program.

Mar 8  Evaluation of Lab assignment 2

Mar 15  Problem statement for implementing
full ATM controller, sample backend csv file, sample constraints file (do not change this file)

Mar 22  Designing a full ATM controller (continued)

Mar 29  Evaluation of full ATM controller design

Apr 5  Discussion on project,
problem
statement
See here
for an open source FPGA Ethernet MAC design in VHDL from Philipp
Kerling,
updated
constraints file for mapping the ports in the Ethernet MAC design
to Digilent Atlys board pins

