Digitaltechnik


von Prof. Jürgen Plate

5 Minimierung schaltalgebraischer Ausdrücke

5.1 Ziele und Möglichkeiten der Minimierung

Die aus einer Wahrheitstabelle gewonnene DNF oder KNF einer booleschen Funktion ist meist nicht die kürzeste und einfachste Form, wie das Beispiel "Würfeldecodierung" zeigte. Oft lassen sich Funktionen vereinfachen und zum Teil auch Variablen eliminieren. Die technische Realisierung der vereinfachten Funktion hat dann einen geringeren Aufwand zur Folge als die 1:1-Realisierung der Normalformen. Für die systematische Vereinfachung muss die boolesche Funktion als DNF oder KNF vorliegen. Es gibt verschiedene Vereinfachungsmethoden, von denen die folgenden beiden hier behandelt werden sollen: In allen Verfahren können nur Funktionen mit einer Ausgangsvariablen vereinfacht werden. Verfahren, mit denen Funktionen mit mehreren Ausgangsvariablen optimiert werden können, basieren meist auf den obigen Verfahren.

Messgröße zur Bestimmung der Komplexität einer zu realisierenden Schaltfunktion ist die Aufwandszahl AZ:

AZ = Gesamtanzahl aller benötigten Gattereingänge

Wobei gilt, dass die Eingangsvariablen immer in invertierter wie in Eigenform vorhanden sind.

Das folgende Beispiel stammt aus dem "Würfeldecoder" vom vorhergehenden Kapitel. Die Version der DNF lautete für a:

  a = (¬x3 ∧ x2 ∧ x1) ∨ (x3 ∧ ¬x2 ∧ ¬x1) ∨ (x3 ∧ ¬x2 ∧ x1)

  AZ = (3 + 3 + 3)   + 3      = 12
        and-Gatter  or-Gatter    
Die minimierte Form lautete:
  a = (x1 * x2) + x3

  AZ = 3
Für alle Minimierungsverfahren kommt die Kürzungsregel zum Ensatz (aus den Theoremen), die manchmal auch "Nachbarschaftsregel" genannt wird (bei der Minimierung mittels der Theoreme sind verständlicherweise alle Theoreme mehr oder weniger im Einsatz):

(A ∧ B) ∨ (A ∧ ¬B) = A
(A ∨ B) ∧ (A ∨ ¬B) = A

5.2 Minimierung mit den Theoremen

Umformen der vorgegebenen Gleichungen mit den Theoremen für boolesche Gleichungen bis eine Minimalform erzielt wird. Hauptsächlich kommen hier die o. a. Kürzungsregel und die Theoreme von De Morgan zum Einsatz. Das Verfahren erfordern oftmals Probieren und intuitives Vorgehen und sind in der Regel nur sinnvoll, wenn die Möglichkeit der Minimierung relativ offensichtlich ist.

Die Vorgehensweise kann an einem Beispiel demonstriert werden. Gegeben ist die Gleichung y = Σ(1,3,4,6,7) bei drei Eingangsvariablen (x3,x2,x1). Die Darstellung als DNF lautet:

  y = (¬x3 ∧ ¬x2 ∧ x1)      d1
    ∨ (¬x3 ∧ x2 ∧ x1)       d3
    ∨ (x3 ∧ ¬x2 ∧ ¬x1)      d4
    ∨ (x3 ∧ x2 ∧ ¬x1)       d6
    ∨ (x3 ∧ x2 ∧ x1)        d7
Die Aufwandszahl beträgt: AZ = 5*3 + 5 = 20

Die Kürzungsregel kann auf d1 und d3 angewendet werden, weil x2 in negierter und in Eigenform auftritt (und die anderen Terme identisch sind):

  (¬x3 ∧ ¬x2 ∧ x1) ∨ (¬x3 ∧ x2 ∧ x1) = (¬x3 ∧ x1)  
Ebenso lassen sich d6 und d7 kürzen, da x1 negiert und nicht negiert auftritt:
  (x3 ∧ x2 ∧ ¬x1) ∨ (x3 ∧ x2 ∧ x1) = (x3 ∧ x2)
Zusammengefasst ergibt sich:
  y = (¬x3 ∧ x1) ∨ (x3 ∧ ¬x2 ∧ ¬x1) ∨ (x3 ∧ x2)
Die Aufwandszahl beträgt nun: AZ = 2 + 3 + 2 + 3 = 10, ist also nur noch halb so gross. Das kann man auch gut erkennen, wenn man für beide Lösungen die Schaltung zeichnet:

Beispiel 2: Disjunktive Form vereinfachen

  y = (¬a ∧ b ∧ c) ∨ (a ∧ c) ∨ (a ∧ ¬b ∧ ¬c)
Trick! Zuerst erweitern mit: a ∧ c = (a ∧ b ∧ c) ∨ (a ∧ ¬b ∧ c)
  y = (¬a ∧ b ∧ c) ∨ (a ∧ b ∧ c) ∨ (a ∧ ¬b ∧ c) ∨ (a ∧ ¬b ∧ ¬c)
    = ((¬a ∨ a) ∧ b ∧ c) ∨ (a ∧ ¬b ∧ (c ∨ ¬c))
    = (b ∧ c) ∨ (a ∧ ¬b)
Beispiel 3: DNF vereinfachen
  y = (¬a ∧ ¬b ∧ c) ∨ (¬a ∧ b ∧ ¬c) ∨ (a ∧ ¬b ∧ ¬c) ∨ (a ∧ ¬b ∧ c) ∨ (a ∧ b ∧ ¬c)
