Blatt09

Page 1

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

Übungsblatt 9

Vorgeschlagenes Lesethema der Woche: Addierer von Zahlen mit Nachkommastellen in 8087 https://www.righto.com/2026/06/intel-8087-adder-reverse-engineered.html

Bonusblatt: Die Lehrevaluation fängt am Montag 29. 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 Punkte)

Sei ein Addiererschaltkreis für zwei -Bit-Binärzahlen.

a)

Konstruieren Sie einen kombinierten Addierer/Subtrahierer für -Bit-Zweierkomplementzahlen basierend auf der Bibliothek . Die Operation soll über ein Inputsignal sub gewählt werden können: Wenn sub , soll eine Subtraktion durchgeführt werden, wenn sub , soll eine Addition durchgeführt werden.

b)

Erweitern Sie Ihren Schaltkreis um ein Überlaufsignal overflow, so dass overflow genau dann, wenn das Ergebnis der Addition/Subtraktion nicht als -Bit-Zweierkomplementzahl darstellbar ist.

Page 2

Aufgabe 3 (3 + 3 Bonus Punkte)

Ein -Bit Inkrementer berechnet die Funktion , mit . In der Vorlesung wurde vorgestellt, wie man einen -Bit Inkrementer nach dem beim -Bit Carry-Ripple-Addierer verwendeten Schema konstruieren kann.

a)

Konstruieren Sie nun einen schnelleren -Bit Inkrementer auf Basis des in der Vorlesung vorgestellten -Bit Conditional-Sum-Addierers. Geben Sie hierzu die Basiszelle und den rekursiven Aufbau von für an. sei hierbei eine Zweierpotenz, d.h. für .

b)

Geben Sie die Tiefe Ihres -Bit Inkrementers an, und beweisen Sie Ihre Aussage. Geben Sie die Kosten Ihres -Bit Inkrementers nur asymptotisch an, und begründen Sie lediglich kurz.

Aufgabe 4 (8 + 2 Punkte)

Für eine Funktion mit der folgenden OFF-Menge (Reihenfolge ):

a)

Nutzen Sie KV, um die Primimplikanten zu finden. Listen Sie diese auf.

b)

Nutzen Sie das quienny von Prof. Biere, um die Primimplikanten zu finden. Um das Programm zu installieren, müssen Sie git clone https://github.com/arminbiere/quienny.git ausführen und dann ./configure && make -j. Das Programm nimmt als einziges Argument eine Datei mit allen Elementen der ON-Menge (ein Eintrag pro Zeile).

c)

Nutzen Sie dann eine Primimplikantentabelle, um die wesentlichen Primimplikanten zu finden. Nutzen Sie die Reihenfolge, die ./quienny8 ausgibt! Danach nutzen Sie Petrick's Methode, um das zyklische Überdeckungsproblem nach einem Produkt von Summen umzuwandeln.

Wichtig: Wir erwarten nur, dass Sie das PIT in ein Produkt von Summen umwandeln, aber nicht, dass Sie diese Formel ausrechnen. Dies ergibt vereinfacht, dass wir haben.

Abgabe: 3. Juli 2026, 1600