Warum sind Sum-of-Products-Implementierungen beliebter als Product-of-Sums-Implementierungen?

Nach dem, was ich in meinen digitalen Logikkursen gelernt habe, wird tendenziell alles mit NAND gemacht, da sie billiger sind und jede boolesche Funktion mit NAND (oder übrigens NOR) realisiert werden kann. Ich könnte mir vorstellen, dass Produktsummenimplementierungen (UND- und ODER-Gatter) aus diesem Grund nicht besonders allgegenwärtig sind.

Obwohl Produkt-von-Summen und Summe-von-Produkten im Wesentlichen die gleiche Komplexität haben (eins kann durch Invertieren aller Ein- und Ausgänge in das andere umgewandelt werden), denke ich, dass die meisten Leute es einfacher finden, mit der Summe von Produkten zu arbeiten. Angenommen, ein ROM-Chip soll an Speicheradressen [während denen MREQ aktiv sein wird] bei 0xC000–0xFFFF ausgewählt werden und soll auch an Adresse 0x0000–0x3FFF ausgewählt werden, wenn BANKSEL nicht gesetzt ist. Seine Auswahlgleichung könnte in Produktsummenform geschrieben werden als:

UseROM = (MREQ & A15 & A14) # (MREQ & !A15 & !A14 & !BANKSEL)

Die entsprechende Produkt-von-Summen-Form wäre unter der Annahme der gleichen Ausgangspolarität