Umstellen (Assoziativgesetz) und "verdoppeln" von a ∧ b ∧ ¬c (Expansionsgesetz) ergibt:
  y = (¬a ∧ ¬b ∧ c) ∨ (a ∧ ¬b ∧ c) ∨ (¬a ∧ b ∧ ¬c) ∨ (a ∧ b ∧ ¬c) ∨ (a ∧ b ∧ ¬c) ∨ (a ∧ ¬b ∧ ¬c)
    = ((a or ¬a) ∧ ¬b ∧ c) ∨ ((a or ¬a) ∧ b ∧ ¬c) ∨ ((b ∨ ¬b) ∧ a ∧ ¬c)
    = (¬b ∧ c) ∨ (b ∧ ¬c) ∨ (a ∧ ¬c)
    = ((a ∨ b) ∧ c) ∨ (¬b ∧ c) 
Wird ausser AND und OR auch EXOR zugelassen, ist die folgende Alternative möglich:
  y = (b ⊕ c) ∨ (a ∧ ¬c)
Beispiel 4: KNF vereinfachen
  y = (a ∨ b ∨ c) ∧ (a ∨ ¬b ∨ ¬c) ∧ (¬a ∨ ¬b ∨ ¬c)
    = (a ∨ b ∨ c) ∧ ((a ∧ ¬a) ∨ ¬b ∨ ¬c)
    = (a ∨ b ∨ c) ∧ (¬b ∨ ¬c)
Die Beispiele zeigen schon, dass eine Vereinfachung mit den Theoremen schon bei kleinen Ausdrücken relativ schwierig ist, da man nicht immer weiss, welche der Theoreme man anwenden soll, ob eine Erweiterung in späteren Schritten zur Vereinfachung führt und ob das erzielte Ergebnis tatsächlich die minimale Form ist.

5.3 Graphisches Minimierungsverfahren nach Karnaugh-Veitch

Ein Karnaugh-Veitch-Diagramm (KV-Diagramm) ist eine mehrdimensionale grafische Darstellung einer Funktion, bei der sich benachbarte Zellen nur im Hinblick auf eine Eingangsvariable unterscheiden (kombinatorische Nachbarschaft). Gewisse Mengen von mit "1" beschrifteten kleinen Quadraten werden durch Konturen gebündelt (verschmolzen), die sich auch durchdringen können. Der besondere Nutzen besteht darin, dass durch die Verschmelzung meist einfachere bzw. kürzere Funktionsdarstellungen gewonnen werden. Das KV-Diagramm eignet sich daher sehr gut für die Vereinfachung von logischen Schaltungen mit bis zu fünf Eingangs- und einer Ausgangsvariablen. Dabei wird die Wahrheitstabelle in ein Rechteck mit 2n Feldern übergeführt (n = Anzahl der Eingangsvariablen).

Begriffe:

Bis jetzt wurden eingeführt: Neu kommen nun hinzu: Beim KV-Diagramm kann man sich das folgendermaßen vorstellen:

Das KV-Diagramm hat folgende Merkmale:

Aufbau

Die KV-Diagramme werden induktiv durch Spiegelung gebildet: Zur Erzeugung des KV-Diagramms für n-dimensionale Funktionen wird das KV-Diagramm für (m–1)-dimensionale Funktionen durch Spiegelung verdoppelt. Die jeweils neu hinzu kommende Variable hat in der alten Tafel den Wert 0, in der neuen Hälfte der neuen Tafel den Wert 1.

Die Kästchennummern sind die Dezimalzahlen zu den Dualzahlen (xn ... x0) in der Spalte "Nr" der jeweiligen Wahrheitstabelle. Sie sehen also, dass ein KV-Diagramm den Inhalt der Wahrheitstabelle in anderer Form wiedergibt.

Normalerweise lässt man auch die Bezeichung der negierten Variablen fort, es werden also nur X0, X1, x2 usw. aufgeführt. In vielen Veröffentlichungen wird der Bereich der Variablen auch durch eine Linie parallel zur Kante des KV-Diagramms markiert, wie folgendes Beispiel zeigt:

Auch sind die KV-Diagramme achsensymmetrisch, sodass sich unter Umständen unterschiedlich aussehende, aber inhaltlich identische KV-Diagramme ergeben. Wichtig ist alleine die Zuordnung der Felder zu den jeweiligen Eingangsvariablen. Die folgende Abbildung zeigt eine Alternative zur Anordnung weiter oben.

Das Wichtigste ist abolute Sorgfalt beim Ausfüllen des KV-Diagramms. Zwei Beispiele mit jeweils zwei Eingangsvariablen:

In der Regel werden beim Minimieren einer DNF auch nur die mit "1" gefüllten Felder beschriftet (Minterme), da - wie weiter unten gezeigt wird - nur diese Felder für die Vereinfachung genutzt werden können. Im nächsten Beispiel wird ausgehend von der Wahrheitstabelle das KV-Diagramm gefüllt (zur besseren Übersicht sind die Feldnummern nochmals mit eingetragen):

Es kann aber auch von der Schaltfunktion als Kurzform der DNF (oder KNF) ausgegangen werden. Das obige KV-Diagramm könnte auch aus der Gleichung Y(x2,x1,x0) = Σ(2,3,6,7) hervorgehen. Wenn man eine Vorlage hat, bei der, wie in den obigen KV-Diagrammen, die dezimale Nummerierung eingetragen ist, hat man es sogar noch wesentlich leichter als bei der Wahrheitstabelle.

Grafische Minimierung mit KV-Diagrammen

KV-Diagramme aus der disjuntiven Normalform (DNF) bzw. aus disjunktiven Formen

Zwei logische Ausdrücke, die sich nur in einer Variablen unterscheiden, können zu einem Term zusammengefasst werden:

(x1 ∧ ¬x2) ∨ (x1 ∧ x2) = x1

Kombinatorisch benachbarte Minterme ("1"-Felder) im KV-Diagramm unterscheiden sich ebenfalls nur in jeweils einer Variablen und können somit zu einem übergeordneten Ausdruck zusammengefasst werden. Für die Darstellung des resultierenden Implikanten werden weniger Eingangsvariablen benötigt (durch die Anwendung der Kürzungsregel fällt ja immer die Eingangsvariable weg, die sowohl in Eigenform als auch invertiert vorliegt). Dabei lassen sich zwei benachbarte "Pärchen" auch wieder zusammenfassen und so fort. Es es ergibt sich also eine Reduktion um ...

