Minimierung Flashcards
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.
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.
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.
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.
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.
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.
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.
Welche Güteklassen von Feldverbünden kennen wir?
Implikant
Primimplikant
Kern-Primimplikant
Absolut eliminierbarer Primimplikant
Relativ eliminierbarer Primimplikant
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
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.
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
Definieren sie einen absolut eliminierbaren Primimplikanten
Ein Primimplikant, der kein Einselement (keinen Minterm) besitzt, der nicht bereits durch einen anderen Kern-Primimplikanten abgedeckt wird
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.
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
Nennen sie die Grundregeln für das Aufstellen der disjunktiven Normalform und des KV-Diagramms
- Ausgehend von der Wahrheitstabelle das KV-Diagramm aufstellen
- Anhand der Wertetabelle die Felder mit 1, 0 und X für Don’t Care eintragen
- Benachbarte 1-Felder werden zu einem Block zusammengefasst, redundante Blöcke dürfen benutzt werden
- Zwei Blöcke die sich nur in einer Variablen unterscheiden lassen sich zusammenfassen zu einem größeren Block
- Ein 1-Feld und ein X-Feld dürfen in mehreren Blöcken integriert sein
- 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
- Die logische Gleichung ergibt sich als disjunktive (ODER) Verknüpfung der konjunktiven Terme
- 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
