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

  • Quiz 4 on Wed, Apr 12, 6pm - 7.30pm in KReSIT 201 and 301. Syllabus includes all that will be taught until Tues, Apr 11
  • Some links to online material on static timing analysis and symbolic reachability analysis have been posted. See the "Lecture Schedule" section.
  • Please subscribe to moodle and Piazza to stay updated about the course. The code for joining the class will be announced in class.

Teaching Staff

Instructor Supratik Chakraborty
Friendly Theory TAs Diptesh Kanojia Shudhatma Jain Samiran Roy A. V. N. Raju Kajal Gupta Vertika Srivastava
Friendly Lab TAs Aniruddha Khushwaha Aditya Kusupati Shubham Goel Kushal Babel Kapil Vaidya Hardik Gawari Manjunath K Abhilash Panicker


What When Where
Tues 15:30 - 17:00
Fri 15:30 - 17:00
CC 103, New CSE Building/center>
Wed 14:00 - 17:00
LH 101, Lecture Hall Complex
Office hour
Thurs 18:00-19:00
(by prior email appointment)
Room 314 (New CSE Building)
Problem solving session


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 year's course page for old problem sets (practice and exam).
Questions Posted on Solutions due by
Practice problem set 1Jan 20, 2017 Self-practice
Quiz 1Jan 24, 2017 In-class (3.30-5.00pm)
Practice problem set 2Feb 9, 2017 Self-practice
Quiz 2Feb 10, 2017 In-class (4.00-5.00 pm)
Practice problem set 3Feb 23, 2017 Self-practice
Midsem ExamFeb 23, 2017 In-hall (5.30-7.45pm)

Lecture Schedule

Jan 3 Introduction, course logistics, a couple of real-world problems to motivate a systematic study of digital system design, truth-tables and designing circuits from them, introduction to Karnaugh maps (K-maps)
Jan 6 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, n-bit carry lookahead adder, n-bit 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 de-muliplexors, 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 flip-flops to break feedback loops and allow sequencing of steps, a simple device (latch) for use in breaking feedback loops
Jan 13 More on D-latches and D-flip-flops, need for care in choosing delays when implementing latches and flip-flops with gates, their use in breaking feedback loops in data-processing 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 20Reduced 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, if-then-else 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 mid-sem questions; introduction to And-Inverter 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 fraig-ing 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, clock-to-q delays, and minimum and maximum combinational logic delays between flip-flops
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, k-inductive reachability as a SAT problem
Apr 7 Solving practice problems on symbolic unbounded reachability analysis, more on bounded reachability and k-inductive reachability; introduction to re-timing

Lab Schedule

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 3-bit ripple-carry adder using half-adders and full-adders.
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 8Evaluation 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 22Designing a full ATM controller (continued)
Mar 29Evaluation of full ATM controller design
Apr 5Discussion 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