Deshalb werden immer möglichst viele Felder zusammengefasst, was möglichst kurze Formeln (d. h. wenige Variablen) für die Implikanten ergibt. Die Vorgehensweise ist dann folgendermassen:

Im ersten Schritt wird die Wahrheitstabelle in das KV-Diagramm überführt und im zweiten Schritt Rechtecke gebildet, z. B.:

Im dritten Schritt wird die vereinfachte Funktionsgleichung erstellt, wobei für jedes Rechteck anhand der Koordinatenbezeichnungen eine Formel angegeben werden kann. Dabei werden, wie schon erwähnt, Variablen welche invers und nicht invers (in Eingenform) auftreten, weggelassen.

Für das Beispiel im Bild oben gilt:

Regeln für die Gruppenbildung


Zusammenfassung: Man sucht eine vollständige Überdeckung der Einsen mit möglichst großen rechteckigen Blöcken.

Beispiel: y = (¬a ∧ b ∧ c) ∨ (a ∧ c) ∨ (a ∧ ¬b ∧ ¬c)
Um die DNF zu erhalten, muss der mittlere Term erweitert werden: (a ∧ c) = (a ∧ b ∧ c) ∨ (a ∧ ¬b ∧ c)

Die vier Minterme werden als "1" im KV-Diagramm eingetragen:
¬a ∧ b ∧ c
a ∧ b ∧ c
a ∧ ¬b ∧ c
a ∧ ¬b ∧ ¬c

Es ergeben sich drei Primimplikanten: (a ∧ c), (a ∧ ¬b) und (b ∧ c).

Da aber der rote Primimplikant (a ∧ c) vollständig von den anderen beiden abgedeckt wird, ist er nicht mehr nötig und es ergibt sich als endgültige Lösung:
y = (a ∧ ¬b)(b ∧ c)

Wir merken uns also:


Beispiel: Statt einer Formel ist eine Wahrheitstabelle gegeben. Ausgehend von dieser werden zunächst die entsprechenden Felder mit "1" ausgefüllt und anschließend die Primterme ermittelt:

Als MDF ergibt sich: Y = ¬X1 ∨ (¬X0 ∧ X2)

Wie schon gesagt, kommt es bei der Zusammenfassung benachbarter Felder darauf an, möglichst große Blöcke zu bilden. Je größer der Block, desto einfacher die Schaltfunktion. Dabei muss jedes mir einer "1" gefüllte Feld erfasst werden. Das folgende Bild zeigt Beispiele für das Zusammenfassen von Mintermen in KV-Diagrammen durch Zweier-, Vierer- und Achterblöcke:

Das folgende Beispiel zeigt, dass es nicht nur mehrere gleichwertige MDF gegen kann, sondern sich auch - wenn man nicht aufpasst - ungünstige Zusammenfassungen ergeben können. Das folgende Bild zeigt zwei KV-Diagramme zur daneben stehenden Wahrheitstabelle. Das obere KV-Diagramm benötigt fünf Minterme und hat 1 Vierer-, 3 Zweier- und 1 Einsergruppe.

Das untere KV-Diagramm fasst (richtigerweise) die grüne und die violette Zweiergruppe über die Ränder hinweg zu einer weiteren Vierergruppe zusammen (im unteren KV-Diagramm rot gezeichnet). Ebenso wird die Einsergruppe "über Kante" zu einer Zweiergruppe (orange).

Damit ergibt sich dann die MDF: Y = (¬X2 ∧ X3) ∨ (¬X1 ∧ X3) ∨ (¬X0 ∧ X1 ∧ ¬X3)

Es gibt auch Sonderfälle: Einige Funktionen besitzen keine Kern-Primimplikanten. Bei anderen Funktionen lassen sich keine Minterme/Maxterme zusammenfassen, sie können somit nicht minimiert werden. Das folgende Bild zeigt links eine Funktion ohne Kern-Primimplikanten und rechts eine nicht minimierbare Funktion:

KV-Diagramme aus der konjuntiven Normalform (KNF) bzw. aus konjunktiven Formen

DNF und KNF sind zwei völlig gleichwertige Realisierungsmöglichkeiten eines schaltalgebraischen Ausdrucks. So wie die DNF zur MDF so ist die KNF der gleichen Schaltfunktion zur minimierte konjunktive Form minimierbar. Beide minimierten Formen sind in ihrem logischen Wahrheitsgehalt ebenso gleichwertig; nicht jedoch in ihrem Minimierungsergebnis.

Im Prinzip ist die Vorgehensweise wie bei den disjunktiven Formen, es werden hier nur die Nullen anstelle der Einsen betrachtet. Man sucht nun konjunktive Terme (Implikate) durch Betrachtung von Maxtermen und deren mögliche Zusammenfassung:

  1. Zusammenfassung größtmöglicher Blöcke von Nullen, wobei jeder Block wieder 2k Felder umfassen muss
    → bilden der disjunktiven Minimalform für inverse Funktion ¬Y
    → Primimplikate
  2. Auswahl einer minimalen Anzahl von Primimplikaten (Kernprimimplikate und weitere Primimplikate).
    → minimale konjunktive Form (MKF)
Es gibt noch eine Besonderheit beim Ablesen der Terme für die "0"-Blöcke: Um den disjunktiven Summenterm zu erhalten, verknüpft man die Variablen, in denen der Block nicht liegt, disjunktiv miteinander. Die "0"-Blöcke bezeichnen ja die Felder, bei denen Y = 0 (also ¬Y = 1) ist. Deshalb die Invertierung.
→ Anwendung der De-Morgan'schen Regel ergibt konjunktive Minimalform der Originalfunktion Y.
Man kann aber auch, wie im folgenden Beispiel, aus den "0"-Gruppen Minterme bilden und dies anschliessend mittels DeMorgan invertieren.

