1 Friedrich-Alexander-Universität Erlangen-Nürnberg Christoph Rager25.07.2006 Modellbasierte...

Friedrich-Alexander-Universität Erlangen-NürnbergChristoph Rager 25.07.2006 1

Modellbasierte Zuverlässigkeitsanalyse

(Hauptseminar 1: Qualitäts- und Zuverlässigkeitsmangagement)

Christoph Rager

Überblick

Zuverlässigkeit Fehlerbaumanalyse (FTA)

Aufbau Auswertung Grenzen

Binary Desicion Diagram (BDD) Definition und Eigenschaften OBDD ROBDD Reduktion Konstruktion Auswertung Bewertung

Bestimmung Zuverlässigkeit eines Systems durch Vorhersage des zukünftigen Verhaltens

Zuverlässigkeitsanalysen: Simulationen analytische Methoden Modell des realen Systems als Basis

analytische Verfahren: mathematische Methoden als Grundlage z.B. Fehlerbaumanalyse, BDD

Zuverlässigkeitsfunktion:R(t) = P{t<T}

Ausfallfunktion: F(t) = 1 - R(t)

FTA ist Verfahren für Zuverlässigkeitsanalyse

Fehlerbaum (FT: fault tree): strukturiertes Logikdiagramm Basisereignisse (BE) Top- Ereignis (TE) Konstruktion:

- Top- Down- Verfahren- zu jedem TE eigener FT

Analyse: qualitativ:

- Bestimmung der minimal cutsets (MCS)- Sortierung der MCS

quantitativ:- Berechnung der Eintrittswahrscheinlichkeit des TE

Bestimmung MCS mit Hilfe Boolescher Algebra

TE = E1 . E2

E1 = A + E3

E3 = B + C

E2 = C + E4

E4 = A . B+

Vereinfachung FT durch MCS

Top- Down- Verfahren: Terme nacheinander einsetzen nach TE auflösen

C A . B

TE = C + A . B

Vereinfachung FT durch MCS

Top- Down- Verfahren: Terme nacheinander einsetzen nach TE auflösen

C A . B

TE = C + A . B

+beide Bäume besitzen die selben MCS!

Durchführung FTA mit zunehmender Größe des FT schwieriger

Probleme: Rechenzeit steigt exponentiell mit Anzahl der Knoten bei Bestimmung MCS:

- Abbruchfehler

bei Berechnung Eintrittswahrscheinlichkeit TE:- kein effizienter Algorithmus- Schätzung selten eintretender Ereignisse

Durchführung FTA mit zunehmender Größe des FT schwieriger

Probleme: Rechenzeit steigt exponentiell mit Anzahl der Knoten bei Bestimmung MCS:

- Abbruchfehler

bei Berechnung Eintrittswahrscheinlichkeit TE:- kein effizienter Algorithmus- Schätzung selten eintretender Ereignisse

Lösungsmöglichkeit durch neuen Algorithmus, basierend auf Binary

Decision Diagrams (BDD)

BDD ist gerichteter, azyklischer Graph mit genau einer Wurzel

Eigenschaften: genau zwei Knoten ohne ausgehende Kanten jeder andere Knoten hat zwei ausgehende Kanten jeder Knoten mit Variable xi markiert

Darstellung: 1- Kante als durchgezogene Linie 0- Kante gestrichelt Senken als Rechteck Knoten als Kreise

OBDD hält eine vorgegebene Variablenordnung von Wurzel zur Senke ein

Ordered BDD Variablen in jedem Pfad in selber Reihenfolge Darstellung von Schaltfunktionen mit Hilfe Shannon-

Zerlegung:f = xi

. fxi + xi

fxi: positiver Cofaktor (xi= 1)

fxi: negativer Cofaktor (xi= 0)

OBDD für gegebene Schaltfunktionen nicht eindeutig bestimmt

Forderung an Darstellung: minimal Redundanzfreiheit

Arten von Redundanzen: 0- und 1- Nachfolgeknoten eines Knotens v identisch bestimme Teilgraphen treten mehrfach auf

Anwendung von Reduktionsregeln ROBBD (Reduced Ordered BDD) als Ergebnis

kanonischen Darstellung von Schaltfunktionen durch zwei Reduktionsregeln

Eliminationsregel (Deletion Rule): 0- und 1- Nachfolgeknoten eines Knotens v identisch Vorgehen:

- Knoten v eliminieren- in Knoten v eingehenden Kanten auf Nachfolgeknoten umleiten

Eliminationsregel (Deletion Rule): 0- und 1- Nachfolgeknoten eines Knotens v identisch Vorgehen:

