Blatt05

Page 1

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

Übungsblatt 5

Achtung 1: Bis auf den Schaltkreis, muss diese Abgabe mit dem Computer geschrieben worden sein. Handgeschriebene Antworten werden nicht benotet.

Achtung 2: Nächste Woche ist Pfingstpause. Da gibt es also keine Tutorate und keine Abgabe – diese ist erst in zwei Wochen. Und am 4. Juni ist Feiertag.

Vorgeschlagenes Lesethema der Woche: PLAs mit Bildern in richtigen CPUs: https://www.righto.com/2026/02/8087-instruction-decoding.html

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 (3 + 2 Punkte)

Die formale Beschreibung eines Schaltkreises über der Bibliothek STD sei gegeben durch

Page 2

wobei:

a)

Zeichnen Sie .

b)

Führen Sie für eine symbolische Simulation durch (geben Sie für jedes Gatter die an seinem Ausgang berechnete Funktion an).

Aufgabe 3 (4 Punkte)

Finden Sie eine möglichst kostengünstige CMOS-Realisierung (bzgl. Anzahl der p- und n-Kanal-Transistoren aus der Vorlesung) für ein neues Gatter, welches die folgende boolesche Funktion berechnet:

Achten Sie darauf, dass es in Ihrem Gatter keinen Kurzschluss gibt, d.h. für keine Eingangsbelegung gibt es einen leitenden Pfad von der Spannungsquelle (1) zur Masse (0). Selbstzerstörerische Gatter bekommen keine Punkte.

Hinweis 1: Die volle Punktzahl erreichen Sie für eine ordentlich gezeichnete funktionierende Lösung mit maximal 6 Transistoren.

Hinweis 2: Zum Abbilden der Transistoren kann ich nur TikZ empfehlen:

\begin{circuitikz}[transform shape, scale=1.0]
\draw (0,0) node[nmos] (nmos_a) {};
\draw (-5,-1) node[pmos] (pmos_b) {};
\path (pmos_b.S) edge node[above] {something}
      (nmos_a.D);
\end{circuitikz}

Page 3

Hinweis 3: Die Realisierung darf auch per Hand produziert werden. Es gibt einen Punkt dafür, dass die Realisierung ordentlich gezeichnet ist. Mit dem Computer produzieren erhöht die Wahrscheinlichkeit, dass Sie diesen Punkt bekommen.

Aufgabe 4 (3 Punkte)

Sei , mit , ein Schaltkreis über einer Zellbibliothek BIB und eine Eingangsbelegung, .

Dann ist eine Belegung für alle Knoten gegeben durch folgende Definition (siehe Kap. 3.1.2 Folie 12):

  • ,
  • und
  • falls mit , , dann
    .

Zeigen Sie, dass die Belegung eindeutig ist, wenn der Graph azyklisch ist. Beweisen Sie dafür die Teilaussagen in a) - c).

Hinweis: Ein formaler Beweis ist nicht zwingend notwendig. Informale, jedoch ausführliche und nachvollziehbare Begründungen sind ebenfalls ausreichend.

Hinweis: Sobald Sie eine Teilaussage bewiesen haben, sollten Sie diese in den folgenden Teilaufgaben verwenden.

a)

Jeder azyklische Graph hat mindestens eine Wurzel.

Hinweis: Beweis durch Widerspruch.

Page 4

b)

Für jeden azyklischen Graphen ist eine topologische Sortierung möglich. Eine topologische Sortierung der Knoten eines gerichteten Graphen wird definiert als eine bijektive Abbildung

mit

(d.h. jedem Knoten wird eine eindeutige Nummer zugewiesen und der Anfangsknoten jeder Kante hat eine kleinere Nummer als ihr Endknoten.)

c)

Mit einer topologischen Sortierung von ist die Belegung eindeutig.

Hinweis: Führen Sie den Beweis durch vollständige Induktion über die Anzahl von Knoten im Graphen.

Abgabe: 05. Juni 2026, 1600