Institut für Rechnerentwurf und Fehlertoleranz

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


Blatt5

Musterlösung zum 5. Übungsblatt

1. Aufgabe (Aufwand von Fehlerkorrekturcodes)

Man kann die Formel durch folgenden Gedankengang herleiten:

Die Fehlerkorrektur ist eine Abbildung fehlerhafter (und fehlerfreier) Codewörter auf fehlerfreie Codewörter. Wieviele fehlerhafte Codewörter werden jeweils auf ein korrektes abgebildet? Geht man von einem korrekten Wort der Länge m+k Bit aus, so gibt es m+k Möglichkeiten für 1 Fehler. Für 2 Fehler hat man (m+k über 2) Möglichkeiten. Die Anzahl unterschiedlicher Bits zweier Wörter, hier also die Anzahl der Fehler, nennt man Hammingabstand. Die Menge aller Wörter mit einem Hammingabstand e oder weniger zu einem Wort nennt man Hammingkugel mit Radius e.

Soll also ein Code e Fehler korrigieren so liegen in der Hammingkugel mit Radius e folgende Anzahl an Woertern 

    1     das fehlerfreie Wort
    
+  m+k    Woerter mit einem Fehler

  /m+k\
+ |   |   Woerter mit zwei Fehlern
  \ 2 /

+ ....

  /m+k\
+ |   |   Woerter mit e Fehlern
  \ e /
Alle diese Woerter müssen eindeutig auf das fehlerfreie Wort abgebildet werden, sprich die Hammingkugeln dürfen sich nicht schneiden. Die Redundanz der k Korrekturbits dient nun dazu alle diese Fehlerfälle zu unterscheiden und muß daher mindestens so groß sein sein. 
       e
 k    ___  / m+k \
2  >= \    |     |
      /__  \  i  /
      i=0
Es muß noch darauf hingewiesen werden, daß die Gleichheitsbedingung nur selten auftritt. Ein "verschnittfreier" Code ist nur für wenige m und e möglich. Bei vielen Codes gibt es daher neben den korrigierbaren Wörtern auch noch welche die außerhalb aller Hammingkugeln liegen. Diese werden zwar als fehlerhaft erkannt, können aber nicht mehr eindeutig zugeordnet werden. Fehlererkennung und Korrigierbarkeit sind dann unterschiedlich.

2. Aufgabe (Hammingcode)

  1.     ( 1101 )
    | 1011 |
    | 1000 |
G = | 0111 |
    | 0100 |
    | 0010 |
    ( 0001 )

  2.     ( 1010101 )
H = | 0110011 |
    ( 0001111 )

  3.                   /1\
                  |0|
      ( 1010101 ) |0|   /1\
H c = | 0110011 | |0| = |1| -> Fehler in Bit 3 
      ( 0001111 ) |1|   \0/
                  |0|
                  \1/

3. Aufgabe (Zuverlässigkeit)

  1. S1 = (K1 K4 K7) OR (K2 K5 K8) OR (K3 K6 K9)
    S2 = (K1 OR K2 OR K3)(K4 OR K5 OR K6)(K7 OR K8 OR K9)

  2. "Ausmultiplizieren" von S2:
    S2 = (K1 K4 K7) OR (K2 K5 K8) OR (K3 K6 K9) OR (K1 K6 K9) OR ... weitere Terme.
    Folglich: S1 => S2
    Im Zuverlässigkeitsblockdiagramm sind die Wege von S2 eine Obermenge der Wege von S1.
    Also: phi(S2) = phi(S1) + phi(zusätzliche Wege) => phi(S2) >= phi(S1)

  3. phi(K1 K4 K7) = phi(K2 K5 K8) = phi(K3 K6 K9) = 0,9^3
    phi(S1) = 1 - (1 - 0,9^3)^3 = 0,980
    phi(K1 OR K2 OR K3) = phi(K4 OR K5 OR K6) = phi(K7 OR K8 OR K9)
    = 1 - (1 - 0,9)^3
    phi(S2) = (1 - (1 - 0,9)^3)^3 = 0,997
    PHI(S1 -> S2) = ( 1 - 0,980)\(1 - 0,997) = 6,66

