Prime Implicant Vereinfachung mit Petricks Methode

Quine-McCluskey Method with Don't Care (Dezember 2018).

Anonim

Prime Implicant Vereinfachung mit Petricks Methode


Was ist Petricks Methode "// www.encyclopedia.com/topic/Boolean_algebra.aspx" target = "_ blank"> Boolesche Algebra, eine Vereinfachungsmethode für komplexe Schaltungen. In Tabelle 1.1 ist ein Beispiel mit zwei Mindestlösungen dargestellt. Wenn die Anzahl der Variablen in einer gegebenen Funktion zunimmt, kann die Anzahl der Primimplikanten und die Komplexität des Primzahldiagramms drastisch zunehmen. In solchen Fällen können Versuch und Irrtum die beste Lösung sein, um alle Mindestlösungen zu finden. Die Methode, die im vorherigen Artikel erwähnt wurde, war ein guter Weg, um alle Minimum-Lösungen aus einem Diagramm zu finden, aber Petricks Methode hat einen viel besseren systematischen Ansatz. Vor dem Versuch, Petricks Methode auszuführen, alle wesentlichen Primimplikanten; ebenso wie die Minterme, die sie abdecken, müssen aus der Prim-Implikanten-Tabelle herausgenommen werden.

Tabelle 1.1

Um dieses Konzept vollständig zu erfassen, wird Tabelle 1.1 verwendet, um Petricks Methode zu veranschaulichen. Zu Beginn muss jede Zeile in der Tabelle ( P 1, P 2, P 3 ) beschriftet werden. Eine logische Funktion, P, wird gebildet, was gilt, wenn alle Minterms verdeckt sind. Dies ermöglicht, dass P1 eine logische Variable ist, was wahr ist, wenn die Primimplikanten in der P1-Zeile in der Lösung enthalten sind. P 2 sollte auch eine logische Variable sein, was wahr ist, wenn die Primimplikanten in der P 2 -Reihe in der Lösung usw. enthalten sind. Wenn man die Spalte 0 betrachtet, scheint diese Spalte X in den Reihen P 1 und P 2 zu haben ; Also müssen die Zeilen P 1 und P 2 gewählt werden, um den Minterm 0 abzudecken. Um nun den nächsten Minterm, Minterm 1, abzudecken, müssen die Zeilen P 3 oder P 1 gewählt werden; Daher muss ( P 1 + P 3 ) gelten, um wahr zu sein. Um Minterm 2 zu erfassen, muss ( P 2 und P 4 ) ebenfalls gelten. Um die Minterme 5, 6 und 7 leicht abzudecken, müssen der Ausdruck ( P 3 + P 5 ), ( P 4 + P 6 ) und ( P 5 + P 6 ) gelten, um wahr zu sein. Da alle Minterms abgedeckt werden müssen, um Petricks Methode anzuwenden, muss die folgende Funktion erfüllt sein:

P = ( P 1 + P 2 ) ( P 1 + P 3 ) ( P 2 + P 4 ) ( P 3 + P 5 ) ( P 4 + P 6 ) ( P 5 + P 6 ) = 1, was dies bedeutet ist, dass die Reihen P 1 oder P 2 gewählt werden müssen und die Reihe P 1 oder P 3 und die Reihe P 2 oder P 4, et al.

Als nächstes muss P vollständig auf eine minimale SOP reduziert werden. Dies ist relativ einfach aufgrund der Tatsache, dass es keine Komplimente des Ausdrucks gibt. Nach dem Multiplizieren mit der Booleschen Algebraregel ( X + Y ) ( X + Z ) = X + YZ sowie dem Verteilungsgesetz lautet die folgende Funktion:

P = ( P 1 + P 2 P 3 ) ( P 4 + P 2 P 6 ) ( P 5 + P 3 P 6 )

= ( P 1 P 4 + P 1 P 2 P 6 + P 2 P 3 P 4 + P 2 P 3 P 6 ) ( P 5 + P 3 P 6 )

= P 1 P 4 P 5 + P 1 P 2 P 5 P 6 + P 2 P 3 P 4 P 5 + P 2 P 3 P 5 P 6 + P 1 P 3 P 4 P 6 + P 1 P 2 P 3 P 6 + P 2 P 3 P 4 P 6 + P 2 P 3 P 6

Danach, mit X + XY = X, um redundante Terme aus der Logikfunktion P zu entfernen, wird die folgende Funktion erzeugt:

P = P 1 P 4 P 5 + P 1 P 2 P 5 P 6 + P 2 P 3 P 4 P 5 + P 1 P 3 P 4 P 6 + P 2 P 3 P 6

Da P nun wahr sein muss (oder P = 1), um jeden Minterm abzudecken, kann die Funktion wie folgt beschrieben werden. Um jeden Minterm vollständig abzudecken, müssen die Reihen P 1 und P 4 und P 5 gewählt werden, oder die Reihen P 1 und P 2 und P 5 und P 6 oder die Reihen P 2 und P 3 und P 6 . Obwohl es insgesamt fünf Lösungen gibt, für die die minimale Anzahl von Primimplikanten erhalten werden kann, sind die einzigen zwei ausgewählten Lösungen die Reihen P 1, P 4 und P 5 oder die Reihen P 2, P 3 und P 6 . Die Wahl der ersten Menge liefert F = a'b ' + bc' + ac und die zweite mit F = a'c ' + b'c + ab, die als die beiden minimalen SOP-Lösungen geschrieben werden.

