CS226: Digital Logic Design
CS254: Digital Logic Design Lab
(Spring 2018)


Announcements:
  • Final CS226 marks and grades. Happy vacations!
  • Please subscribe to moodle and Piazza to stay updated about the course. The code for joining the class on piazza has been announced in class. If you missed it, please contact the instructor.

Teaching Staff

Instructor Supratik Chakraborty
Friendly Theory TAs Swati Anand Kantikumar Anil Lahoti Vaishali Jhalani Himadri Sekhar Bandyopadhyay Ashish Mithole Mohammed Kaleem
 
Friendly Lab TAs Shubham Goel Kartik Singhal Shriram S. B. Utsav Anand Manjunath K Anup Kori Tarun Omprakash Verma

Hours

What When Where
Lectures
Thurs 15:30 - 17:00
Fri 15:30 - 17:00
LA 301, Lecture Hall Complex
CC 103, New CSE Building
 
Lab
Tues 14:00 - 17:00
LH 302, Lecture Hall Complex
 
Office hour
Thurs 18:00-19:00
(by prior email appointment)
Room 314 (New CSE Building)
 
Problem solving session
TBA
TBA

Grading

CS226 CS254
Midterm 30%
Endterm 40%
Quizes 30%
In-semester lab evaluation 30%
Final project 70%

Ground Rules

Online discussions

We will use Piazza as the primary mode of online discussion for this course. Please visit the course page and sign up as a student using the access code announced in class. Rather than emailing questions to the teaching staff, I encourage you to post your questions on Piazza.

Reading Material


Software needed for lab work

You will need to download and install the following software on your laptops for the lab assignments and for your final project.

Practice Questions and Exams

Please see last two years' (2016, 2017) course pages for old problem sets (practice and exam).
Questions Posted on Graded/Ungraded
Practice Question Set 1 Jan 13, 2018 Ungraded
Practice Question Set 2 Feb 4, 2018 Ungraded
Quiz 1 Feb 9, 2018 Graded
Mid-semester Exam Feb 26, 2018 Graded
Quiz 2 Apr 7, 2018 Graded
Quiz 3 Apr 18, 2018 Graded
End-semester Exam May 2, 2018 Graded


Lecture Schedule

DateTopics
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.

Lab Schedule

DateTopics
Jan 4 Introduction, lab logistics, a quick introduction to VHDL (Aniruddha's slides on VHDL)
Xilinx ISE related links: download local copy, Xilinx official installation/licensing doc, quick guide to installing/licensing ISE, getting started with ISE
Jan 9 More on VHDL, use of Xilinx ISE for design entry in VHDL, compilation and simulation using testbenches. Processes and sensitivity lists. Design of a simple, hierarchical design using processes. Simulation cycle of VHDL, and the notion of delta delays in simulation.
Files used in class: design, test harness
Jan 16 Implementing a Wallace Tree Multiplier for multiplying two 3-bit numbers using a hierarchical design style
Template top module
Jan 23 Implementing a simple encrypter and decrypter in VHDL. Problem statement
Template encrypter module , Template decrypter module
Jan 30 Mapping a simple design on the Digilent Atlys board.
Useful resources for FPGA mapping using Adept2: Windows pack, Ubuntu runtime, Linux utilities
A useful link for Linux users trying to install Adept2 (locally cached copy)
Digilent Atlys master constraints file
Encrypter, decrypter evaluation based on simulation in ISE.
Feb 6 Discussion on common errors in VHDL coding that lead to non-synthesizable designs, mapping encrypter and decrypter designs to Digilent Atlys board, evaluation based on designs mapped to board.
VHDL files, constraint file and readme file needed for wrapping your encrypter and decrypter designs before mapping them to Digital Atlys board.
Feb 13 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).
Feb 13 Railway signaling communication between Digilent Atlys board and a host machine (laptop) using FPGALink (problem statement)
Mar 6 More advanced communication between Digilent Atlys board and a host machine using FPGALink: revised and detailed problem statement, VHDL/C source file locations that may be useful to you when modifying your design (file locations)
Mar 13 More sophisticated communication between Digilent Atlys board and a host machine using FPGALink: problem statement
Mar 20, 27 UART communication on Digilent Atlys: some interesting reads -- Wikipedia page, a simple project, page 16 of the Xilinx Digilent Atlys manual, drivers from Exar.
Apr 3 Final project statement: communicating railway signal controller with clarifications
Apr 10 Final project help session
Apr 15 Final project demo, evaluation and viva