Minimierung Flashcards Preview

Technische Grundlagen 2 > Minimierung > Flashcards

Flashcards in Minimierung Deck (19):
1

Was sind Minimierungsverfahren?

Minimierungsverfahren sind systematische Verfahren zum Auffinden von konjunktiver oder disjunktiver Minimalform einer gegebenen boolschen Funktion.
Je nach Komplexität der Aufgabenstellung gibt es verschiedene Verfahren.
Damit sollen Schaltungen optimiert werden und im Endeffekt Geld für unnötige Gatter bei der Umsetzung gespart werden.

2

Beschreiben sie das grafische Minimierungsverfahren nach Karnaugh-Veitch

Die grafische Minimierung funktioniert unter der Verwendung sogenannter KV-Diagramme.
Dafür werden Wertetabellen für eine Boolsche Funktion aufgestellt und diese wird in ein KV-Diagramm eingetragen. Wenn die Funktion 1 für ein Feld ist, wird eine 1 ins Diagramm eingetragen, wenn die Funktion 0 ist, wird eine 0 eingetragen.
Benachbarte Felder (2x1, 2x2, 1x4, 2x4) können zusammengefasst und damit vereinfacht werden.
Don't Cares werden mit einem X eingetragen und können für die Optimierung verwendet werden, müssen aber nicht berücksichtigt werden.

3

Was ist ein Minterm?

Ein Minterm ist eine konjunktive Verknüpfung (UND) aller Variablen, für welche die Funktion 1 ergibt.
Die Minterme werden dann mit einem ODER verbunden.
Der Term beschreibt alle Kombinationen, für die die Funktion 1 ausgibt.

4

Was ist ein Maxterm?

Ein Maxterm ist die disjunktive (ODER) Verknüpfung aller Variablen, für welche die Funktion 0 ausgibt.
Die Maxterme werden dann mit einem UND verbunden.
Der Term beschreibt alle Kombinationen, für die die Funktion 0 ausgibt und stellt die Negation des Minterms dar.

5

Wie kann man Minterme und Maxterme bestimmen?

Man kann entweder aus der Wertetabelle alle Terme für y = 1 aufstellen und diese negiert sind die Maxterme. Diese Darstellung ist allerdings noch nicht optimiert.
Außerdem kann man das KV-Diagramm verwenden und aus den Optimierungen den Minterm und Maxterm aufstellen. Diese Darstellung ist dann auch optimiert.

6

Was ist die kanonische disjunktive Normalform (kDNF) und die kanonische konjunktive Normalform (kKNF)

Kanonisch bedeutet, es ist noch keine Vereinfachung/Minimierung passiert. Die boolsche Funktion ist also in ihrer einfachsten und aufwendigsten Form beschrieben.
In der kanonischen disjunktiven Normalform wird eine boolsche Funktion durch Disjunktion (ODER-Funktion) ihrer Minterme m dargestellt.
Analog dazu ist die kanonische konjunktive Normalform die Darstellung einer boolschen Funktion durch Konjunktion (UND-Funktionen) ihrer Maxterme M.

7

Was ist die DNF und KNF?

Die DNF beschreibt die Sammlung aller Minterme für eine boolsche Funktion.
Die KNF beschreibt die Sammlung aller Maxterme für eine boolsche Funktion.
Die beiden Normalformen lassen sich ineinander überführen, daraus folgt, es gibt zu jeder Schaltfunktion einen äquivalenten Term in DNF und einen äquivalenten Term in KNF.

8

Welche Güteklassen von Feldverbünden kennen wir?

Implikant

Primimplikant

Kern-Primimplikant

Absolut eliminierbarer Primimplikant

Relativ eliminierbarer Primimplikant

9

Definieren sie einen Implikanten

Ein Implikant ist ein Feldverbund im KV-Diagramm, bzw. der entsprechende algebraische Term. Ein Implikant überdeckt mindestens eine oder maximal alle Einsstellen der Funktion f. Ein Minterm ist also auch ein Implikant

10

Definieren sie einen Primimplikanten

Ein Implikant wird als Primimplikant bezeichnet, wenn er in keinem anderen Implikanten vollständig enthalten ist. Ein Primimplikant wird also nicht durch einen anderen Implikanten überdeckt und besitzt damit mindestens eiine Einsstelle mehr als die existierenden Implikanten von f.

11

Definieren sie einen Kern-Primimplikanten

