Date | Topics |
Jan 5 |
Introduction, course logistics, motivation for turning
algorithms to circuits, basic logic gates, truth-tables and
designing circuits from them, introduction to Karnaugh maps
(K-maps) |
Jan 11 |
More on K-maps and optimizing inputs of AND/OR gates in
two-level AND-OR circuits, design of some basic building
blocks: half-adder, full-adder, n-bit ripple-carry adder,
Discussion of nominal delays through ripple carry adder. |
Jan 12 |
More on adders, design of n-bit carry lookahead adders and nominal
delay analysis, design of n-bit 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/flip-flops)
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 edge-triggered D flip-flops from latches. Use of
flip-flops in datapath designs, and different ways in which
updates of flip-flops can be controlled.
|
Jan 25 |
More on D flip-flops, asynchronous set and reset of latches and
flip-flops, building registers using D flip-flops.
Datapath design for implementing an exponentiation algorithm, role
of multiplexors in steering different inputs to registers.
Problems associated with clock-gating in high-speed 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 control-flow 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 control-flow 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 control-flow graphs with many
states/inputs using truth-tables 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 worst-case. 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. Re-visiting 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 |
And-Inverter Graphs (AIGs): definition, properties,
non-canonicity, pros and cons. Boolean operations on AIGs,
ternary operations on AIGs, composition using AIGs. Rewrites,
strash-ing and fraig-ing in AIGs. Filtering pairs of nodes for
equivalence/complementation checks for fraig-ing.
|
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
fraig-ing. 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 flip-flops. Relation between clock-period
and maximum delay through next-state 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 pseudo-boolean
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 non-negative
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
non-negative. 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 |
Re-timing 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.
|