- Knoten v eliminieren- in Knoten v eingehenden Kanten auf Nachfolgeknoten umleiten

Isomorphieregel (Merging Rule): bestimme Teilgraphen treten mehrfach auf:

- Knoten u und v mit gleicher Variable markiert- 1- bzw. 0- Kante von u und v haben jeweils gleichen Nachfolger

Vorgehen:- Knoten u oder v eliminieren- in diesen Knoten eingehenden Kanten auf verbleibenden umlenken

Isomorphieregel (Merging Rule): bestimme Teilgraphen treten mehrfach auf:

- Knoten u und v mit gleicher Variable markiert- 1- bzw. 0- Kante von u und v haben jeweils gleichen Nachfolger

Vorgehen:- Knoten u oder v eliminieren- in diesen Knoten eingehenden Kanten auf verbleibenden umlenken

Reduktionsrichtung von unten nach oben

Anwendung Eliminationsregel Anwendung Isomorphieregel

Konstruktion von BDD auf zwei unterschiedlichen Wegen

Schaltfunktion als Ausgangspunkt: schrittweise Erstellung BDD mit Hilfe der Shannon-

Zerlegung Äquivalenztest parallel dazu keine Reduktion erforderlich

FT als Ausgangspunkt: vollständigen Entscheidungsbaum aufstellen:

- TE als Anfangspunkt- logische Verknüpfung der Ereignisse durch boolesche Algebra

Reduktion

Konstruktion BDD zum TE = AB + C (Variablenordnung: A < B < C)

C A . B

Schritt 1: AB

und und

Schritt 1: AB

und und

1 . X = X

0 . X = 0

Schritt 1: AB Schritt 2: AB + C

1 + X = 1

0 + X = X

Schritt 1: AB Schritt 2: AB + C Schritt 3: Reduktion

jeder Pfad vom Wurzelknoten zur Senke 1 löst das TE aus

Auswertung FT effizient mit Hilfe BDD

Bestimmung der minimalen Lösungen: jeder Pfad von Wurzel zur Senke 1 ist Lösung Lösungen nicht minimal minimale Lösung mit Hilfe Algorithmus (Rauzy)

Ermittlung der Eintrittswahrscheinlichkeit des TE: exakte Resultate (kein Abbruch) mit Hilfe der Shannon- Zerlegung:

p (f) = p (x = 1) * p (f {x = 1} ) + p (x = 0) * p (f {x = 0} )

Bewertung des BDD- Ansatzes

Vorteile ggü. FTA: exakte Berechnungen

- keine Abbruchfehler- keine Schätzungen

Bewältigung großer Anzahl von cutsets schnellere Berechnung Softwarepakete erhältlich (z.B. Aralia...)

Nachteile: Verlagerung Komplexität auf Erstellung Größe BDD abhängig von Variablenordnung

Anwendung: symbolische Verifizierung von Digitalschaltkreisen Modellierung technischer Systeme (Kraftwerke, Flugzeuge...)

Quellenangabe

Buchacker, K.: Definition und Auswertung erweiterter Fehlerbäume für die Zuverlässigkeitsanalyse technischer Systeme

Fault Tree Handbook with Aerospace Applications (NASA) Rauzy, A.: New algorithms for fault trees analysis Meinel, C., Theobald, T.: Algorithmen und Datenstrukturen

im VLSI- Design http://www.wikipedia.de

Vielen Dank für die Aufmerksamkeit!

Backup

Berechnung der Wahrscheinlichkeit des TE bei „oder“- Verknüpfung

P(Q) = P(A) + P(B) – P(A∩B)

Näherung bei kleinen Wahrscheinlichkeiten: P(A), P(B) < 10-1

P(A∩B) klein gegenüber P(A) + P(B)

P(Q) = P(A) + P(B)

Reduktion eines OBDD (1)

id: 4id: 2

id: 5id: 6

id: 4id: 2

id: 5id: 6

id: 4id: 2

id: 5id: 6

id: 4id: 2

id: 5id: 6

id: 4id: 2

id: 5id: 6

Konstruktion BBD mit Schaltfunktion als Ausgangspunkt

Geg.: f(x1, x2, x3) = x1(x2 + x3)

Unterfunktionen von x1 berechnen:

fx1 = x2 + x3

fx1 = 0

Geg.: f(x1, x2, x3) = x1(x2 + x3)

fx1 = x2 + x3

fx1 = 0

fx1x2 = x3

fx1x2 = 1 + x3 = 1

Geg.: f(x1, x2, x3) = x1(x2 + x3)

fx1 = x2 + x3

