 |
Digitaltechnikvon Prof. Jürgen Plate |
|
Digitaltechnikvon Prof. Jürgen Plate |
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 = 3Fü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 |
|---|
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.
Das KV-Diagramm hat folgende Merkmale:
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.
| (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 ...
Im ersten Schritt wird die Wahrheitstabelle in das KV-Diagramm überführt und im zweiten Schritt Rechtecke gebildet, z. B.:
Für das Beispiel im Bild oben gilt:
Die Gruppen müssen so groß wie möglich sein.
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:
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:
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
Ein weiteres Beispiel:
Insgesamt ergibt sich:
"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.
Y = (X1 ∧ ¬X3)
∨ (X0 ∧ ¬X2)
∨ (X1 ∧ X2)
mit AZ = 2 + 2 + 2 + 3 = 9
DNF:
Als weiterer Effekt ergibt sich die Erkenntnis, dass die angegebene
DF nicht minimal ist. Die MDF lautet:
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.
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:
Die Berechnung der disjunktiven Minimalform mit dem QMC-Verfahren
wird folgendermaßen durchgeführt:
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
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,
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:
Diese Primimplikanten weren nun in einer Tabelle den Mintermen
gegenübergestellt:
Bei der Auswahl des Minimalsatzes aus den Primimplikanten wird
also folgendermassen vorgegangen:
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:
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:
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.
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:
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:
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:
2. Minimieren Sie folgende Schaltfunktionen mittels des KV-Diagramms:
3. Gegeben sei die Schaltfunktion
y(x3,x2,x1,x0) = (x3 ∧ ¬x2) ∨ (¬x3 ∧ ¬x1)
∨ (¬x2 ∧ x0) ∨ (x1 ∧ x0)
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).
5. Gegeben ist die Schaltfunktion
y(x3,x2,x1,x0) = Σ(8,9,10,12,13,14)
2. Aufgabe
3. Aufgabe
4. Aufgabe
5. Aufgabe
2. Gegeben ist die Funktion Z:
2. Aufgabe
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:
2. Aufgabe:
3. Aufgabe:
Y = (X3 ∨ X0) ∧ (X3 ∨ ¬X2) ∧
(X2 ∨ ¬X1 ∨ X0) ∧ (¬X2 ∨ X1 ∨ X0)
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
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.
Unter Ausnutzung der P-Terme ergibt sich:
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:
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)
(¬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.
W(D,C,B,A) = (¬B ∧ A)
∨ (D ∧ A)
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
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.
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 "*").
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)
1. Tabelle bzw. Liste:
Gruppe dezimal a b c ok
1 0 0 0 0 x
2 2 0 1 0 x
4 1 0 0 x
3 5 1 0 1 x
6 1 1 0 x
2. Tabelle bzw. Liste:
Gruppe dezimal a b c ok
1 0,2 0 - 0 x
0,4 - 0 0 x
2 2,6 - 1 0 x
4,5 1 0 - P1
4,6 1 - 0 x
3. Tabelle bzw. Liste:
Gruppe dezimal a b c ok
1 0,2,4,6 - - 0 P2
1 0,4,2,6 - - 0
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).
Der Vergleich aller Terme aus Gruppe 1 mit allen Termen der Gruppe
2 (0 mit 2, 0 mit 4) ergibt (0,2) und (0,4). Der Vergleich aller
Terme von Gruppe 2 mit Gruppe 3 ergibt (2,6), (4,5) und (4,6).
Daran denken: das "-" wird wie "0" oder "1" behandelt und muss
ebenfalls bei beiden Termen an der gleichen Stelle stehen.
Verglichen werden auch hier nur die Terme, die sich nur bei
einer Variablen unterscheiden, also (0,2) mit (4,6) und (0,4)
mit (2,6). Es bleibt also ein Primimplikant übrig (4,5).
Es sind keine weiteren Zusammenfassungen mehr möglich. Jedoch
repräsentieren die beiden Einträge (0,2,4,6) und (0,4,2,6)
dieselben Vollkonjunktionen → es ergibt beidesmal denselben
Term "--0", es kann also eine Zeile gestrichen werden.
a ∧ c
a ∧ ¬b
¬b ∧ ¬c
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.
Falls alle Spalten markiert sind, ergibt sich die MDF aus der ODER-Verknüpfung
aller Kernprimimplikanten.
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.
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)
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.
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.
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)
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
Bestimmte Gattertypen nicht vorhanden
(oder nicht erwünscht)
DF kann ohne Mehraufwand nur durch NAND realisiert werden:
→ NAND-NAND-Folge
Y = (x1 ∧ x2) ∨ (x3 ∧ x4)
→ ¬[¬(x1 ∧ x2) ∧ ¬(x3 ∧ x4)]
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.
Lösungen
1. Aufgabe
w = [x2 ∧ (x1 ∨ x0) ∨ (x1 ∧ x0) oder
w = [x0 ∧ (x1 ∨ x2) ∨ (x1 ∧ x2)
nach d: 1 x ODER eingespeist in 1 x UND, parallel 1 x UND,
beide in 1 x ODER, 3 Gatterebenen
KNF: y = Π(2,6,12,13,14)
Y(x3,x2,x1,x0) = (x2 ∨ ¬x0) ∧ (x3 ∨ ¬x0) ∧ (x2 ∨ x1)
Übungen zur QMC-Minimierung
1. Gegeben ist folgende Funktion Y:
Y(x3,x2,x1,x0) = Σ(1,3,6,7,8,9,12,13,15)
Z(x3,x2,x1,x0) = Σ(0,2,4,8,9,13) mit den P-Termen 1,3,6,11,12 und 15
Lösung
1. Aufgabe
Y = (x3 ∧ x2 ∧ x1) ∨ (x3 ∧ x1) ∨ (x3 ∧ x2 ∧ x0)
∨ (x2 ∧ x1)
Y = (¬x3 ∧ x2 ∧ x1) ∨ (x3 ∧ ¬x1) ∨
(¬x3 ∧ ¬x2 ∧ x0) ∨ (x3 ∧ x2)
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.
z(x2,x1,x0) = (0,2,6,7), P-Term: 4
z(x3,x2,x1,x0) = (0,1,4,5,11,15), P-Terme: 3,7
Lösung
1. Aufgabe
y = (¬x2 ∧ x0) ∨ m
z = ¬x0 ∨ m
y = (¬x3 ∧ ¬x0) ∨ m
z = (¬x3 ∧ ¬x1) ∨ m
UND-UND-Folge = UND-Verknüpfung
Zum vorhergehenden Abschnitt
Zum Inhaltsverzeichnis
Zum nächsten Abschnitt
Copyright © Hochschule München, FK 04, Prof. Jürgen Plate
Letzte Aktualisierung: 09. Feb 2013