Das folgende Beispiel illustriert die Vorgehensweise:

Für die Zusammenfassung der Felder zu Gruppen ergeben sich die rechts daneben stehenden Minterme. Um von diesem ausgehend zu Maxtermen zu gelangen, muss das Theorem von DeMorgan angewendet werden:

¬I1 = X3 ∨ X0
¬I2 = X3 ∨ ¬X2
¬I3 = X2 ∨ ¬X1 ∨ X0
¬I4 = ¬X2 ∨ X1 ∨ X0

Insgesamt ergibt sich also:

Y = ¬I1 ∧ ¬I2 ∧ ¬I3 ∧ ¬I4
Y = (X3 ∨ X0) ∧ (X3 ∨ ¬X2) ∧ (X2 ∨ ¬X1 ∨ X0) ∧ (¬X2 ∨ X1 ∨ X0)

Ein weiteres Beispiel:
Die Wahrheitstabelle wurde schon ins KV-Diagramm übertragen und die Gruppen sind bereits markiert. Diesmal sollen die Maxterme direkt aus dem KV-Diagramm bestimmt werden:


Es ergeben sich die folgenden Maxterme:
¬X0 ∨ X2
¬X2 ∨ X3
¬X1 ∨ X2 ∨ ¬X3

Insgesamt ergibt sich:
Y = (¬X0 ∨ X2) ∧ (¬X2 ∨ X3) ∧ (¬X1 ∨ X2 ∨ ¬X3)

Minimierung unvollständig definierter Funktionen

Sind in einer Wahrheitstabelle nicht immer alle Wertekombinationen der Variablen definiert ("beliebig", "dont’t care"), so spricht man von einer unvollständig definierten Funktion. Sind solche Felder vorhanden, lassen sie sich beliebig als "0" oder "1" interpretieren, was bei den Vereinfachungen mehr Möglichkeiten der Optimierung bietet. Solche "beliebig" wählbare Werte nennt man auch Parameter-Terme oder P-Terme. Für günstige Minimierungsergebnisse sind P-Terme in Gruppen integrierbar (d. h. P = 1). Gruppen, die nur aus P-Termen bestehen, sind unsinnig. Es gilt also:

In einer Wahrheitstabelle und im KV-Diagramm werden die unbestimmten Funktionswerte (P-Terme) als "X" eingetragen.

"X"-Terme können im KV-Diagramm sowohl als "0" oder als "1" betrachtet werden. Dadurch lassen sich optimalere Blöcke bilden.

Das folgende Beispiel zeigt die Nutzung der P-Terme für die Gruppierung. Ohne Ausnutzung der P-Terme wüden sich zwei Zweiergruppen und eine Einergruppe ergeben. Die resultierende Formel würde dann lauten: Y = (X1 ∧ ¬X2 ∧ ¬X3) ∨ (¬X0 ∧ X1 ∧ X2) ∨ (X0 ∧ ¬X1 ∧ ¬X2 ∧ X3). Die Aufwandszahl ist: AZ = 3 + 3 + 4 + 3 = 13.


Unter Ausnutzung der P-Terme ergibt sich:

Y = (X1 ∧ ¬X3)(X0 ∧ ¬X2)(X1 ∧ X2)

mit AZ = 2 + 2 + 2 + 3 = 9

KV-Diagramm für 5 Variablen

Unten sehen Sie die Darstellung des KV-Diagramms für 5 Variablen. Für die "Nachbarschaftsbeziehungen" gelten folgende Regeln:
  1. Wie bisher: Horizontal und vertikal nebeneinanderliegende Zellen gelten als benachbart und können ggf. zusammengefasst werden (Torus-Topologie über den Rand hinweg nicht vergessen).
  2. Zellen, die bei Spiegelung an der Geraden g aufeinander fallen, sind ebenfalls benachbart (z. B. 4 und 20 oder 7 und 23).


Darstellung und Generierung von Codes mit KV-Diagrammen

Beispiel: Glixon-Code

Eintragen einer DF und Expandierung auf DNF/KNF


Beispiel: W(D,C,B,A) = (¬B ∧ A)(D ∧ C ∧ A)

DNF:

(¬D ∧ ¬C ∧ ¬B ∧ A) ∨
(¬D ∧  C ∧ ¬B ∧ A) ∨
( D ∧ ¬C ∧ ¬B ∧ A) ∨
( D ∧  C ∧ ¬B ∧ A) ∨
( D ∧  C ∧ ¬B ∧ A) ∨
( D ∧  C ∧  B ∧ A)
Auf die gleiche Art und Weise kann die KNF "herausgelesen" werden.

Als weiterer Effekt ergibt sich die Erkenntnis, dass die angegebene DF nicht minimal ist. Die MDF lautet:
W(D,C,B,A) = (¬B ∧ A)(D ∧ A)

Die grafische Minimierung mit Hilfe eines KV-Diagramms kann rein theoretisch für beliebig viele Eingangsvariablen durchgeführt werden. Ab fünf Eingangsvariablen wird die Analyse der zusammenfassbaren Felder aufgrund der zunehmend komplexeren Nachbarschaftsbeziehungen zu kompliziert. Daher eignen sich KV-Diagramme für die Minimierung von Funktionen mit bis zu fünf Eingangsvariablen.

5.4 Tabellarisches Verfahren nach Quine-McCluskey

Da die Vereinfachung boolescher Funktionen über das KV-Diagramm nur von Hand möglich ist, wurde das hier vorgestellte Verfahren (benannt nach den Erfindern) zur Lösung mittels Computer entwickelt. Es ist weniger anschaulich als das KV-Diagramm, kann dafür automatisiert durchgeführt werden. Auch das Verfahren von Quine und McCluskey (QMC-Verfahren) stützt sich auf die Kürzungsregel:

(A ∧ B) ∨ (A ∧ ¬B) = A
(A ∨ B) ∧ (A ∨ ¬B) = A

Es arbeitet also nach dem gleichen Prinzip wie die KV-Diagramme. Es werden nur die Terme betrachtet, bei denen die boolesche Funktion "1" ergibt. Solche Terme, die sich in nur einer Variablen unterscheiden, werden zusammengefasst. Ausgangspunkt ist in der Regel die Wahrheitstabelle einer Funktion. Im Gegensatz zu den KV-Diagrammen gilt jedoch:

Bei diesem Verfahren werden die Minterme der disjunktiven Normalform systematisch miteinander verglichen, um Variablen der Beziehung (A ∨ ¬A) = 1 zu eliminieren. Um solche Beziehungen zu finden, werden die Minterme in Gruppen zusammengefasst, welche nach Anzahl der "1"-Werte der Variablen geordnet werden. Um Vereinfachungen zu finden, werden aufeinanderfolgende Gruppen miteinander verglichen.

Die Berechnung der disjunktiven Minimalform mit dem QMC-Verfahren wird folgendermaßen durchgeführt:

  1. Tabelle aller Minterme aufstellen
  2. Zeilen zusammenfassen, die sich nur in einer Variable unterscheiden
  3. Zeilen weiter zusammenfassen, bis alle Primimplikanten gefunden
  4. Aufstellen einer neuen Primimplikanten-Tabelle
  5. Identifikation der Kernprimimplikanten → zur Minimalform hinzufügen
  6. Weitere Primimplikanten hinzufügen bis alle Minterme überdeckt werden

Zuerst wird die Tabelle aller Minterme aufgestellt, in der die Minterme nach Gruppen sortiert eingetragen werden, wobei die Sortierung der Gruppen nach Anzahl der Einsen aufsteigend erfogt. Also

Nun werden jeweils alle Terme der Gruppe m mit allen Termen der Gruppe m+1 verglichen. Unterscheiden sich beide Terme nur in einer Variablen, können die beiden Terme zusammengefasst werden. In der Tabelle werden die beiden Terme als "verwendet" markiert und in einer zweiten Tabelle der Term eingetragen, wobei die entfallene Variable durch "-" markiert wird. Falls ein Term nicht verwendet werden konnte, bildet er einen Primimplikaten für die spätere Weiterverarbeitung (markiert mit "*").

Mit der so entstandenen zweiten Tabelle wird genauso verfahren und es entsteht eine dritte Tabelle und so weiter. Die Iteration endet, wenn sich keiner Terme mehr kombinieren lassen. Beim Zusammenfassen kann es vorkommen, dass die gleichen Ausdrücke mehrfach entstehen. In solchen Fällen werden alle "Doubletten" bis auf eine einzige gestrichen.

Nun erfolgt die Aufstellung der Primimplikantentabelle (alle mit "*" markierten Terme), aus der man schon eine minimale Form erstellen kann. Oft ergeben sich noch weitere Vereinfachungen durch Überdeckung einiger Terme.

Schreibvereinfachung: Für eine einfache tabellarische Behandlung schreibt man für eine Variable in einem Konjunktionsterm:

1, wenn die Variable nicht invertiert auftritt,
0, wenn die Variable invertiert auftritt und
-, wenn die Variable nicht (mehr) auftritt.

Beispiel

Gegeben ist folgende boolesche Funktion:
f(a,b,c) = Σ(0,2,4,5,6) In der Spalte "ok" wird ein "x" eingetragen, wenn der Term für einen Eintrag in der folgenden Tabelle verwendet wurde. Andernfalls handelt es sich um einen Primterm (P1, P2).

Die 1. Liste wird aus der DNF gefüllt, die 2. Liste entsteht durch das Zusammenfassen der Terme aus der 1. Liste und die 3. Liste entsprechend aus der 2. Liste:

Es kann aber auch der Fall auftreten, dass die nach obigem Schema gefundene disjunktive Form noch nicht minimal ist. Unter Umständen kann man aus dem Minimalsatz noch weitere Primimplikanten heraus gestrichen werden. Das ist möglich, wenn die Minterme eines Primimplikanten durch die anderen Primimplikanten vollständig abgedeckt werden. Dazu ein Beispiel:

Die Funktion y = Σ(0,4,5,7) führt nach dem obigen Verfahren zu den Primimplikanten:
 a ∧  c
 a ∧ ¬b
¬b ∧ ¬c

Diese Primimplikanten weren nun in einer Tabelle den Mintermen gegenübergestellt:

      PI       0  4  5  7  Minterme 
    a ∧  c           x  x
    a ∧ ¬b        x  x     
   ¬b ∧ ¬c     x  x
Man erkennt sofort, dass der mittlere Primimplikant (a ∧ ¬b) weggelassen werden kann, weil seine Minterme durch die anderen abgedeckt werden (4 durch den ersten, 5 durch den dritten). Das ergibt dann als MDF: y = (a ∧ c) ∨ (¬b ∧ ¬c). Auf der anderen Seite sind die anderen beiden Primimplikanten notwendig, da der Minterm 0 nur durch den ersten und Minterm 7 nur durch den dritten Primimplikanten abgedeckt werden.

Bei der Auswahl des Minimalsatzes aus den Primimplikanten wird also folgendermassen vorgegangen:

  1. Aufbau der Überdeckungsmatrix
  2. Auswahl des Minimalsatzes
    Jeder vorkommende Minterm (bzw. dessen Dezimalnummer) muss durch einen Primimplikanten abgedeckt werden. Anschließend lassen sich nicht mehr benötigte Primimplikanten eliminieren → Zeileneliminierung → es entsteht eine kleinere Matrix.
Falls alle Spalten markiert sind, ergibt sich die MDF aus der ODER-Verknüpfung aller Kernprimimplikanten.

