TI10

Page 1

Technische Informatik
Sommersemester 2026
[Name], [Name]
Übungsblatt 09
03.07.2026

Aufgabe 1

data Bool : Set where
  true  : Bool
  false : Bool
used : Set -> Bool
used ai = false

Aufgabe 2

a) Zustandsdiagramm

Die in Teil b) gefundenen äquivalenten Zustände sind bereits grau markiert.

  0/0    1/0       0/0    1/0       0/0    1/0       0/0    1/0
[a] ──────── [e] ──────── [c] ──────── [f]         [d] ──────── [b]
                                        0/1  1/1    0/1  1/1

b) Äquivalente Zustände

Zwei Zustände können nur dann äquivalent sein, wenn sie bei gleicher Eingabe die gleichen Ausgaben erzeugen. Nach Ausgabeverhalten zerfallen die Zustände in zwei Kandidatengruppen:

( für und ),
( für und )

  1. und erzeugen gleiche Ausgaben und haben identische Folgezustände (: , : ). Also gilt .

  2. : Für geht nach und nach ; wegen sind die Folgezustände äquivalent. Für gehen beide nach . Die Ausgaben stimmen überein .

Page 2

  • : Für geht nach , aber nach . Da und unterschiedliche Ausgaben erzeugen, gilt , also .
  • : Für geht nach und nach . Wegen (unterschiedliche Ausgaben) folgt .

Eine weitere Iteration liefert keine neuen Äquivalenzen. Ergebnis:

Reduziertes Zustandsdiagramm (mit , , , , Startzustand ):

  0/0    1/0       0/0    1/0       0/1    1/1       0/1    1/1
[A] ──────── [F]         [B] ──────── [D]

c)

Für 4 Zustände genügen 2 Flip-Flops mit Zustandsvariablen .

Wahl der Kodierung: Die Ausgabe ist genau in den Zuständen und (unabhängig von ). Wir kodieren daher so, dass genau diese Zustände markiert — dann gilt einfach und die Ausgabe kostet kein einziges Gatter:

Startzustand der Flip-Flops: (entspricht , also dem alten Startzustand ).

Übergangstabelle:

Zustand
0 0 0 0 0 0
0 0 1 0 1 0
0 1 0 0 0 0
0 1 1 1 1 0
1 0 0 1 1 1
1 0 1 1 0 1
1 1 0 0 1 1
1 1 1 1 0 1

Ableitung der Schaltfunktionen:

Aus den Spalten und liest man ab:

Für betrachtet man (Spaltenvergleich): dieser Wert ist genau dann 1, wenn und gilt, also

Page 3

Das Zwischensignal kommt in beiden Gleichungen vor und wird geteilt:

  FF0: z₀          FF1: z₁
   │  │              │  │
   │  └──┐    ┌──────┘  │
   │     │    │         │
   │   ┌─┴──┐ │       ┌─┴──┐
   │   │AND2│ │       │XOR2│ ← h = z₁ ⊕ x
   │   └──┬─┘ │       └──┬─┘
   │      │   │          │
   │   ┌──┴──┴──┐    ┌───┴───┐
   └──→│  XOR2   │←───│  z₀'  │
       └────────┘    └───────┘
         z₁'

Kosten: 2 Flip-Flops + 3 Gatter (XOR2, AND2, XOR2 ∈ STD) = 5 < 8

Aufgabe 3

Gegeben: Mealy-Automat mit , ,

a) Ausgabefolge: , Endzustand:

b) Zustands- und Ausgabetafel:
0 1
1 1
0 1
1 0
0 0
1 1
0 0
1 1

Page 4

c) Boolesche Ausgabefunktion :

Mit Hilfe der gegebenen Codierung gilt es eine Boolesche Funktion , für die Ausgabe des Automaten zu finden.

Wahrheitstafel über :

Zustand
0 0 0 1
0 0 1 1
0 1 0 1
0 1 1 0
1 0 0 0
1 0 1 1
1 1 0 0
1 1 1 1

ON-Menge:

  • deckt
  • deckt
  • deckt
  • deckt

Damit ist

Page 5

Aufgabe 4

a)

(alle Minterme, partitioniert nach Anzahl positiver Literale):

Schritt : Verglichen werden nur Monome aus benachbarten Blöcken, die sich genau an einer Stelle unterscheiden. Die unterschiedliche Variable wird eliminiert:

0001 + 0011 → 00-1
0001 + 0101 → 0-01
0001 + 1001 → -001
0011 + 1011 → -011
0101 + 1101 → -101
1001 + 1011 → 10-1
1001 + 1101 → 1-01

Der Minterm 1110 lässt sich mit keinem anderen Minterm kombinieren. Er wird von keinem überdeckt, also ist er ein Primimplikant:

partitioniert nach Variablenmenge:

Schritt : Kombiniert werden nur Monome mit gleicher Variablenmenge , die sich an genau einer Stelle unterscheiden:

-001 + -011 → -0-1
-001 + -101 → --01
0-01 + 1-01 → --01
00-1 + 10-1 → -0-1

Jedes Element von wird hierbei weiter kombiniert, es entstehen keine Primimplikanten auf Stufe 1:

ü

partitioniert nach ():

Schritt : Beide Elemente haben unterschiedliche Variablenmengen und lassen sich nicht kombinieren. Beide sind Primimplikanten:

Primimplikantenmenge:

Page 6

b) Karnaugh-Map und Vergleich

KV-Diagramm:

00 01 11 10
00 0 1 1 0
01 0 1 0 0
11 0 1 0 1
10 0 1 1 0

Durch das KV-Diagramm ergibt sich . Das deckt sich exakt mit Prim() aus a). Da alle drei Primimplikanten wesentlich sind, ist das Minimalpolynom:

c) Kosten

i) Vollständiges Polynom (7 Minterme): Jeder Minterm hat 4 Literale:

ü

ii) Reduziertes Polynom (3 Primimplikanten):

ü

d)

Quine-McCluskey: Nein. Ein 64-Bit Addierer hat Eingangsbits (plus Carry), also einen Eingaberaum der Größe . QM startet mit der expliziten Aufzählung aller Minterme und vergleicht sie paarweise. Der Speicher- und Zeitbedarf wächst exponentiell mit der Variablenzahl, daher ist das Verfahren für 129 Variablen nicht anwendbar.

Karnaugh-Veitch: Nein. KV-Diagramme sind ein manuelles Mustererkennungsverfahren, das anschaulich nur bis etwa 4 Variablen funktioniert. Für 129 Variablen höchst unanwendbar.