4. Aufgabe (Zuverlässigkeit)

  1. S1 = ((K1 AND K2) OR (K3 AND K4)) AND A1
    und 
    S2 = ((K1 OR K3) AND A1) AND ((K2 OR K4) AND A2).

  2. Sei x:= e^(-lambda*T) und y:= e^(-mu*T).
    phi(S1, T) = (1 - (1 - x^2)^2) * y
    phi(S2, T) = (1 - (1 - x)^2)^2 * y^2

    lambda klein, mu groß => Ki zuverlässig, Ai unzuverlässig => phi(S1, T) > phi(S2, T)

    z.B. lambda = 10^(-6)/h, mu = 1/h =>
    phi(S1, 10^3 h) = (1 - (1 - (e^(-10^(-6)/h * 10^3 h))^2)^2) * e^(-1/h * 10^3h)
    = 0,999 996 0 * e-1000 = 1/e^1000

    phi(S2, 10^3 h) = (1 - (1 - (e^(-10^(-6)/h * 10^3 h)))^2)^2 * (e^(-1/h) * 10^3h)^2
    = 0,999 998 0 * e-2000 = 1/e^1000 * 1/e^1000

    lambda groß, mu klein => Ki unzuverlässig, Ai zuverlässig => phi(S1) < phi(S2)

    z.B. lambda = 100/h, mu = 10^(-6)/h => phi(S1, 10^3 h) = (1 - (1 - (e^(-10))^2)^2) * e^(-0,001) = 4 * 10^(-9) * 1

    phi(S2, 10^3 h) = (1 - (1 - (e^(-10))^2)^2) * (e^(-0,001))^2 = 8,2 * 10-9 * 1^2

  3. phi(S1,T) = phi(S2,T) <=> (1 - (1 - x^2)^2) * y = (1 - (1 - x)^2)^2 * y^2
    <=> 2x^2 - x^4 = (2x - x^2)^2 * y
    <=> 2 - x^2 = (2 - x)^2 * y <=> y = (2 - x^2)/((2 - x)^2) e^(-mu*T) = (2 - e(-2*lambda*T))/((2 - e^(-lambda*T))^2)
    <=> mu = (1/T)*ln ((2 - (e^(-lambda*T))^2)/(2 - e^(-2*lambda*T)))
  4. 1/(5*10^5 h) * ln (((2 - e^((-8*10^(-6)/h) * 5*10^5 h))^2)/ (2 - e^(-2*8*10^(-6)/h * 5*10^5 h)) = 1,35 * 10^(-6)/h > mu
    => mu klein genug, so daß f¸r T = 5*10^5 h gilt: phi(S2,T) > phi(S1,T). Wähle also das System S2.

5. Aufgabe (Zuverlässigkeit)

  1. S(2von3)=(K1 K2) OR (K1 K3) OR (K2 K3)
  2. z(t) = (d/dt F_L(K,t))/R(K,t) = (d/dt(1-R(K,t)))/R(K,t)
    = lambda
  3. R(K,t) < R(S(2von3),t)
    Schnittpunkte der Überlebensw'keiten finden (R:=R(K,t)):
    R = R^3 + 3*R^2*(1-R) = 3*R^2 - 2*R^3
    => R1 = 0, R2 = 1/2, R3 = 1
    R(K,t) ist zwischen 1/2 und 1 kleiner als R(S(2von3),t)
    => t1 = 0, t2 = ln(2)/lambda. Gesuchtes Intervall: (0, ln(2)/lambda).

  4. MTTF = Integral(0,infty)R(S(2von3),t) dt = 5/(6lambda) => lambda=1
Felix Holderied