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


Announcements:
  • Please subscribe to moodle and Piazza (see below) to stay updated about the course.

Teaching Staff

Instructors Supratik Chakraborty Ashwin Gumaste
Friendly TAs Aniruddha Khushwaha Amit Goyal Jash Dave Samiran Roy Deepali Mittal Darsh Shah Aditya Nambiar Aditya Kusupati Shudhatma Jain Anand Dhoot Utkarsh Kumar Chandra Maloo

Hours

What When Where
Lectures
Tues 15:30 - 17:00
Fri 15:30 - 17:00
Classroom LH 101, Lecture Hall Complex
Lab
Wed 14:00 - 17:00
Classroom LH 101, Lecture Hall Complex (primarily)
OSL, Mathematics Building (if announced in advance)
Office hour
Thurs 17:00-18:00
(by email appointment)
CFDVS Lab 1 (Maths basement)
Problem solving session
Mon 21:30-23:00
SIC 201 (KReSIT Building)

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

Questions Posted on Solutions due by
Practice problem set 1 Jan 18, 2016  
Practice problem set 2 Feb 7, 2016  
Quiz 1 along with grading scheme Feb 16, 2016  
Practice problem set 3 and sample solutions Feb 22, 2016  
Mid-semester exam with model solution Feb 25, 2016  
Practice problem set 4 Mar 6, 2016  
Practice problem set 5 Mar 15, 2016 Mar 20, 2016
Quiz 2 Mar 17, 2016  
Practice problem set 6 Apr 11, 2016 April 16, 2016
Quiz 3 Apr 11, 2016  
Quiz 3 (supplement) Apr 15, 2016  
Practice problem set 7 and solutions Apr 25, 2016  
End-semester exam Apr 26, 2016  


Lecture Schedule

DateTopics
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 truth-table based approach using sum-of-product circuits, K-map 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, de-multiplexer, priority encoder. Slides for material covered in class.
Feb 2 Datapath design lectures by Prof. Ashwin Gumaste: D-, JK- and T-flip-flops, 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, if-then-else 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 K-maps and using a recursive formulation with ROBDDs.
Mar 1 And-inverter graphs (AIGs): definition, non-canonicity, 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. Linear-time conversion from AIG to equisatisfiable CNF formula: Tseitin encoding. Brief discussion on mid-sem 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 (divide-and-conquer) 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 flip-flops, 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 Re-timing: overview and simple applications for reducing flip-flop 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

Lab Schedule

DateTopics
Jan 6 Introduction, lab logistics, a quick introduction to VHDL (Aniruddha's slides on VHDL)
Jan 13 Using process statements with sensitivity lists in VHDL, updating registers a short delay after an enabling event using data values a short delay before the enabling event, implementing a given algorithm using process statements, caveats and solutions. Evaluation exercise.
Jan 20 More on process statements with sensitivity lists, unstable modules resulting from process statements, variables in process statements, contrasting zero delay in assignment to a variable with delta-delay in assignment to signals, how multiple delta delays can stack up when simulating assignments to signals in process statements; evaluation exercise using a circuit that mimics a division-like algorithm.
Feb 10 Stop-watch in VHDL. Click here for the problem statement.
Feb 17 Debouncer (and stop-watch) in VHDL. Click here for the problem statement.
Mar 2 Mapping stop-watch with debouncer from VHDL to an FPGA.
Mar 9 Introduction to abc and the BLIF format. Using abc to modify a given counter design, and optimize the design. BLIF documentation, and problem statement.
Mar 16 Using abc to optimize next-state logic of a sequential circuit. Problem statement
Mar 23 Project help session
Mar 30 Designing a simple musical instrument using digital logic. Problem statement
Apr 6 Project help session
Apr 13 Project viva evaluations