Petricks Methode zusammengefasst, lautet wie folgt:

  1. Beginne damit, die Primzahlimplikate zu reduzieren; Dies kann erreicht werden, indem irgendeine wesentliche Primimplikanzzeile und die entsprechenden Spalten entfernt werden.
  2. Jede Zeile, die im Primimplikanten-Diagramm reduziert wurde, muss mit P1, P2, P3 et al.
  3. Es wird eine logische Funktion P gebildet, die gilt, wenn alle Spalten abgedeckt sind. Diese Funktion besteht aus einem Produkt von Summentermen, wobei jeder Summenterm die Form ( P i0 + P i1 + …) hat, wobei P i0, P i1 … die Zeilen angeben, die die i- Spalte abdecken.
  4. Die Logikfunktion P muss auf eine minimale Summe von Produkten reduziert werden, indem nach außen multipliziert wird und die Boolesche Algebraregel X + XY = X angewendet wird.
  5. Jeder Term in der resultierenden Funktion repräsentiert eine Lösung oder eine Reihe von Zeilen, die alle Minterme im Prim-Implikanten-Diagramm abdecken. Um zu bestimmen, was die Mindestlösungen sind, werden Begriffe ausgewählt, die eine minimale Anzahl von Variablen enthalten. Jeder dieser Begriffe repräsentiert eine Lösung mit einer minimalen Anzahl von Primimplikanten.
  6. Für jeden gefundenen Term wird die Anzahl der Literale in jedem Primimplikanten gezählt und notiert. Der oder die Ausdrücke, die der minimalen Gesamtanzahl von Literalen entsprechen, werden ausgewählt, und dann werden die entsprechenden Summen von Primimplikaten entsprechend ausgeschrieben.

Diese Methode ist für ziemlich große Diagramme sehr mühsam, aber andererseits ist sie auf einem Personalcomputer leicht implementierbar.

Vereinfachen mit der Quine-McCluskey-Methode

Wenn eine unvollständig spezifizierte Funktion präsentiert wird, ist die richtige Zuordnung der Werte zu den Nicht-Pflege-Bedingungen erforderlich, wenn ein Minimalformular für die Funktion erhalten werden soll. Im Folgenden wird die Quine-McCluskey-Methode modifiziert und verwendet, um eine Mindestlösung zu erhalten, wenn irgendwelche Nicht-Pflege-Begriffe existieren. Während des Prozesses werden Bedingungen, die nicht gepflegt werden, wenn sie vorhanden sind, so behandelt, als ob sie Mindestanforderungen wären. Auf diese Weise können die beiden zusammen mit zusätzlichen Mintermen kombiniert werden, um Literale zu entfernen, wenn sie verfügbar sind. Extra-Prim-Implikant (en) können aus Nicht-Interessieren erzeugt werden, dies ist in Ordnung, weil der / die Extra-Prim-Implikant (en) im nächsten Schritt des Prozesses entfernt werden. Während sie eine Prim-Implikanten-Tabelle bilden, werden die Nicht -Sorgen nicht an der Spitze geschrieben. Dies wird gemacht, um sicherzustellen, dass alle erforderlichen Minterms vollständig von einem der ausgewählten Primimplikanten abgedeckt sind, wenn das Diagramm gelöst wird. Dennoch sind die Nicht -Pflege-Begriffe am Ende nicht in der Lösung enthalten, es sei denn, sie wurden bereits bei der Bildung eines ausgewählten Primimplikanten verwendet. Es wird gezeigt, dass ein Beispiel zur Vereinfachung einer unvollständig spezifizierten Funktion ein besseres Verständnis dessen liefert, was gerade erläutert wurde.

$ F (A, B, C, D) = \ Summe m (2, 3, 7, 9, 11, 13) + \ Summe d (1, 10, 15) $$

(Die Summe von d und seinen Begriffen sind keine Pflege Begriffe)

Um nun die Primimplikanten zu finden:

Die Spalten mit Nicht-Pflege-Begriffen werden entfernt, wenn das folgende Diagramm erstellt wird:

* bezeichnet einen essentiellen Primimplikanten

F = B'C + CD + AD

Beachten Sie, dass, obwohl die angegebene ursprüngliche Funktion unvollständig angegeben wurde, dieser letzte Ausdruck für F vereinfacht ist und für alle möglichen Werte für A, B, C und D definiert ist und somit vollständig spezifiziert ist. Durch diese Methode wurden die Werte in der Wahrheitstabelle für F, die ursprünglich bereitgestellt wurde, automatisch den Nicht-Sorgen zugeordnet. Durch Ersetzen jedes Ausdrucks im letzten Ausdruck für F ( oben gezeigt) durch die entsprechende Summe von Mindestwerten kann der Ausdruck wie folgt geschrieben werden:

F = ( m 2 + m 3 + m 10 + m 11 ) + ( m 3 + m 7 + m 11 + m 15 ) + ( m 9 + m 11 + m 13 + m 15 )

Wenn m 10 und m 15 in diesem Ausdruck erscheinen und m 1 nicht, deutet dies darauf hin, dass die Nicht-Pflege-Begriffe in der Wahrheitstabelle, die ursprünglich für F angegeben wurde, wie folgt bezeichnet wurden:

für ABCD = 0001; F = 0; für 1010, F = 1; für 1111, F = 1

Auftauchen

Ab sofort sollten Sie wissen, was Petricks Methode ist, wie Sie sie anwenden und unvollständig spezifizierte Funktionen mit der Quine-McCluskey-Methode vereinfachen. Die Quine-McCluskey-Methode kann mit einem digitalen Computer verwendet werden, um Funktionen mit bis zu 15 oder mehr Variablen zu vereinfachen. Als nächstes wird eine Methode von in die Karte eingegebenen Variablen verwendet, um einen minimalen SOP-Ausdruck einer gegebenen Funktion zu finden.