ENEE 644 Computer-Aided Design of Digital Systems
-- Logic Synthesis and Optimization
(last update: 05/12/2003)
(05/12/03) HW6 posted.
It consists of suggested problems on the minimization of incompletely
specified machine and state encoding.
The assignment is optional, meaning that you
do not have to turn it in.
However, I highly recommend you to at least take a look of these problems.
Finally, you can use this to replace the lowest
score you have received in the prvious five homework assignments.
- Due 5:00 pm Friday, May 16: in my mailbox or to my office if you want the
graded homework back before the final.
- Due 1:30 pm Tuesay, May 20: in our classroom right before the final
(05/02/03) HW5 posted, due Wednesday, May 14 in class.
(04/14/03) Pattern graphs file posted.
(04/13/03) Project specification posted
The final project specification is posted.
There is no changes been made from the original posting, just a few places
that have been made more clear.
The TA will post the pattern graph file that is going to be used
in the project soon.
(04/13/03) Homework pick-up
I will bring the grades homework #2 and pattern graphs assignment to class
on Monday. So you can pick them up after the lecture. You can also get your
homework #1 if you have not picked them up yet.
Homework #3 is due in class on Monday
and the solutions will be posted outside my office after class.
(04/07/03) Sample Midterms posted
The midterm will be on Wednesday, April 16 from 2:00 pm - 3:30 pm.
Midterms from the previous two years are posted as:
sample 1 and
(04/07/03) Homework solutions
I have posted the solution to homework 1 outside my office.
There are two sets of solutions that are identical.
They are not for you to take away.
If you want to make a copy, please make sure that the other copy is there
and return it back after you finish copying.
(03/28/03) HW 3 is assigned and due on Monday, April
14 in class.
(03/24/03) Important announcements on the project:
getting the pattern graphs for library cells
posted, due Monday April 7, in class.
If you have any questions, comments, and suggestions on the draft of
project description , please
also let us know no later than the lecture on Monday April 7.
The formal and FIRM project description will be posted by Wednesday April 9.
The tentative project due date is 11:59 pm, Sunday May
(03/13/03) Lecture notes for the week of Mar. 17 posted.
Homework 2 is now due in class on Monday, March 31st.
(03/12/03) Project description is
posted. Please send your questions and comments to the TA and Dr. Qu.
We will maintain a link to post all the questions and answers with regarding
(03/07/03) Homework 2 is posted. Please note the
due date information.
(03/04/03) The room for TA's office hour has been moved to AVW 1458.
(03/01/03) Dynamic programming to solve Technology Mapping.
The course project will be on using dynamic programming algorithm to solve
the technology mapping problem. Both will be discussed in great details in
this coming week's lectures. Please check the
lecture notes and another one-page note on
dynamic programming. You are welcome to come to me or the TA if you have
any questions on these.
(02/21/03) a question on HW1:
> For chp3.35;
> (b) ab=> c=a'=b'=c
> (e) y'=> z=(x'+z)(y+z)
> what does it mean? "=>"sign?
a=>b is defined as the function a'+b.
(See prob. 39 on page 120 for more about this.)
HW 1 is posted and will be due Wednesday, Feb. 26 in
class. Please also complete the brief course information
sheet and turn in with your homework.
When you send email to me, please start the subject title with "644: ...".
As I am receiving dozens of emails everyday, this will make sure that your
message will be opened promptly. Normally, I will reply within 48 hours.
An email with subject title: "Welcome to ENEE 644 and more" was sent to you
on Feb. 4. Please check all your email accounts (mostlikely wam or glue
accounts). If you have not received this message, send me a message so I can
add you into the class emailing list.
Homework 6: (optional) give it to me, to my office or in my mailbox, before
5:00 pm Friday, May 16 if you want me to grade it.
- Chapter 8: 1,2,3,4,7,8,9
- Apendix B: (pp. 533-534) 24, 26, 27, 28, 29, 30, 31, 32
Homework 5: assigned May 2, due Wednesday, May 14 in class.
- Chapter 3: 3, 6, 9, 10, 11, 12 (a,b,c,d,f)
- Chapter 7: 1, 2, 4, 6, 9, 10, 12, 13, 14
Homework 4: assigned April 21, due Wednesday, May 7 in class.
- Chapter 10: 1, 3, 7, 8, 10, 13, 17, 22, 24, 25
- Chapter 11: 3, 4, 5, 6, 7
Homework 3: assigned Mar. 28, due Monday April 14 in class.
- Chapter 5: 1, 2, 3, 5, 9, 11, 12, 14, 20
- Chapter 6: 1, 2, 4, 6
- Supplementary Problem 1:
When we build BDD from a Boolean expression (see slide #7 of the lecture on
March 17), we calculate the cofactors in a top-down breadth first fashion.
Build the BDD for the same function under the same variable ordering by
depth first. How many cofactors you have computed? Breadth-first and
depth-first, which one is better in building BDDs?
- Supplementary Problem 2:
Consider an internal node representing a variable v in a BDD, v has
1) the T edge goes to f_v, the cofactor of function f w.r.t. v;
2) the E edge goes to f_v', the cofactor of the same function f w.r.t. v';
3) the incoming edge from function node F.
By using the concept of complement edge, how many different functions you
can get at function node F? List all of them.
For example, if you make the incoming edge a complement edge, we have
F = (v f_v + v' f_v')' = f'
Homework 2: assigned Mar. 7, due Wednesday Mar. 19
in class. (Read the homework for more information on due date.).
Homework 1: assigned Feb. 13, due Wednesday Feb. 27
in class together with the course information sheet
Meeting Time: MW 2:00 - 3:15 pm
Meeting Place: EGR
||Dr. Gang Qu
||1417 A.V. Williams Bldg.
| Office Hours:
||MW 12:45 - 1:45 pm (or by appointment)
||Mr. Ankush Varma
| Office Hours:
||Tuesday 2:30-4:30 pm
||G.D. Hachtel and F. Somenzi, Logic
Synthesis and Verification Algorithms, Kluwer Academic Publishers
||G. De Micheli, Synthesis
and Optimization of Digital Circuits, McGraw-Hill, Inc. 1994.
||T.H. Cormen, C.E. Leiserson, and R.L. Rivest, Introduction
to Algorithms, The MIT Press and McGraw-Hill, Inc. 1994.
This course covers the theory and techniques
of synthesis and optimization of digital systems. In particular,
we will study in a sequence the theory, design, and implementation of computer-aided
design (CAD) tools used in physical design automation, logic synthesis,
architectural synthesis, and system-level synthesis. This semester we focus
on logic synthesis and optimization. The core topics include: graph terminologies
and problems, fundamental algorithms, boolean algebra, logic-level synthesis
and optimization techniques for 1) two-level circuits, 2) multi-level circuits,
and 3) sequential circuits. On completion of this course, students should
understand the essential logic synthesis algorithms and tools, be able
to reason about problems in logic synthesis in general and be capable of
reading critically the recent literature.
Questions and Comments: firstname.lastname@example.org