Ein Kern-Primimplikant oder essentieller Primimplikant ist ein Primimplikant, der mindestens ein Eins-Element (Minterm) besitzt, welcher von keinem anderen Primimplikanten dargestellt wird

12

Definieren sie einen absolut eliminierbaren Primimplikanten

Ein Primimplikant, der kein Einselement (keinen Minterm) besitzt, der nicht bereits durch einen anderen Kern-Primimplikanten abgedeckt wird

13

Welche Faustregeln für Minimierung kann man festhalten?

Alle Minterme müssen überdeckt werden.
Kern-Primimplikanten müssen in der Schaltungsrealisierung grundsätzlich berücksichtigt werden, sie bilden den Kern der Schaltung.
Bei mehreren möglichen Lösungen wird die mit den geringsten Projektbezogenen Kosten ausgewählt.

14

Definieren sie ein Don't Care Feld

Ein Don't Care Feld ist ein Feld bzw. ein Term, bei dem es egal ist ob der Term 1 oder 0 ist und der dementsprechend nur als Optimierungspotential mitgenutzt wird, aber nicht zwingend verwendet werden muss

15

Nennen sie die Grundregeln für das Aufstellen der disjunktiven Normalform und des KV-Diagramms

1. Ausgehend von der Wahrheitstabelle das KV-Diagramm aufstellen
2. Anhand der Wertetabelle die Felder mit 1, 0 und X für Don't Care eintragen
3. Benachbarte 1-Felder werden zu einem Block zusammengefasst, redundante Blöcke dürfen benutzt werden
4. Zwei Blöcke die sich nur in einer Variablen unterscheiden lassen sich zusammenfassen zu einem größeren Block
5. Ein 1-Feld und ein X-Feld dürfen in mehreren Blöcken integriert sein
6. Jeder Block wird durch konjunktive Verknüpfung (UND) der Eingangsvariablen beschrieben, sobald ein größtmöglicher Block gefunden wurde, ist dieser nichtmehr zu vereinfachen und wird als Prim-Implikant bezeichnet
7. Die logische Gleichung ergibt sich als disjunktive (ODER) Verknüpfung der konjunktiven Terme
8. Die logische Gleichung wird nur dann minimal, wenn die Blöcke so groß wie möglich sind und die Anzahl der Blöcke minimal wird

16

Erklären sie das Grundprinzip von Quine-McCluskey

Wird verwendet, wenn es zu viele Variablen in einer Boolschen Gleichung gibt, um den grafischen Ansatz zu verwenden.
Die algorithmische Minimierung wird dabei auch oft für rechnerbasierte Minimierung genutzt.
1. Alle relevanten Minterme identifizieren
2. Die relevanten Minterme in Gruppen einteilen, je nach Anzahl der enthaltenen Einsen in den Termen
3. Gruppen zusammenfassen indem man zwei Terme aus benachbarten Gruppen vergleicht und wenn die 1 an der gleichen Stelle steht, ersetzt man die Stelle der zusätzlichen 1 mit einem Strich und die verschiedene 1 bleibt stehen
4. Solange 3. durchführen, bis man nichtmehr weiter vereinfachen kann
5. Überdeckungstabelle aufstellen mit den Variablen oben und den gefundenen Termen links

17

Welche Reduktionsregeln von Q-McCluskey müssen in der Überdeckungstabelle überprüft werden

Reduktionsregel 1: Wesentliche Primimplikanten
PI ist wesentlich, wenn es der einzige PI ist, der m überdeckt
Reduktionsregel 2: Zeilendominanz
Eine Zeile P1 dominiert P2 wenn P1 alle Punkte enthält von P2 und zusätzlich Punkte
Reduktionsregel 3: Spaltendominanz
Eine Spalte m1 dominiert eine Spalte m2, falls jede Zeile die m2 überdeckt von m1 überdeckt wird

18

Wie werden Don't Cares bei Q-McCluskey berücksichtigt

Sie können für die Optimierung verwendet werden.
Dafür werden sie bei der Bestimmung der Primimplikanten als Minterme mitgeführt und dementsprechend auch bei der Minimierungsoption verwendet. Bei der Überdeckungstabelle werden die Don't Care Felder nichtmehr berücksichtigt, da sie nicht abgedeckt werden müssen

19

Welche Felder werden bei einem JK FlipFlop im KV Diagramm zusammengefasst?

Bei J=1 S mit 1 als Dont Care

Bei K=1 R mit 0 als Dont Care