ECE574A

Digital Logic
Fall 2012
Designation: 
Required for ECE
Catalog Data: 

Graduate Course Information

==============================================

ECE 574A - Computer-Aided Logic Design

Credits: 3.00

Course Website: http://www2.engr.arizona.edu/~ece474a/D2L

UA Catalog Description: http://catalog.arizona.edu/allcats.html

Course Assessment:

Exam: 4 (lowest score dropped)

Project:  4 programming projects

Participation:  12-15 participation activities (1 dropped)

Grading Policy:

Typically: 55% Exams (4, lowest score dropped),

                40% Programming Assignments,

                  5% Participation/In-Class Exercises.

Course Summary:

This course is an introduction to Computer-Aided Logic Design. This is a highly active research area, enabling the design of increasingly complex digital systems. In this course we will mainly focus on three areas - specification, synthesis, and optimization. We will look at how to specify functionality at a variety of abstractions, use industry-standard tools to simulate these designs, investigate some of the underlying optimization techniques utilized, as well as develop your own tools. Topics include, but are not limited to (1) Register-Transfer Level (RTL) Design, (2) Behavioral Synthesis, (3) Optimization and Tradeoffs of Combinational and Sequential Circuits, (4) Exact and Heuristic Minimization of Two-Level Circuits.

Students will be expected to implement a variety of Verilog and C/C++ projects throughout the semester. While specific programming assignments may change with the course offering, projects typically focus on the implementation of optimization and synthesis methods discussed in class, as well as the RTL design. 

Prerequisite(s): 
ECE 275
Textbook(s): 

No textbook is required. The class notes/slides are sourced from the following materials:

Digital Design, Frank Vahid, John Wiley & Sons, ISBN 0470044373

Verilog for Digital Design, Frank Vahid and Roman Lysecky, John Wiley & Sons, ISBN 9780470052624

Logic Synthesis and Verification Algorithms, Gary D. Hachtel and Fabio Somenzi, Springer, ISBN 0387310045

Logic Minimization Algorithms for VLSI Synthesis, Robert K. Brayton, Gary D. Hathtel, C. McMullen, and Alberto L. Sangiovanni-Vincentelli, Kluwer Academic Publishers, ISBN 0898381649

Introduction to Algorithms, Thomas H. Cormen, Charles E. Leiserson, and Ronald L. Rivest, McGraw-Hill, 0070131430

Synthesis and Optimization of Digital Circuits, Giovanni De Micheli, McGraw-Hill, ISBN 0070163332

Course Learning Outcomes: 

By the end of this course, the student will be able to:

  1. Understand the difference between heuristic and exact optimization methods, and be able to classify a variety of algorithms into these categories.
  2. Use the Quine-McCluskey tabular minimization technique for identifying all the prime implicants, and solve the covering problem using Petrick’s method to find an optimal two-level implementation, for both completely specified and incompletely specified logic functions.
  3. Use Quine-McCluskey with iterative and recursive consensus methods for identifying all the prime implicants (complete sum), and solve the covering problem using row/column dominance to find a minimal gate, two-level implementation, for both completely specified and incompletely specified logic functions.
  4. Understand how generalized optimization algorithms can be adapted to the logic minimization problem.
  5. Use Branch-and-Bound along with MIS to solve the covering problem.
  6. Understand Espresso’s representation of Boolean functions and basic operations on compact cubical format.
  7. Use Espresso’s Unate Complement, Complement, and Expand subprocedures.
  8. Understand a variety of scheduling algorithms, including ASAP, ALAP, Hu’s, LIST_L, LIST_R, and Force Directed.
  9. Understand a variety of methods used for resource sharing and binding.
  10. Understand the role of verification in CAD along with the different testing methods.
  11. Design logic minimization tools in C/C++ and output the resulting circuit implementation in Verilog or equivalent textual representation.
Course Topics: 

1.     (Quick) Review of FSMs, RTL design, and Verilog.

2.     Graph theory basics – representation of graphs, breadth first search, depth first search, Dijkstra’s algorithm, Bellman Ford algorithm.

3.     Behavioral synthesis (scheduling) – Hu’s, LIST_L, LIST_R, Force Directed Scheduling.

4.     Behavioral synthesis (resource sharing and binding) – Resource compatibility/conflict graphs, clique partitioning, graph coloring, left-edge algorithms

5.     Behavioral synthesis (Datapath/controller generation) – sequential code to FSM+D implementation.

6.     Two-level Logic Optimization – Quine-McCluskey, Row/Column dominance, Branch and Bound, Simulated Annealing

7.     Heuristic Logic Optimization (Espresso) – Overview and representation, unate complement, complement, expand.

Class/Laboratory Schedule: 

Lecture:  150 minutes/week

Prepared by: 
Dr. Susan Lysecky
Prepared Date: 
April 2013

University of Arizona College of Engineering