Formale Verifikation
Formale Verifikation
Simulation und formale Verifikation
Werkzeuge der formalen Verifikation
Equivalence-Checking: Problemstellung
Erfüllbarkeitsproblem(Satisfiability,SAT)
SAT1-Problem
SAT-Equivalence-Checker
Graphenisomorphie
Binary Decision Diagrams (BDDs)
Binärer Entscheidungsbaum: Beispiel
Zusammenfassen identischer Teilbäume
Entfernen überflüssiger Knoten
Abhängigkeit der Knotenanzahl von der Entwicklungsreihenfolge
Vorteile der BDDs
Beispiel:ALU(SN74181)
Model-Checking
Symbolic Model Checking
Zustandsmengen
Temporale Logik
Elemente von CTL
CTL-Syntax
AX und EX
AF and EF
AG und EG
Beispiel: Modulo-3-Zähler
Startseite
Hinweis
: Da Javascript ausgeschaltet ist, sind die Grafiken nicht animiert.
Darstellung von Zustandsmengen
● Ausgangspunkt: Zustandsdiagramm einer sequentiellen Schaltung
00
01
10
11
0/1
1/0
1/0
1/0
0/0
0/0
1/0
● Boolesche Ausdrücke (charakteristische Funktionen)
charakterisieren Mengen von Zuständen
z
1
z
2
● Beispiel: zwei Zustandsvariablen z
1
, z
2
●
z
1
+ z
2
charakterisiert die Menge {01, 10, 11}
z
2
●
z
2
charakterisiert die Menge {00, 10}