Trifft dies nicht zu, werden in einem zweiten, kleineren Schema die nicht markierten Primterme und die noch nicht bedienten Minterme eingetragen. Enthält dieses Schema Zeilen ohne Markierungen, so können diese ebenfalls entfallen.

Weiterhin können Spalten dann gestrichen werden, wenn es eine oder mehrere andere Spalten gibt, die weniger Markierungen als die betrachtete Spalte haben und diese Markierungen nur in den gleichen Zeilen auftreten.

Durch diese Schritte entsteht nun ein nochmals vereinfachtes Schema, anhand dessen unter Berücksichtigung der jeweiligen Aufwandszahlen die günstigste Auswahl aus den verbliebenen Primimplikanten zu treffen ist. Hierbei ist sicherzustellen daß alle Minterme erfasst werden.

Die MDF wird durch ODER-Verknüpfung der Kernprimimplikanten sowie der ausgewählten Primimplikanten gebildet.

Beispiel: Gegeben ist die Funktion Y = f(x1,x2,x3,x4) = Σ(0,4,6,11,12,13,14)

1. Liste:

   Gruppe  dezimal   dual    ok 
      1       0      0000    x  
      2       4      0100    x  
      3       6      0110    x
             12      1100    x  
      4      11      1011    P1 
             13      1101    x
             14      1110    x  
2. Liste:
   Gruppe  dezimal   dual    ok 
      1     0,4      0-00    P2 
      2     4,6      01-0    x
            4,12     -100    x  
      3     6,14     -110    x
            12,13    110-    P3
            12,14    11-0    x  
3. Liste:
   Gruppe  dezimal   dual    ok 
      1   4,6,12,14  -1-0    P4
          4,12,6,14  -1-0           → Ende
Bilden der Überdeckungsmatrix:
(Die Kernprimimplikanten sind mit "*" markiert - nur ein "x" in der Spalte.)
   Primimp.  0   4   6  11  12  13  14 Minterme 
      P1                 *
      P2     *   x
      P3                     x   *
      P4         x   x       x       *          
Es können die folgenden Spalten eliminiert werden:
   Spalte    überdeckt durch 
      4         0 und 6
     12         6 und 13  
     14         6
Die verkleinere Matrix:
   Primimp.  0   6  11  13 Minterme 
      P1             *
      P2         *
      P3                 *
      P4     *                      
Leider kann kein Primimplikant eliminiert werden. Es ergibt sich die MDF als
Y = P1 ∨ P2 ∨ P3 ∨ P4 =
(x1 ∧ ¬x2 ∧ x3 ∧ x4) ∨ (¬x1 ∧ ¬x3 ∧ ¬x4) ∨ (x1 ∧ x2 ∧ ¬x3) ∨ (x2 ∧ ¬x4)

Beispiel: Gegeben ist die Funktion Y = f(x1,x2,x3,x4,x5) = Σ(2,4,5,6,10,12,13,14,18,22,26,30)

1. Liste:

   Gruppe    dezimal   dual     ok 
      1         2      00010    x
                4      00100    x  
      2         5      00101    x
                6      00110    x
               10      01010    x
               12      01100    x
               18      10010    x  
      3        13      01101    x
               14      01110    x
               22      10110    x
               26      11010    x  
      4        30      11110    x  
2. Liste:
   Gruppe    dezimal   dual     ok 
      1        2,6     00-10    x
               2,10    0-010    x
               2,18    -0010    x
               4,5     0010-    x
               4,6     001-0    x
               4,12    0-100    x  
      2        5,13    0-101    x
               6,14    0-110    x
               6,22    -0110    x
              10,14    01-10    x
              10,26    -1010    x
              12,13    0110-    x
              12,14    011-0    x
              18,22    10-10    x
              18,26    1-010    x  
      3       14,30    -1110    x
              22,30    1-110    x
              26,30    11-10    x  
3. Liste:
   Gruppe    dezimal   dual     ok 
      1     2,6,10,14  0--10    x
            2,6,18,22  -0-10    x
           2,10,18,26  --010    x
            4,5,12,13  0-10-    P1
            4,6,12,14  0-1-0    P2 
      2    6,14,22,30  --110    x
          10,14,26,30  -1-10    x
          18,22,26,30  1--10    x  
4. Liste:
   Gruppe    dezimal   dual     ok 
      1     2,6,10,14  ---10    P3
          18,22,26,30              
Aufstellen der Überdeckungsmatrix:
         2   4   5   6  10  12  13  14  18  22  26  30 
   P1        x   *           x   *
   P2        x       x       x       x
   P3    *           x   *           x   *   *   *   * 
P1 ist Kernprimimplikant (5, 13), ebenso P3 (2, 18 - 30). Die Spalten 4, 12 und 13 können eliminiert werden (P1), ebenso die Spalten 6, 10, 14, 18, 22, 26 und 30 (P3). Es ergibt sich die reduzierte Matrix:
         2   5 
   P1        *
   P2
   P3    *     
Die Zeile bei P2 ist leer → P2 kann entfallen. Es ergibt sich die MDF: Y = (¬x2 ∧ x3 ∧ ¬x5) ∨ (¬x1 ∧ x2).

Funktionen mit Beliebig-Werten, MKF

Die Vorgehensweise beim Minimieren unvollständig definierter Funktionen ist analog der Behandlung vollständig definierter Funktionen. Hierbei wird zunächst angenommen, dass die Funktion überall da, wo sie nicht definiert ist (Beliebig-Wert, P-Term) den Wert "1" annimmt. Hierdurch können möglichst viele Terme zusammengefasst werden.

Bei der anschließenden Primimplikantentafel hingegen werden dann nur die tatsächlichen Minterme der Funktion berücksichtigt. Die P-Terme dürfen nicht in die Primimplikantentafel aufgenommen werden.