fx1 = 0

fx1x2 = x3

fx1x2 = 1 + x3 = 1

fx1x2x3 = 1

fx1x2x3 = 0

Operationen auf BDD (exemplarisch)

binäre Operationen: Verknüpfung mehrerer BDD mit boolescher Algebra Voraussetzung:

- gleiche Variablenordnung der Funktionen

Anwendung:- Erstellung großer BDD- einfache Veränderung bestehender BDD

Algorithmen: Äquivalenztest:

- Test, ob zwei gegebene OBBD die gleiche Fkt. Darstellen

Auswertung:- Durchlauf des OBDD von der Wurzel zur Senke

Speicherverwaltung

Situation: große OBBD aus Vielzahl von kleinen OBBD aufgebaut kleine OBDD nur eine vorübergehende Zeit von Bedeutung nicht benötigte OBBD sollen entfernt werden

Problematik beim sofortigen Löschen: „tote“ Knoten evtl. für spätere Berechnungen noch benötigt Knoten kann nur gelöscht werden, wenn zugleich alle seine

Vorgänger gelöscht werden Strategie: Garbage Collection

Speicherplatz eines „toten“ Knotens wird nicht sofort freigegeben

warten bis Umstrukturierungsaufwand in gutem Verhältnis zum Gewinn an Speicherplatz

1 Friedrich-Alexander-Universität Erlangen-Nürnberg Christoph Rager25.07.2006 Modellbasierte...

Documents

Zuverlässigkeitsanalyse einer elektrischen Architektur … die Richtlinie EASACS-25.1309 und die zugehörige Leitlinie AMC-25.1309 wurde ein konsisten- ... Design . Freeze. ... Teil

Anderson-Lokalisierung - Hauptseminar: Wechselwirkende ... · Anderson-Lokalisierung Hauptseminar: Wechselwirkende Quantengase - WS 2009/2010 David Peter 26. Januar 2010

Modellbasierte Regelung der Hochleistungstriebwerke von ...Modellbasierte Regelung der Hochleistungstriebwerke von Hyperschallflugzeugen Andreas Kreiner Vollständiger Abdruck der

Kunst- und Kulturgeschichte fileSWS LP A h KuKMA-01-FE1 Feldstudien 1 1 Hauptseminar + 1 interdisziplinäres Kolloquium 4 10 501 Hauptseminar KuKMA-02-FA 4 Fallstudien 1 Hauptseminar

Modellbasierte Zuverlässigkeitsanalyse

Modellbasierte Software-Entwicklung eingebetteter Systeme

Modulhandbuch - Startseite TU Ilmenau · Praktikum Mikrofabrikation 0 0 4 SL 5 Hauptseminar FP Hauptseminar Elektronik-Technologie 0 2 0 PL 4 Hauptseminar Mikro- und Festkörperelektronik

Hauptseminar Displacement-Mapping mit Geometry-Shadernw3-o.cs.hm.edu/~nischwit/Hauptseminar/2009/Seminararbeit_michel… · Displacement-Mapping beschreibt im allgemeinen eine Technik,

Hauptseminar – Messmethoden der experimentellen

Ludwig-Maximilians-Universität München Hauptseminar: Soziophonetik

Seminar: Modellbasierte Entwicklung in der Fahrzeuginformatik Presentations · 2013-06-24 · Sandro Schulze Seminar SS 2013 Modellbasierte Entwicklung in der Fahrzeuginformatik 31

Zuverlässigkeitsanalyse umfelderfassender Sensorik

Nichtlineare modellbasierte Pr.diktive Regelung auf Basis ... · Lehrstuhl fur Elektrische Antriebssysteme¨ Technische Universität M ünchen Nichtlineare modellbasierte prädiktive

Modellbasierte Planung zur Unterstützung der

Dünnschicht- und Tandemsolarzellen Hauptseminar Physikalische Aspekte der Solarenergienutzung Hauptseminar Physikalische Aspekte der Solarenergienutzung

MDA Praktisch Modellbasierte Java Entwicklung Markus Völter voelter@acm voelter.de

Hauptseminar: „Der Urknall und seine Teilchen“

Experimentelle und modellbasierte Untersuchung von ...Experimentelle und modellbasierte Untersuchung von Stehwellenantrieben Von der Fakultät für Maschinenbau der Gottfried Wilhelm

Modellbasierte Softwareerstellung (Model-driven Architecture, MDA)

Modellbasierte Entwicklung und Test von Regelungssytemen › content › dam › mathworks › mathwork… · Institute of Flight System Dynamics Modellbasierte Entwicklung und Test