Binary Decision Diagram Technology (Wintersemester 2005/2006)

Dozent:
Tutoren: Prof. Dr. Christoph Meinel

Allgemeine Information

• Semesterwochenstunden: 4
• ECTS: 6
• Benotet: Ja
• Einschreibefrist: 01.11.2005
• Lehrform:
• Belegungsart: Wahlpflichtmodul

Studiengänge

• IT-Systems Engineering MA

Beschreibung

This course covers both the theoretic aspect and the practical application of Binary decision Diagrams.

The course is divided into three parts:

• In the first part, the basic theory of BDDs is developed. Algorithms for BDD manipulation and minimization based on variable ordering are discussed. Approximation of the worst-case run-time for all algorithms is given.
• The second part of the course considers the basic data structures (directed acyclic graphs, look-up tables) and essential programming techniques (hashing, dynamic programming) used to represent and manipulate Binary Decision Diagrams. The implementation of a high performance BDD package in C/C++ is discussed, based on a case study of a state-of-the-art BDD package.
• The third part of the course is devoted to application of binary and other DDs to problems encountered in logic synthesis, verification, and testing, image processing.

Voraussetzungen

Prerequisites: Basic knowledge in computer science, programming in C, data structures and algorithms.

Literatur

Course literature:

• Textbook: Ch. Meinel, OBDD Fundamentals and applications, 1998.
• http://eccc.uni-trier.de/eccc-local/ECCC-Books/Meinel-Theobald-book/OBDD-Book.pdf
  
   
• Other Resources:
• Randal E. Bryant, Symbolic Boolean Manipulation with Ordered Binary Decision Diagrams.
• http://www.eecs.umich.edu/~valeria/teaching/eecs478_F05/reference/bryant92.pdf
  
• Henrik Andersen, An introduction to BDDs.
• http://www.itu.dk/people/hra/bdd97.ps
  
• Fabio Somenzi, Binary Decision Diagrams.
• http://overcite.lcs.mit.edu/somenzi99binary.html
  
• lecture notes and slides given by the lecturer.
• BDD package: F. Somenzi, cudd-2.4.1
• ftp://vlsi.colorado.edu/pub/cudd-2.4.1.tar.gz
  http://vlsi.colorado.edu/~fabio/CUDD/cuddIntro.html
   

Lern- und Lehrformen

Instruction Method: 50% of a class period is allocated to lectures while the remaining time will be spent on tools tutorials and exercises. The course is limeted to 15 participants.

Leistungserfassung

Grading Policy:  

• Assignments      30 %   ( are due on the date assigned by the lecturer )
• Project               30 %   ( is due on one week before the final exam )
• Final exam         40 %   ( written )

Termine

Mo 15:15 - 16.45 HPI A-1.1    Di  13:30 - 15:00 HPI A-1.1

Zurück