Effiziente Erfüllbarkeitsalgorithmen für die Generierung von Testmustern

Im Rahmen des Projektes wird untersucht, wie SAT-Algorithmen in der automatischen Testmustergenerierung eingesetzt werden können.

Kontakt: Prof. Dr. Rolf Drechsler

Während Schaltungen noch bis vor einigen Jahren vornehmlich in Rechenanlagen Verwendung fanden, werden sie zunehmend ein Teil unserer täglichen Umgebung und finden in vielen sicherheitskritischen Bereichen Anwendung. Exemplarisch seien hier medizinische Apparaturen und die Automobilindustrie genannt. Schon heute entstehen z.B. in dem zuletzt genannten Bereich bis zu 40% der Kosten durch die Elektronik. Hinzu kommt, dass hier immer mehr "kritische" Komponenten, wie Bremsen und Lenkung, elektronisch unterstützt bzw. gesteuert werden. Daher werden immer höhere Anforderungen an die Verfahren gestellt, die die Korrektheit dieser Schaltungen und Systeme gewährleisten sollen. In den vergangenen Jahren wurden große Fortschritte erzielt, doch durch die immer höhere Komplexität der Systeme und den Einsatz neuer Technologien müssen auch die Werkzeuge weiterentwickelt werden, die die Qualität sicher stellen. Ein wesentlicher Aspekt bei der Erstellung von Schaltungen und Systemen ist der Test. Die durch den Test entstehenden Kosten betragen bis zu 50% der Gesamtkosten der Fertigung. Eine grundlegende Methode zum Testen ist die Generierung von Testmustern ausgehend von einem System und einem betrachteten Fehlermodell. Im Rahmen des Projektes sollen Verfahren zur automatischen Testmustergenerierung (ATPG=Automatic Test Pattern Generation) basierend auf Boolescher Erfüllbarkeit (SAT=Satisfiability) untersucht werden.