Ähnlich wie beim Minimieren mit dem KV-Diagramm kann man mit dem QMC-Verfahren zunächst die MDF der inversen Funktion bestimmen und durch Negieren anschließend die MKF erhalten.

5.5 Ergänzungen

Funktionenbündel

Bisher wurden nur Fälle betrachtet, bei denen Eingangsvariable zu einer einzigen Schaltfunktion verknüpft wurden. Häufig werden jedoch aus einer Gruppe von Eingangsvariablen mehrere Schaltfunktionen gebildet. Wenn beispielsweise ein Decoder von 8-4-2-1-BCD zu Dezimal entworfen werden soll, hat dieser vier Eingänge und zehn Ausgänge.

Schaltungen mit mehreren Ausgängen werden Funktionenbündel genannt. Dabei wird jeder Ausgang durch eine boolsche Funktion beschrieben, kann also auch gegebenenfalls schaltungstechnisch minimiert werden.

In derartigen Fällen ist es möglich, dass bestimmte Teilverknüpfungen (Gruppen, Primterme, Kernprimimplikanten) nicht nur in einer Funktion, sondern u. U. in mehreren Funktionen auftreten. Derartige Teilverknüpfungen müssen natürlich nicht mehrfach aufgebaut werden, sondern werden einmal realisiert und mehrfach verwendet.

Feststellbar sind diese gemeinsam benutzbaren Verknüpfungen:

Beispiel: Gegeben ist ein Bündel aus zwei Funktionen:
Y(x3,x2,x1,x0) = Σ(5,7,8,9,10,11,13,15)
Z(x3,x2,x1,x0) = Σ(0,1,5,6,7,8,9,13,14,15)

Betrachtet man die KV-Diagramme für beide Funktionen, sieht man sofort eine Gruppe (blau gezeichnet), die beide Funktionen gemeinsam haben: x0 ∧ x2. Wir können also formulieren:

Beispiel: Gegeben ist ein Bündel aus zwei Funktionen:
Y(x3,x2,x1,x0) = Σ(2,3,6,7,10,11)
Z(x3,x2,x1,x0) = Σ(0,6,7) mit den P-Termen: 1,8,9

Betrachtet man die KV-Diagramme für beide Funktionen, würde sich bei Y eine Zusammenfassung der vier nebeneinander stehenden Einsen anbieten (obere Hälfte von grün + violett). Wenn man jedoch beide Funktionen betrachtet, kann man bei Y vom Einzeloptimum abgehen und gewinnt so einen gemeinsamen Term (violett). Es ergibt sich dann:

Bestimmte Gattertypen nicht vorhanden

