Binary Decision Diagram Technology (Wintersemester 2005/2006)
Prof. Dr. Christoph Meinel
- Semesterwochenstunden: 4
- ECTS: 6
- Einschreibefrist: 01.11.2005
- Belegungsart: Wahlpflichtmodul
- IT-Systems Engineering MA
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.
Prerequisites: Basic knowledge in computer science, programming in C, data structures and algorithms.
- Textbook: Ch. Meinel, OBDD Fundamentals and applications, 1998.
- Other Resources:
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.
- 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 )
Mo 15:15 - 16.45 HPI A-1.1 Di 13:30 - 15:00 HPI A-1.1