Blatt10

Page 1

Professur für Rechnerarchitektur
Prof. Dr. Armin Biere
Dr. Mathias Fleury
Freiburg, 3. Juli 2026
Technische Informatik

Übungsblatt 10 (v0)

Vorgeschlagenes Lesethema der Woche: Treiber Verification von Microsoft https://web.eecs.umich.edu/~weimerw/2025-481F/readings/slam.pdf

Bonusblatt: Die Lehrevaluation läuft noch bis Sonntag 12. Juli an. Füllen Sie diese aus (siehe das optionale Übungsblatt).

Aufgabe 1 (KI/Pflicht Punkte)

Bitte ankreuzen welches von beiden Punkte passt:

□ Ich habe die Aufgaben selbst versucht zu lösen und möchte ein Korrektur

  • a) mir ist bewusst, dass signifikante Bearbeitung reicht zum Bestehen des Blatts
  • b) mir ist bewusst, dass ich vielleicht trotzdem Vorrechnung muss (ohne meine Notizen!)

□ Ich habe irgendwann die KI gefragt und einfach abgeschrieben. In diesem Fall:

  • a) muss ich alle Aufgaben abgeben, das reicht zum Bestehen dieses Blatts
  • b) mir ist bewusst, dass ich keine Korrektur bekommen werde
  • c) mir ist bewusst, dass ich vielleicht trotzdem Vorrechnung muss (ohne meine Notizen!)

Die Bewertung passiert nur wenn diese Aufgabe beantwortet wurde.

Aufgabe 2 (2 + 2 + 2 Punkte)

Betrachten Sie den Mealy-Automaten , der durch folgende Zustandstafel definiert ist:

Page 2

state next state
0 0
1 0
0 1
1 1
0 0
1 0
0 1
1 1
0 0
1 0
0 0
1 0

Der Startzustand des Mealy-Automaten sei .

Konstruieren Sie ausgehend von diesem Mealy-Automaten ein möglichst kleines Schaltwerk mit dem gleichen sequentiellen Verhalten. Gehen Sie dazu wie folgt vor:

a)

Zeichnen Sie für den oben definierten Mealy-Automaten das entsprechende Zustandsdiagramm.

b)

Prüfen Sie das Zustandsdiagramm auf äquivalente Zustände und fassen Sie diese zusammen. Verwenden Sie dazu folgendes, in der Vorlesung vorgestelltes Verfahren:

  1. Wenn zwei Zustände bei der gleichen Eingabe gleiche Ausgaben erzeugen und den gleichen Folgezustand annehmen, so sind sie äquivalent.
  2. Wenn zwei Zustände bei der gleichen Eingabe gleiche Ausgaben erzeugen und äquivalente Folgezustände annehmen, so sind sie auch äquivalent. Wiederholen Sie diesen Schritt, bis es keine weiteren Äquivalenzen mehr gibt.

Geben Sie die von Ihnen erkannten Äquivalenzen an und markieren Sie sie in dem Zustandsdiagramm aus a). Zeichnen Sie ein reduziertes Zustandsdiagramm, in dem die äquivalenten Zustände zusammengefasst wurden.

c)

Konstruieren Sie aus dem reduzierten Zustandsdiagramm ein Schaltwerk, das möglichst wenig Flip-Flops benötigt. Geben Sie außerdem die Übergangstabelle an, die sich aus der Wahl Ihrer Zustandskodierung ergibt. Vergessen Sie nicht, den Startzustand der Flip-Flops anzugeben.

Hinweis: Wie in der Vorlesung erwähnt, hängen die Kosten des Schaltkreises von der gewählten Zustandskodierung ab. Wenn in Ihrer Lösung die Anzahl der Flip-Flops addiert mit der Anzahl der Gatter (echt) weniger als 8 ergibt, erhalten Sie die Differenz als Bonuspunkte, wobei die Gatter in enthalten sein müssen.

Aufgabe 3 (1 + 2 + 2 Punkte)

Gegeben sei der Mealy-Automat in Abb. 1, mit:

, , und . und sind über das Zustandsdiagramm in Abb. 1 gegeben.

Page 3

(Abbildung 1: Mealy-Automat mit Zuständen und beschrifteten Übergängen.)

a)

Welche Ausgabefolge erhält man durch die Eingabe von ? In welchem Zustand befindet sich der Automat am Ende?

Hinweis: Die Eingabe wird von links nach rechts eingelesen.

b)

Erstellen Sie die Zustands- und Ausgabetafel für mit Einträgen für den aktuellen Zustand , den Eingabewert , den Folgezustand und die zugehörige Ausgabe .

c)

Ein Zustand sei mit Hilfe von Booleschen Zustandsvariablen und codiert: . Für die einzelnen Zustände von sei die folgende Codierung gewählt:

Geben Sie eine Boolesche Funktion , für die Ausgabe des Automaten an ( sei hierbei wieder der Eingabewert). Erläutern Sie Ihr Vorgehen.

Aufgabe 4 (2 + 2 + 2 + 1 Punkte)

Die Funktion sei durch ihre ON-Menge gegeben:

a)

Bestimmen Sie durch Anwendung des Quine-McCluskey-Algorithmus die Primimplikantenmenge von . Geben Sie alle Zwischenschritte, d.h. alle Mengen und an.

Für jeden Schritt des Algorithmus geben Sie an:

Wenn die jeweiligen leer sind, können diese weggelassen werden im Gegensatz zu den . In der Vorlesung wurde immer direkt angegeben.

Page 4

Hinweis: Sie dürfen in dieser Aufgabe die abkürzende Schreibweise für Monome verwenden (z.B. statt "01-1" für ).

Hinweis 2: Eigentlich hatten wir nicht vor, mehr als einen Schritt von Quine-McCluskey zu verlangen. Aber nach den Übungen von letzter Woche ist klar, dass zu viele nicht verstanden haben, was zusammengeführt werden kann oder nicht. Also kommt jetzt eine ganze Übung.

b)

Generieren Sie die Karnaugh Map von der Funktion, berechnen Sie die Primimplikanten, und vergleichen Sie das Resultat.

c)

Bestimmen Sie die Kosten (, ) (gemäß der Vorlesung)

i) des vollständigen Polynoms (besteht aus allen Mintermen der Funktion) und
ii) des reduzierten Polynoms (besteht aus allen Primimplikanten der Funktion).

d)

Ist es mit dem Quine-McCluskey-Algorithmus möglich, einen 64-bit Addierer zu optimieren? Und mit KV?

Abgabe: 10. Juli 2026, 1600