Date  Topics 
Jan 5 
Introduction, course logistics, motivation for turning
algorithms to circuits, basic logic gates, truthtables and
designing circuits from them, introduction to Karnaugh maps
(Kmaps) 
Jan 11 
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,
Discussion of nominal delays through ripple carry adder. 
Jan 12 
More on adders, design of nbit carry lookahead adders and nominal
delay analysis, design of nbit comparators and multiplexors.
Converting simple programs to circuits using the datapath blocks
(adders, comparators, multiplexors) learnt so far. 
Jan 18 
Role of feedback in datapath design, discussion of problems
that can arise with direct feedback (without latches/flipflops)
in datapath. Timing diagram, functionality and design of a D
latch, and how it can help break feedback loops in a datapath
design. 
Jan 19 
More on design of D latches, informal discussion of timing
constraints required for correct functioning of D latches,
building edgetriggered D flipflops from latches. Use of
flipflops in datapath designs, and different ways in which
updates of flipflops can be controlled.

Jan 25 
More on D flipflops, asynchronous set and reset of latches and
flipflops, building registers using D flipflops.
Datapath design for implementing an exponentiation algorithm, role
of multiplexors in steering different inputs to registers.
Problems associated with clockgating in highspeed designs.

Jan 26 
No classes on account of Republic Day 
Feb 1 
Class cancelled. Compensation class on Wed, Feb 7 
Feb 2 
Designing the controller for an exponentiation algorithm: extracting
a controlflow graph (state transition diagram) from the algorithm,
assigning codes to states, implementing controller state transitions
as Boolean functions, role of timing in correct functioning of the
controller and datapath. 
Feb 7 
Implementing arbitrary controlflow graphs (state transition diagrams)
as sequential circuits: going from state transition diagrams to circuits
and back, role of state encoding, naturality of don't cares in both inputs
and outputs, difficulty of implementing controlflow graphs with many
states/inputs using truthtables or Karnaugh maps. Reduced Ordered
Binary Decision diagram: an alternative and often compact representation
of Boolean functions (slides  refer to only the
part about ROBDDs) 
Feb 8 
More on ROBDDs: effect of variable ordering, canonicity under a given
variable order, inevitability of exponential size in worstcase. Examples
of ROBDD construction. ROBDDs, the "ite" operator and multiplexor circuits.
Operating on ROBDDs: negation and arbitrary Boolean operators 
Feb 9 
More on operations on ROBDDs: illustrating through examples. Quiz 1 
Feb 15 
Constructing ROBDDs for ite and compose operators using
a recursive algorithm. Discussion of Quiz 1 solutions.

Feb 16 
Detailed discussion of Quiz 1, Question 2 and its
solution. Continuing with ROBDDs: counting satisfying assignments,
effect of variable ordering, and intuition of why some variable orderings
are bad for some functions.

Mar 1 
Detailed discussion of midsem solutions. Role of don't cares in
digital logic design, and various sources of don't cares.

Mar 2 
Holi break

Mar 8 
More on different kinds of don't cares, reasons why they arise,
and how they can be exploited. External don't cares (ExDC),
satisfiability don't cares (SDC) and observability don't cares
(ODC) and their differences.

Mar 9 
Satisfiability don't cares (SDCs) and their use in optimizing
modules in a given circuit. Simple example of SDCs arising from
correlated inputs to a module. Systematic generation of SDCs from
a given circuit. Revisiting the notion of simplifying a function
f given a set of don't cares specified as another function
g.

Mar 15 
More about SDCs and algorithmic ways to calculate them. Observability
don't cares (ODCs) and their use in simplifying modules inside a circuit.
Boolean derivative of a function, and its use in calculating ODCs. An
algorithm for computing ODCs for the output of an internal module in a
large circuit. Midsem feedback session

Mar 16 
Further discussion about SDCs and ODCs. Working out an example
for calculation of DCs using ExDCs, SDCs and ODCs. Discussion of
grading scheme for midsem. Midsem crib session.

Mar 22 
AndInverter Graphs (AIGs): definition, properties,
noncanonicity, pros and cons. Boolean operations on AIGs,
ternary operations on AIGs, composition using AIGs. Rewrites,
strashing and fraiging in AIGs. Filtering pairs of nodes for
equivalence/complementation checks for fraiging.

Mar 23 
No class. Compensation lecture of Apr 11

Mar 29 
No class. Institute holiday

Mar 30 
No class. Instiute holiday

Apr 5 
Role of SAT solvers in AIG based reasoning: illustration using
fraiging. Converting an AIG to an equisatisfiable CNF formula: Tseitin
encoding and its properties. Applications of ROBDDs and AIGs in checking
equivalence of combinational circuits, and sequential circuits (where
state encoding is preserved).

Apr 6 
Demo of AIGs in action
using
abc . Static timing analysis of combinational circuits:
basic formulation as longest and shortest path calculation in
directed acyclic graphs. Analyzing sequential circuits: Propagation
delays and setup time of flipflops. Relation between clockperiod
and maximum delay through nextstate combinational logic.

Apr 7 
Quiz 2

Apr 12 
Modifying delays of gates to ensure that all timing constraints
required for correct circuit operation are satisfied. A pseudoboolean
constraint formulation for choosing gates from a given library to ensure
that all timing constraints are satisfied  advantages (completeness)
and disadvantages (complexity) of the approach.

Apr 13 
Notion of slack in timing analysis; requirement of nonnegative
slacks at all gates. An efficient, iterative heuristic for
identifying gates with negative slacks and changing gate delays
with the objective of rendering slacks of all gates as
nonnegative. Illustration of heuristic through example. The
timing closure problem.

Apr 18 
Quiz 3

Apr 19 
Discussion of solutions of Quiz 2 and Quiz 3.

Apr 20 
Retiming as an optimization of sequential circuits:
illustrative example, general principle, different optimization
criteria. Review of the contents of entire course. Graded quiz 2
answerbook distribution.