UseROM = MREQ & (A15 # !A14) & (!A15 # A14) & (A14 # !BANKSEL)

Das Summe-der-Produkte-Formular identifiziert effektiv die Umstände, unter denen die Ausgabe aktiv sein sollte, während das Produkt-der-Summe-Formular effektiv die Umstände identifiziert, unter denen die Ausgabe inaktiv sein sollte. Bei ersterem handelt es sich um zwei Produktbegriffe, die jeweils eindeutig einem Zugang in einem der beiden Sortimente zugeordnet sind. Bei letzterem gibt es vier Faktoren, von denen nur einer einen offensichtlichen Zusammenhang mit dem gewünschten Verhalten hat. Man könnte den Sinn der Ein- und Ausgänge umkehren und etwas mehr wie das Erste erhalten:

DontUseROM = (!MREQ # !A15 # !A14) & (!MREQ # A15 # A14 # BANKSEL)

Das wird die Komplexität reduzieren, um dem ersten Beispiel zu entsprechen, aber es ist weitaus weniger intuitiv. In der Tat ist der einzige Weg, dies zu verstehen, herauszufinden, was passieren muss, damit DontUseROM niedrig wird, dh ENTWEDER der erste ODER der zweite Faktor muss niedrig werden. Und jeder Faktor wird nur dann niedrig, wenn die Eingaben ALLE Bedingungen erfüllen, die dafür erforderlich sind. Mit anderen Worten, zurück zur Summe der Produkte.

Umgekehrte Logik kann unnatürlich sein. Kommen wir zur quantifizierten Logik:

"Alles ist entweder eine Ente (und quakt) oder ein Hund (und bellt) oder es ist weder eine Ente noch ein Hund."

Wenn Sie das Dual aufschreiben und dann DeMorgans verwenden, um die Logik umzukehren, erhalten wir etwas Unnatürliches:

Dual (so weit so gut):

DeMorgans, Schritt 1:

Schritt 2:

„Es gibt kein Ding, das gleichzeitig:

• ist entweder ein Nicht-Quacker oder eine Nicht-Ente; und
• ist entweder ein Nichtbeller oder ein Nichthund; und
• ist entweder eine Ente oder ein Hund oder beides."

Sag was? :)

Sum-of-Products geht Hand in Hand mit Teile-und-Herrsche. Eine Produktsummendarstellung eines Satzes teilt ihn in alle Fälle, die ihn unabhängig wahr machen. Satz P ist wahr, wenn so und so; oder eine Situation; oder wenn dieser andere Fall. Die Aufteilung in unabhängige Fälle trägt zur Klarheit der Argumentation bei.

Darüber hinaus beschäftigen wir uns in der Prädikatenlogik und dem damit verbundenen Denken normalerweise mit positiven Wörtern wie "Ente" und weniger mit negativen wie "Nicht-Ente". "Nicht-Ente" ist keine Klasse von Objekten. Dinge werden anhand positiver Attribute klassifiziert, die sie haben, und nicht anhand dessen, was sie nicht haben. Der Raum der Dinge, die "Nicht-Ente" sind, ist unbegrenzt. Das Argumentieren mit solchen Verneinungen ist verwirrend.

In der Aussagenlogik , wie in der Logik nullter Ordnung ohne Quantoren, wie wir es in logischen Schaltungen zu tun haben, können wir die vollständige Wahrheitstabelle aufschreiben. Es kann sich herausstellen, dass der negative Raum einer Funktion tatsächlich einfacher zu charakterisieren ist.

Beispielsweise hat eine boolesche Formel über vier Variablen nur eine Tabelle mit 16 Zeilen. Angenommen, es gibt drei Zeilen, für die es wahr ist, und es ist überall sonst falsch. Dann wird eine einfache Formel erstellt, indem diese drei Kombinationen von vier Variablen angegeben und mit oder kombiniert werden .

Angenommen, die Formel ist nur in drei Zeilen falsch. Dann kann es bequemer und natürlicher sein, diese Ausnahmen zu charakterisieren und so auszudrücken: Die Formel ist wahr, wenn die Variablen nicht in dieser Kombination sind, und nicht in dieser anderen Kombination, und nicht in dieser dritten Kombination. Die nicht -Operatoren können dann in die Kombinationen verteilen, was ein Produkt über Summen ergibt.

Positives Beispiel:

A B C D  P
0 0 0 0  0 
0 0 0 1  0
0 0 1 0  0
0 0 1 1  0
0 1 0 0  1 *
0 1 0 1  0
0 1 1 0  0
0 1 1 1  1 *    Sum of products:
1 0 0 0  0      P = A'BC'D' + A'BCD + ABC'D
1 0 0 1  0
1 0 1 0  0
1 0 1 1  0
1 1 0 0  0
1 1 0 1  1 *
1 1 1 0  0
1 1 1 1  0

Negativbeispiel:

A B C D  P
0 0 0 0  1 
0 0 0 1  1
0 0 1 0  1
0 0 1 1  1
0 1 0 0  0 *
0 1 0 1  1
0 1 1 0  1
0 1 1 1  0 *    Product of sums:
1 0 0 0  1      P = (A'BC'D' + A'BCD + ABC'D)'
1 0 0 1  1      P = (A'BC'D')'(A'BCD)'(ABC'D)'
1 0 1 0  1      P = (A + B' + C + D)(A + B' + C' + D')(A' + B' + C + D')
1 0 1 1  1
1 1 0 0  1      Sum of products:
1 1 0 1  0 *    A'B'C'D' + A'B'C'D + A'B'CD' ... (10 more terms)
1 1 1 0  1
1 1 1 1  1

Trotzdem ist es trotz ihrer Einfachheit etwas schwierig, die dritte Formel (Produkt von Summen) im Vergleich zur zweiten (Produkt von negierten Produkten) zu verstehen. Allerdings ist auch die alternative nicht vereinfachte Summe von 13 Produkten aufgrund der Vielzahl der Begriffe schwer nachvollziehbar.

Zunächst einmal: Wie andere bereits sagten, ist es möglich, alle Logikfunktionen mit eindeutigen NAND- oder NOR-Gattern zu implementieren.

Aufgrund seiner statischen CMOS-Implementierung neigt das NAND-Gatter dazu, schneller zu sein als das NOR. Das liegt daran, dass das NAND-Gatter den kritischen Pfad als eine Reihe von N nMOS-Transistoren hat, wobei N der Fan-In ist:

Das NOR hat stattdessen den kritischen Pfad mit einer Reihe von N pMOS-Transistoren.

Unter den gleichen Bedingungen sind pMOS aufgrund der geringeren Beweglichkeit von Löchern im Vergleich zu Elektronen weniger leitfähig als nMOS, und daher ist es vorzuziehen, NAND-Gatter zu verwenden.

Die Ausbreitungsverzögerung zum UND-Gatter ist geringer als beim ODER-Gatter, sodass die Implementierung der Logik in SOP besser ist als in POS. Der zweite Punkt sind die Kosten des Gatters, UND-Gatter ist billiger als ODER-Gatter.