FB 08 Informatik
Lehrstuhl für "Efficient Computing and Storage"
Prof. Dr.-Ing. André Brinkmann
Fabian Kreppel
Technische Informatik - WS 2024/25
4. Übungsblatt
(Abgabe: 09:00 Uhr, 25. November 2024)
Aufgabe 1: (20 Punkte)
Wir betrachten in dieser Aufgabe Überdeckungsprobleme, bei denen in jeder von m Spal-
ten mindestens eine Eins und in jeder Zeile höchstens zwei Einsen vorkommen.
(a) Geben Sie eine Überdeckungsmatrix für dieses spezielle Überdeckungsproblem an,
die reduzibel und unverkürzbar ist.
(b) Der Greedy-Algorithmus (greedy = gierig) zur approximativen Lösung von Über-
deckungsproblemen verfährt wie folgt: „In jedem Schritt wird eine Zeile ausgewählt,
die möglichst viele bis dahin noch nicht überdeckte Spalten überdeckt. Der Algorith-
mus terminiert, wenn alle Spalten überdeckt sind.“ Zeigen Sie anhand eines Beispiels,
dass der Greedy-Algorithmus auch für dieses spezielle Überdeckungsproblem in der
Regel keine minimale Zeilenmenge liefert.
Aufgabe 2: (20 Punkte)
Die Boolesche Funktion f (x1 , x2 , x3 ) = x1 x3 + x2 wird durch das gezeigte Schaltnetz rea-
lisiert. Mittels schaltungsabhängiger Fehlerdiagnose bestimmen Sie hierfür eine minimale
Testmenge unter der Fehler-Annahme, dass höchstens ein Draht gerissen ist, dadurch aber
eine 0 oder 1-Verklemmung entstehen kann. Zeigen Sie die Ausfalltafeln, Ausfallmatrizen
und Fehlermatrizen, sowie den gesamten Testvektor.
Bemerkung: Betrachten Sie alle möglichen Fehler von genau einer 0- oder 1-Verklemmungen.
1
Aufgabe 3: (30 Punkte)
Sei f : B 4 → B durch die Tabelle gegeben:
x1 x2 x3 x4 f
0 0 0 0 0
0 0 0 1 1
0 0 1 0 0
0 0 1 1 1
0 1 0 0 0
0 1 0 1 1
0 1 1 0 0
0 1 1 1 1
1 0 0 0 0
1 0 0 1 1
1 0 1 0 0
1 0 1 1 0
1 1 0 0 1
1 1 0 1 1
1 1 1 0 1
1 1 1 1 1
(a) Bestimmen Sie zu f eine disjunktive Form d mit minimalen Kosten. Skizzieren Sie
das entsprechende Schaltnetz. (10 Punkte)
(b) Bestimmen Sie einen statischen und einen dynamischen Funktionshasard von f . (10
Punkte)
(c) Ist eine zweistufige Schaltung, welche aufgrund der unter (a) vorgenommen Optimie-
rung gewonnen wurde, frei von Schaltungshasards? Warum? (10 Punkte)
Aufgabe 4: (30 Punkte)
Sei O = 0, 1, 2, ..., 7. Jede Zahl i ∈ O kann dann durch eine dreistellige Dualzahl b(i) =
x1 x2 x3 dargestellt werden. Sei SO ein Schaltnetz, das durch folgende Schaltfunktion fO :
B3 → B3 beschreibbar ist:
fO (b(i)) = b((i + 5) mod 8)
.
(a) Stellen Sie die Wertetabelle von fO auf. Vereinfachen Sie mit Hilfe eines Karnaugh-
Diagramms die Booleschen Funktionen für die Ausgabe von fO . (10 Punkte),
(b) Entwerfen Sie SO mit Logisim und speichern Sie die *.circ und machen Sie ein Bild
von der Schaltung. Benennen Sie die Inputs x1, x2 und x3, und die Outputs f 1, f 2,
f 3. (10 Punkte)
(c) Loggen Sie den Output Ihrer Schaltung mit allen möglichen Werten von i ∈ O und
plotten Sie mit dem Skript waveform_octal.py die Waveform. (10 Punkte)