(oder nicht erwünscht)
  1. Nur NAND-Gatter vorhanden:
    DF kann ohne Mehraufwand nur durch NAND realisiert werden: → NAND-NAND-Folge
    Y = (x1 ∧ x2) ∨ (x3 ∧ x4) → ¬[¬(x1 ∧ x2) ∧ ¬(x3 ∧ x4)]

  2. Nur NOR-Gatter vorhanden:
    KF kann ohne Mehraufwand nur durch NOR realisiert werden: → NOR-NOR-Folge
    Y = (x1 ∨ x2) ∧ (x3 ∨ x4) → ¬[¬(x1 ∨ x2) ∨ ¬(x3 ∨ x4)]

    5.6 Übungen

    Übungen zur KV-Minimierung

    1. Die Schaltfunktion w(x2,x1,x0) habe immer dann den Wert 1, wenn zwei oder mehr Eingangsvariable den Wert 1 haben.
    1. Stellen Sie die Wahrheitstabelle für w auf
    2. Geben Sie die DNF der Schaltfunktion w an
    3. Ermitteln Sie die MDF mittels des KV-Diagramms
    4. Vereinfachen Sie diese MDF unter Anwendung der Logiktheoreme noch weiter
    5. Skizzieren Sie für die Lösungen nach c) und d) jeweils das Logikdiagramm
    6. Wie unterscheiden sich die Lösungen nach c) und d) hinsichtlich Aufwand

    2. Minimieren Sie folgende Schaltfunktionen mittels des KV-Diagramms:

    1. y(x2,x1,x0) = Σ(0,1,3,4,5,6)
    2. y(x3,x2,x1,x0) = Σ(0,1,2,3,5,7,8,9,10,11,12,15)

    3. Gegeben sei die Schaltfunktion

    y(x3,x2,x1,x0) = (x3 ∧ ¬x2) ∨ (¬x3 ∧ ¬x1) ∨ (¬x2 ∧ x0) ∨ (x1 ∧ x0)

    1. Tragen Sie die Schaltfunktion in das KV-Diagramm ein
    2. Prüfen Sie anhand des KV-Diagramms, ob gegebene Form minimal ist und geben Sie bei Bedarf die MDF an
    3. Geben Sie die DNF wie KNF in Kurzschreibweise an

    4. Eine Schaltfunktion von vier Variablen nimmt für die Minterme k2, k4, k6, k12, k13, k14, k15 den Wert 1 an. Die Eingangskombinationen der Terme k5, k9, k10 können nie aufreten (P-Terme).

    1. Geben Sie die MDF der Funktion an
    2. Ermitteln Sie auch die MKF der Funktion

    5. Gegeben ist die Schaltfunktion

    y(x3,x2,x1,x0) = Σ(8,9,10,12,13,14)

    1. Ermitteln Sie die MDF der Funktion
    2. Bestimmen Sie auch die MKF dieser Funktion
    3. Bestimmen Sie die Form des geringeren Realisierungsaufwandes und zeichnen Sie ihr Logikdiagramm.

    Lösungen

    1. Aufgabe
    1. w: Zeilen 3,5,6,7 : 1
    2. w = Σ(3,5,6,7)
    3. w = (x2 ∧ x1) ∨ (x2 ∧ x0) ∨ (x1 ∧ x0)
    4. w = [x1 ∧ (x2 ∨ x0)] (∨ x2 ∧ x0) oder
      w = [x2 ∧ (x1 ∨ x0) ∨ (x1 ∧ x0) oder
      w = [x0 ∧ (x1 ∨ x2) ∨ (x1 ∧ x2)
    5. nach c: 3 x UND (2 Eingänge) in 1 x ODER (3 Eingänge), 2 Gatterebenen
      nach d: 1 x ODER eingespeist in 1 x UND, parallel 1 x UND, beide in 1 x ODER, 3 Gatterebenen
    6. nach c: AZ = 9, nach d: AZ = 8

    2. Aufgabe

    1. y = ¬x1 ∨ (x2 ∧ x0) ∨ (x2 ∧ x0)
    2. y = x2 ∨ (x3 ∧ x0) ∨ (x1 ∧ x0) ∨ (x3 ∧ ¬x1 ∧ ¬x0)

    3. Aufgabe

    1. -
    2. minimale Form: y = (x3 ∧ ¬x1) ∨ (x1 ∧ x0) ∨ (x3 ∧ ¬x2)
    3. DNF: y = Σ(0,1,3,4,5,7,8,9,10,11,15)
      KNF: y = Π(2,6,12,13,14)

    4. Aufgabe

    1. MDF: Y(x3,x2,x1,x0) = (x1 ∧ x0) ∨ (x3 ∧ x2) ∨(x2 ∧ ¬x1)
    2. MKF: Y(x3,x2,x1,x0) = (x3 ∨ x2) ∧ (x3 ∨ ¬x0) ∧ (x2 ∨ x1) oder
      Y(x3,x2,x1,x0) = (x2 ∨ ¬x0) ∧ (x3 ∨ ¬x0) ∧ (x2 ∨ x1)

    5. Aufgabe

    1. MDF: Y(x3,x2,x1,x0) = (x3 ∧ ¬x1) ∨ (x3 ∧ ¬x0)
    2. MKF: Y(x3,x2,x1,x0) = x3 ∧ (¬x1 ∨ ¬x0)
    3. a: AZ = 6, b: AZ = 4

    Übungen zur QMC-Minimierung

    1. Gegeben ist folgende Funktion Y:
    Y(x3,x2,x1,x0) = Σ(1,3,6,7,8,9,12,13,15)
    1. Ermitteln Sie mit dem QMC-Verfahren eine MDF
    2. Vergleichen Sie die Resultate mit der Minimierung im KV-Diagramm

    2. Gegeben ist die Funktion Z:
    Z(x3,x2,x1,x0) = Σ(0,2,4,8,9,13) mit den P-Termen 1,3,6,11,12 und 15

    1. Bestimmen Sie mit dem QMC-Verfahren eine MDF von Z
    2. Bestimmen Sie nun die MKF von Z, indem Sie das QMC-Verfahren zunächst auf die inverse Funktion von Z anwenden und dann das Resultat negieren
    3. Ermitteln Sie die MKF, indem Sie nun das QMC-Verfahren mit den Maxtermen durchführen.

    Lösung

    1. Aufgabe
    1. Zwei gleichwertige MDF:
      Y = (x3 ∧ x2 ∧ x1) ∨ (x3 ∧ x1) ∨ (x3 ∧ x2 ∧ x0) ∨ (x2 ∧ x1)
      Y = (¬x3 ∧ x2 ∧ x1) ∨ (x3 ∧ ¬x1) ∨ (¬x3 ∧ ¬x2 ∧ x0) ∨ (x3 ∧ x2)
    2. DNF in KV-Diagramm eintragen, ergibt gleiche Ergebnisse

    2. Aufgabe

    1. MDF: Z = (¬x3 ∧ ¬x0) ∨ (x3 ∧ ¬x1)
    2. ¬Z = (¬x3 ∧ x0) ∨ (x3 ∧ x1) → Z = (x3 ∨ ¬x0) ∧ (¬x3 ∨ ¬x1)
    3. entsprechend der Angaben aus der Vorlesung:
      negierte Variable: → 1
      nicht negierte Variable: → 0
      nicht vorhandene Variable: → -
      ergibt identische Tabellen wie in b) und nach entsprechender "Rückübersetzung" direkt die MKF

    Übungen zur Minimierung

    1. Ermitteln Sie von folgenden Funktionenbündeln jeweils die MDF und achten Sie bei Angabe der zu realisierenden Schaltung auf die Möglichkeit der Mehrfachausnutzung.
    1. y(x2,x1,x0) = (1,3,6,7), P-Term: 0
      z(x2,x1,x0) = (0,2,6,7), P-Term: 4
    2. y(x3,x2,x1,x0) = (4,11,15), P-Terme: 0,1,2,6,10
      z(x3,x2,x1,x0) = (0,1,4,5,11,15), P-Terme: 3,7

    2. Welche logische Struktur wird durch eine NAND-NOR-Folge ( NOR-Verknüpfung von NAND-Verknüpfungen) realisiert?

    3. Die Funktion w = (a ∧b) ∨ (c ∧ d) ∨ (e ∧ f) ist zu realisieren:

    1. mit UND-Gattern und Invertern
    2. mit NAND-Gattern
    3. mit NAND-Gattern mit nur 2 Eingängen

    Lösung

    1. Aufgabe
    1. m = (x1 ∧ x2)
      y = (¬x2 ∧ x0) ∨ m
      z = ¬x0 ∨ m
    2. m = (x3 ∧ x1 ∧ x0)
      y = (¬x3 ∧ ¬x0) ∨ m
      z = (¬x3 ∧ ¬x1) ∨ m

    2. Aufgabe:
    UND-UND-Folge = UND-Verknüpfung

    3. Aufgabe:

    Zum vorhergehenden Abschnitt Zum Inhaltsverzeichnis Zum nächsten Abschnitt


    Copyright © Hochschule München, FK 04, Prof. Jürgen Plate
    Letzte Aktualisierung: 09. Feb 2013