Institut für Rechnerentwurf und Fehlertoleranz

Prof. Dr. Th. Ungerer
Felix Holderied
8. Juli 1997


Blatt5

5. Übungsblatt zur Vorlesung Rechnerstrukturen

Die Besprechung des Übungsblattes findet am Dienstag den 8. Juli 1997 statt. Die Musterlösung wird im Anschluß an die Übung auf unserem Server http://goethe.ira.uka.de/ zu finden sein. Bei Fragen zu dieser Übung wenden Sie sich bitte telefonisch (608-3961), persönlich (Informatikgebäude am Schloß, Raum 269) oder per Email (felix@ira.uka.de) an mich.

1. Aufgabe (Aufwand von Fehlerkorrekturcodes)

Im Skript (Kap.6.4.1.2) finden Sie folgende Ungleichung: 
 k             
2  >= m + k + 1
k ist die Anzahl der Korrekturbits, m die Anzahl der Datenbits. Es handelt sich um eine notwendige Bedingung für einen Code zur Korrektur eines Bitfehlers. Verallgemeinern sie diese Ungleichung auf Codes zur Korrektur von e Fehlern. Betrachten Sie dazu die Anzahl der fehlerhaften Codewörter, die auf ein fehlerfreies abgebildet werden.

2. Aufgabe (Hammingcode)

Es sei 
                   / c1 \              
    / m1 \         | c2 |              
    | m2 |         | c3 |        / s1 \
m = | m3 |    c =  | c4 |    s = | s2 |
    \ m4 /         | c5 |        \ s3 /
                   | c6 |              
                   \ c7 /
  1. Geben Sie eine binäre (7x4)-Matrix G an, so daß für das zu m gehörende Codewort c gilt: c = G m. Verwenden Sie den im Skript beschriebenen Hammingcode.
  2. Geben Sie eine binäre (3x7)-Matrix H an an, so daß s = H c und s1 + 2 s2 + 4 s3 die Fehlerstelle angibt, wenn genau ein Bit im Codevektor falsch ist bzw. s1 = s2 = s3 = 0 gilt, wenn kein Fehler aufgetreten ist.
  3. Prüfen Sie Ihr Ergebnis am Beispiel c = (1,0,0,0,1,0,1)T.

3. Aufgabe (Zuverlässigkeit)

Die beiden Systeme S1 und S2 seien durch je ein Zuverlässigkeitsblockdiagramm definiert, wobei alle mit H bezeichneten Komponenten die Funktionswahrscheinlickeit phi(H) = 1 aufweisen:


  1. Wie lauten die Systemfunktionen der Systeme S1 und S2 ?
  2. Zeigen Sie, daß eines der beiden Systeme (welches ?) stets eine größere oder gleiche Funktionswahrscheinlichkeit wie das andere aufweist (die Funktionswahrscheinlichkeiten der einzelnen Komponenten seien in beiden Systemen gleich).
  3. Wie unterscheiden sich die Funktionswahrscheinlichkeiten der Systeme, wenn jede Komponente Ki die gleiche Funktionswahrscheinlichkeit phi(Ki) = 0,9 aufweist?

4. Aufgabe (Zuverlässigkeit)

Ein System S0 = K1 AND K2 wird um die redundanten Komponenten K3 und K4 ergänzt, wobei K3 die gleiche Funktion wie K1 und K4 die gleiche Funktion wie K2 ausführt. Zur Auswahl eines der redundanten Ergebnisse sind zusätzlich Auswahleinheiten A1, A2, ... vonnöten. Die Komponenten K1, ..., K4 besitzen die Ausfallrate lambda, die Auswahleinheiten die Ausfallrate mu.
  1. Zeichnen Sie jeweils Zuverlässigkeitsblockdiagramm und Fehlerbaum der redundanten Systeme 
    S1 = ((K1 AND K2) OR (K3 AND K4)) AND A1
S2 = ((K1 OR K3) AND A1) AND ((K2 OR K4) AND A2).
  2. Zeigen Sie durch Beispiele, daß durch Wahl der Parameter lambda und mu phi(S1,1000h) sowohl kleiner als auch größer sein kann als phi(S2,1000h).
  3. Welcher Bedingung müssen mu und die Zeit T genügen, damit für eine vorgegebene Ausfallrate lambda beide Systeme die gleiche Funktionswahrscheinlichkeit besitzen, d.h. 
     phi(S1, T) = phi(S2, T)?
  4. Welches System ist für lambda = 8*10^(-6)/h und mu = 1*10^(-6)/h während der Betriebsdauer 0 <= t <= 5 10^5 h vorzuziehen?

5. Aufgabe (Zuverlässigkeit)

Gegeben sei ein 2-von-3-System, dessen Komponenten zufallsverteilt mit gleicher Rate ausfallen. Die Überlebenswahrscheinlichkeit einer Komponente wird durch die Formel 
        - lambda t             
R(t) = e           , lambda > 0
beschrieben.
  1. Geben Sie die Systemfunktion an.
  2. Wie groß ist die Ausfallrate für eine einzelne Komponente?
  3. Bestimmen Sie die Zeitintervalle, in denen das 2-von-3-System eine größere Überlebenswahrscheinlichkeit als eine einzelne Komponente aufweist.
  4. Bestimmen Sie lambda derart, daß die mittlere Lebensdauer für das gegebene 2-von-3-System 5/6 beträgt.
Felix Holderied