TI08-1

Technische Informatik
Sommersemester 2026
[Name], [Name]
Übungsblatt 08
24.06.2026

Gegeben ist die Primimplikantentafel für Minterme und Primimplikanten .

, also dominiert die Zeile .

Die restlichen Zeilen sind unvergleichbar, keine Spalte ist wesentlich, also direkt zu Petrick:

Zusammenfassen:

Damit:

Der kürzeste Term ist (Kosten 2). Probe: und überdecken alle sechs Minterme.

Minimalpolynom: .

a)

b)

Die Länge des längsten Pfades in einem Schaltkreis ist der Pfad mit höchster Tiefe. hat die höchste Tiefe mit:

Schritt 1: 1. Reduktionsregel

Jede Spalte hat mindestens zwei Einsen, also gibt es keine wesentlichen Primimplikanten.

Schritt 2: 2. Reduktionsregel

Jede Zeile, die überdeckt, überdeckt auch . Also gilt für alle Spalte dominiert .

Schritt 3: 3. Reduktionsregel

Zeile überdeckt und damit alles, was Zeile überdeckt. Da nicht teurer als ist, dominiert somit .

Schritt 4: 1. Reduktionsregel

Spalte wird nur noch von überdeckt, ist wesentlich. und alle von überdeckten Spalten werden entfernt.

Schritt 5: 3. Reduktionsregel

Zeile überdeckt und damit alles, was , , jeweils überdecken. überdeckt alle drei Zeilen, werden also gelöscht.

Die Tafel lässt sich allein mit den drei Reduktionsregeln vollständig auflösen, die Methode von Petrick ist hier nicht nötig. Die gefundenen wesentlichen Primimplikanten sind :

Gegeben mit

a)

ON-Menge: die Vektoren mit ungeradem Hamming-Gewicht, also , , , .

Quine-McCluskey, alle Paare mit Hamming-Distanz 1:

Jeder Kandidat „−" deckt zwei Vektoren ab, von denen einer (der Partner mit geflipptem Bit) gerades Hamming-Gewicht hat und damit nicht in der ON-Menge liegt. Also ist keiner der zusammengefassten Terme ein gültiger Implikant, und die vier Minterme sind alle selbst Primimplikanten und essentiel.

b) für beliebiges

Seien zwei ON-Minterme mit Hamming-Distanz 1, also und unterscheiden sich an einer Position . Der zusammengefasste Term deckt auch den Vektor mit geflipptem ab. Dessen Hamming-Gewicht ist , also gerade, also . Damit ist der zusammengefasste Term kein Implikant.

Jeder Minterm ist sein eigener Primimplikant. Anzahl:

c) durch Fallunterscheidung

Sei und . Die Gesamtparität hängt nur von und ab:

Die Spalte für ist genau , also .

d)

Wir wählen . Allgemein gilt die Tiefenrekurrenz ; diese ist für minimal, da beide Teilbäume gleich tief sind. Jede andere Wahl würde eine Seite tiefer machen und die Gesamttiefe erhöhen.

Schaltkreisskizze (Tiefe 3 = , 7 Gatter):

e)

Sei mit . Durch -fache balancierte Zerlegung ergibt sich:

Tiefe: Mit Basisfall und Rekurrenz folgt

Kosten: Auf Ebene liegen XOR-Gatter. Aufsummiert:

Der Schaltkreis für () hat somit:

a)

Carry . Ergebnis . Mit kein Überlauf, darstellbar.

b)

Carry . liegt außerhalb , und zeigt einen Überlauf an. Nicht darstellbar.

c)

Carry . liegt außerhalb , und zeigt einen Überlauf an. Nicht darstellbar.