Blatt08

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

Übungsblatt 8

Vorgeschlagenes Lesethema der Woche: Chips die programmiert werden können https://semiwiki.com/semiconductor-manufacturers/intel/289872-inside-a-counterfeit-8086-processor/

Achtung 1: Für KV werden Sie für die Klausur 4 Buntstifte brauchen (damit es lesbar ist).

Bitte ankreuzen welches von beiden Punkte passt:

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

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

Die Bewertung passiert nur wenn diese Aufgabe beantwortet wurde.

Leftovers:

Sei für eine boolesche Funktion die folgende Primimplikantentafel für die Minterme und die Primimplikanten bereits ermittelt worden:

Reduzieren Sie die Primimplikantentafel so weit wie möglich, geben Sie dabei die einzelnen verwendeten Reduktionsregeln an. Wenden Sie dann die Methode von Petrick an, um das aus der gegebenen Primimplikantentafel resultierende Minimalpolynom zu bestimmen. Gehen Sie dabei davon aus, dass alle Primimplikanten die gleichen Kosten haben.

Gegeben sei folgender Schaltkreis in Abb. 1.

(Abbildung 1: Schaltkreis mit Eingängen und Gattern bis .)

Geben Sie zu jedem Gatterausgang einen Booleschen Ausdruck an, der die berechnete Funktion repräsentiert.

Geben Sie die Länge des längsten Pfades in diesem Schaltkreis an.

Sei für eine Boolesche Funktion die folgende Primimplikantentafel für die Minterme und die Primimplikanten bereits ermittelt worden:¹

¹Auf die vorliegende Primimplikantentafel wurden bereits einige Reduktionsschritte angewendet, wovon Sie sich aber nicht weiter stören lassen sollten.

Für die Kosten der Primimplikanten gilt: .

Reduzieren Sie die Primimplikantentafel soweit wie möglich. Geben Sie dabei die einzelnen verwendeten Reduktionsregeln an (Name oder Nummer wie in der Vorlesung). Geben Sie an, aus welchen Primimplikanten das Minimalpolynom besteht. Falls notwendig, wenden Sie dazu die Methode von Petrick an.

Hinweis: Zur Wahrung der Übersichtlichkeit ist es ratsam, mehrere Primimplikantentafeln zur Darstellung der Reduktionen zu verwenden.

Gegeben sei die Boolesche Funktion mit

Geben Sie die ON-Menge zu an. Verwenden Sie anschließend das Verfahren von Quine-McCluskey, um alle Primimplikanten zu berechnen. Bestimmen Sie zum Schluss mithilfe der Primimplikantentafel das Minimalpolynom.

Leiten Sie nun das Minimalpolynom zu für her. Erläutern Sie Ihre Vorgehensweise und geben Sie die Anzahl der Primimplikanten im Minimalpolynom an.

Sie wollen das Minimalpolynom realisieren und erkennen, dass sowohl die Kosten für eine PLA als auch die Kosten für eine direkte Schaltkreisübersetzung exponentiell mit anwächst. Sie wollen jedoch eine kostengünstigere Lösung. Sei für eine alternative Definition für . Leiten Sie die Funktion für mithilfe einer Fallunterscheidung her.

Skizzieren Sie auf Basis von Aufgabenteil c) einen Schaltkreis für für mit möglichst geringer Tiefe.

Hinweis: Überlegen Sie sich, wie Sie wählen müssen, um eine möglichst geringe Tiefe zu erreichen.

Benutzen Sie Ihren Schaltkreis aus Aufgabenteil d), um sich einen Schaltkreis für zu überlegen, der ebenfalls eine möglichst geringe Tiefe hat. Dabei sei , mit . Geben Sie in Abhängigkeit von die Kosten und Tiefe Ihres Schaltkreises an. In diesem Aufgabenteil ist keine Skizzierung des Schaltkreises erforderlich.

Addieren Sie die folgenden Paare von 6-Bit Zweierkomplementzahlen mit der in der Vorlesung gezeigten Methode. Ist das Ergebnis nicht als 6-Bit Zweierkomplementzahl darstellbar, so geben Sie dies explizit an und begründen Sie.

und

und

und

Abgabe: 26. Juni 2026, 1600