Date  Topics 
Jan 5 
Introduction, course logistics, a couple of challenge problems
to motivate a systematic study of digital system design, examining
a few algorithms for integer division with the intent of implementing
these as digital logic circuits 
Jan 8 
Delving deeper into the design of a divider: identification of
a controller and a datapath to implement a division algorithm,
role of registers and delays, discussion on the tradeoff between
space (circuit size) and delay 
Jan 12 
Examining the integer division datapath more closely:
moving registers around, and their impact on the computation;
a naive controller design for integer division, and the importance
of sequencing operations correctly; a differential equation solver:
another example of control and datapath design starting from a
given algorithm

Jan 15 
Controlling updates of registers: controlling clock input
versus controlling data input; multiplexors: their role in
datapath design, and their implementation; designing a
controller for the integer division algorithm; need for
hidden state variables in the controller. Slides showing datapath and controller of divider. 
Jan 19 
Controller design: state transition tables and diagrams.
Implementing state transition logic as a Boolean circuit:
naive truthtable based approach using sumofproduct circuits,
Kmap based approach and the benefits of identifying large cubes,
limitations of both approaches. Don't cares in compact
specification of logic functions. Partial specifications of
logic functions. Introduction to Binary Decision Diagrams
for representing logic functions. 
Jan 22, 29 
Datapath design lectures by Prof. Ashwin Gumaste: adders,
subtractors, multiplier, comparator, decoder, encoder, multiplexer,
demultiplexer, priority encoder.
Slides for material covered in class.

Feb 2 
Datapath design lectures by Prof. Ashwin Gumaste: D, JK and
Tflipflops, state equations and state machines, sequence detector
example.
Slides for material covered in class
(ignore the slides on the implication chart method).

Feb 5 
Taking stock of CS226 and CS254 so far. Using ROBDDs to represent
and manipulate Boolean functions, multiplexer circuits from ROBDDs,
variable ordering and ROBDD size, negation and binary operations
on ROBDDs.
Slides  ignore the point
about "quantification" on slide 13. You can also ignore slides 21
and 22. You need to see up to slide 23 for ROBDDs.

Feb 9 
More about ROBDDs: binary operations, ifthenelse operation,
function composition, counting satisfying assignments, etc.
Some simple rules of thumb for good variable
ordering  swapping adjacent variables in an order and
dynamic "sifting". 
Feb 12 
More about swapping adjacent variables in an order, use of
unique table and computed table to construct ROBDDs, brief
discussion on garbage collection of unused nodes in an ROBDD.

Feb 16 
Solving example problems on ROBDDs; Quiz 1 
Feb 19 
Discussing solutions to quiz 1; ROBDDs with complement edges, rules
to choose between alternate ROBDDs with complement edges
representing the same function; simplifying functions using don't
cares on Kmaps and using a recursive formulation with ROBDDs.

Mar 1 
Andinverter graphs (AIGs): definition, noncanonicity,
simple operations, advantages and disadvantages. Operations to
simplify AIGs: simplify, strash, fraig. Importance of SAT solving
in simplifying AIGs.

Mar 4 
More on simplification of AIGs: balance, refactor, collapse.
Lineartime conversion from AIG to equisatisfiable CNF formula:
Tseitin encoding. Brief discussion on midsem solutions.

Mar 8 
Simplifying ROBDDs using don't cares (or cares). Deciding
termination cases in recursive formulation of simplification.
Discussion on why local optima may not lead to global optimum
when using a recursive (divideandconquer) approach to
simplification; illustration of this phenomenon through
an example.

Mar 11 
Different kinds of don't cares: satisfiability don't cares
(SDC), observability don't cares (ODC), external don't cares
(EXDC). EXDCs resulting from unreachable states of sequential
state machines. Computing SDCs in a combinational circuit and
simplifying digital circuits using SDCs.

Mar 15 
Computing ODCs in a
combinational circuit, and using them to simplify digital
circuits. Static and dynamic timing analysis: simple
algorithms and their applications; false paths in timing
analysis.

Mar 18 
More on static timing analysis (STA) and simple
shortest/longest STA algorithms; setup and hold time of
flipflops, identifying safe clock periods. Calculating
latest and earliest required times of change at gates in a
given combinational circuit; identifying gates whose delays
need to be changed to ensure required minimum and maximum
circuit delays

Mar 22 
More on how delays of gates in a combinational circuit can
be altered to meet minimum and maximum delay requirements
through the circuit.

Mar 29 
Lecture by Prof. Ashwin Gumaste: All about FPGAs ( Slides)

Apr 1 
Retiming: overview and simple applications for reducing
flipflop count and minimum clock period in a given sequential
circuit.

Apr 5 
Finding conditions for propagating transitions from inputs
along specific paths with prescribed delays; formulation as a
constraint solving problem, and illustration through examples.
Automatic formal verification: Significance of the reachability
problem, and some naive ways of computing reachable states;
representing sets of states using Boolean functions.

Apr 12 
Automatic formal verification: Symbolic algorithms for solving
the reachability problem, and applications in logic optimization.
Slides
on symbolic reachability analysis.

Apr 15 
Revision, problem clearing session
