Summe von Produkten (SOP) beherrschen: Leitfaden für Boolesche Funktionen

Kurz gesagt: Die Summe von Produkten (SOP) ist ein systematischer Weg, jede Wahrheitstabelle in einen Booleschen Ausdruck zu verwandeln: Schreiben Sie für jede Zeile mit Ausgang 1 einen Minterm und verknüpfen Sie sie dann mit ODER. Die kanonische Form ist korrekt, aber selten minimal – vereinfachen Sie mit Karnaugh-Maps oder Boolescher Algebra.

Die grundlegende Herausforderung des digitalen Entwurfs besteht darin, ein gewünschtes Verhalten – eine als Wahrheitstabelle ausgedrückte Regelmenge – in eine physische Anordnung von Logikgattern zu übersetzen. Wie lässt sich diese Lücke systematisch und ohne Raten schließen?

Die Antwort ist die Sum-of-Products-Form (SOP). SOP liefert eine mechanische, wiederholbare Methode, jede Wahrheitstabelle in eine funktionierende Schaltung auf Gatterebene umzuwandeln. Es ist der erste große Schritt von abstrakten Anforderungen zu greifbarer Hardware.

Was ist die Summe von Produkten?

Im Kern ist die Summe-von-Produkten-Form eine Methode, einen Booleschen Ausdruck zu schreiben, indem man einen oder mehrere UND-Terme mit ODER verknüpft. In der Booleschen Algebra nennen wir die ODER-Operation häufig „Summe“ und die UND-Operation „Produkt“.

Betrachten Sie den folgenden Ausdruck:

Hier ist $(A \cdot \overline{B})$ ein Produktterm und $(\overline{A} \cdot B)$ ein weiterer. Das Symbol + steht für die ODER-Operation, also für die „Summe“ dieser Produkte. Diese Struktur übersetzt sich direkt in eine zweistufige Schaltung: Eine erste Ebene aus UND-Gattern führt in eine zweite Ebene mit einem einzelnen ODER-Gatter. Diese Vorhersagbarkeit ist die Quelle ihrer Stärke.

Die atomare Einheit: Minterme

Um aus einer Wahrheitstabelle einen beliebigen SOP-Ausdruck zu bauen, müssen wir zunächst seinen grundlegenden Baustein verstehen: den Minterm. Ein Minterm ist ein spezieller Produktterm, der jede Variable der Funktion enthält, entweder in direkter oder komplementierter Form.

Für eine Funktion mit drei Variablen (A, B, C) gibt es $2^3 = 8$ mögliche Minterme. Jeder Minterm entspricht genau einer Zeile der Wahrheitstabelle.

Die Regel zum Erzeugen eines Minterms ist einfach:

• Hat die Variable in der Zeile den Wert 1, verwenden Sie die Variable direkt (etwa A).
• Hat die Variable in der Zeile den Wert 0, verwenden Sie ihr Komplement (etwa $\overline{A}$).

Listen wir die Minterme für ein System mit drei Variablen auf:

Beachten Sie, dass jeder Minterm nur für seine spezifische Eingangskombination den Wert 1 annimmt. Beispielsweise ist $m_5$ ($A \cdot \overline{B} \cdot C$) nur wahr, wenn A=1, B=0 und C=1 sind. Für alle anderen sieben Eingangskombinationen ist er falsch. Minterme sind Präzisionswerkzeuge, um einzelne Zeilen einer Wahrheitstabelle gezielt anzusprechen.

Von der Wahrheitstabelle zu SOP: eine Drei-Schritte-Methode

Sobald die Minterme verstanden sind, ist das Umwandeln einer Wahrheitstabelle in einen SOP-Ausdruck ein geradliniger, mechanischer Prozess.

Verwenden wir als Beispiel eine „2-aus-3-Mehrheitsfunktion“. Der Ausgang Y ist nur dann 1, wenn zwei oder mehr Eingänge 1 sind.

Schritt 1: Alle Zeilen mit Ausgang 1 identifizieren. In unserem Beispiel ist der Ausgang Y für die Eingangskombinationen 011, 101, 110 und 111 1.

Schritt 2: Den Minterm für jede dieser Zeilen schreiben. Aus der obigen Tabelle ergeben sich die entsprechenden Minterme $m_3, m_5, m_6,$ und $m_7$.

Schritt 3: Alle Minterme mit ODER verknüpfen. So erhalten wir den endgültigen SOP-Ausdruck der Funktion:

Dies wird als kanonische SOP-Form bezeichnet, denn sie ist eine direkte, nicht vereinfachte Summe aller relevanten Minterme. Sie beschreibt die Funktion vollständig, und daraus lässt sich sofort eine Schaltung bauen.

Häufige Falle: kanonische und minimale Form

Eine häufige Verwirrung bei Lernenden besteht darin, die kanonische SOP als endgültige Antwort anzusehen. Sie ist zwar funktional korrekt, aber fast nie die effizienteste Implementierung. Meist benötigt sie mehr Gatter und Eingänge als nötig.

Betrachten wir den Ausdruck der Mehrheitsfunktion erneut. Mit Boolescher Algebra lässt er sich vereinfachen:

Dieser algebraische Ansatz funktioniert, ist bei größeren Ausdrücken jedoch fehleranfällig. Eine Karnaugh-Map bietet eine visuelle Methode zur SOP-Vereinfachung. Wenn wir die 1en der Wahrheitstabelle in einer K-Map gruppieren, finden wir rasch einen wesentlich einfacheren Ausdruck:

Diese minimale SOP-Form implementiert exakt dieselbe Logik, benötigt aber nur drei UND-Gatter mit zwei Eingängen und ein ODER-Gatter mit drei Eingängen – eine deutliche Verbesserung gegenüber den vier UND-Gattern mit drei Eingängen und einem ODER-Gatter mit vier Eingängen der kanonischen Form. Die Lehre ist klar: Die erste abgeleitete SOP ist der Ausgangspunkt der Optimierung, nicht ihr Ziel.

Auf digisim.io simulieren

Bauen wir die nicht vereinfachte kanonische Version unserer Mehrheitsschaltung, um das Konzept zu bestätigen. Dies ist der beste Weg, die Verbindung zwischen Gleichung und Hardware zu verinnerlichen.

1. Eingänge einrichten: Ziehen Sie drei Input-Komponenten aus der Werkzeugleiste auf die Arbeitsfläche. Beschriften Sie sie mit A, B und C.
2. Die Minterme (Produktterme) erzeugen:

• Für den ersten Minterm $\overline{A} \cdot B \cdot C$ benötigen Sie ein NICHT-Gatter für Eingang A. Verdrahten Sie den Ausgang dieses NICHT-Gatters zusammen mit den Eingängen B und C mit einem UND-Gatter mit drei Eingängen.
• Wiederholen Sie diesen Vorgang für die anderen drei Minterme: $(A \cdot \overline{B} \cdot C)$, $(A \cdot B \cdot \overline{C})$ und $(A \cdot B \cdot C)$. Sie erhalten insgesamt vier UND-Gatter mit drei Eingängen.

3. Die Summe erzeugen: Verdrahten Sie die Ausgänge aller vier UND-Gatter mit einem einzigen ODER-Gatter mit vier Eingängen.
4. Den Ausgang hinzufügen: Verbinden Sie den Ausgang des letzten ODER-Gatters mit einer Output-Komponente (oder einer LED als visuelle Rückmeldung).

Testen Sie nun Ihre Schaltung! Schalten Sie die Eingänge A, B und C um. Der Ausgang ist nur aktiv, wenn mindestens zwei Eingänge High sind, exakt wie in der ursprünglichen Wahrheitstabelle. Sie haben erfolgreich eine Spezifikation in eine funktionierende digitale Logikschaltung übersetzt.

Die Verbindung von SOP zu NAND-NAND

Eine der wichtigsten Eigenschaften von SOP ist die direkte Abbildung auf NAND-NAND-Logik. In der CMOS-Technik sind NAND-Gatter physisch kleiner und schneller als UND- oder ODER-Gatter. Glücklicherweise lässt sich jeder SOP-Ausdruck mit den De-Morgan-Gesetzen in eine zweistufige NAND-NAND-Schaltung umwandeln.

Die Umwandlung ist mechanisch. Beginnen wir mit der minimalen Mehrheitsfunktion:

Wenden Sie doppelte Negation an, die den Wert nicht verändert:

Wenden Sie das De-Morgan-Gesetz auf den äußeren Überstrich an:

Jedes $\overline{AB}$ ist eine NAND-Operation, und der äußere Überstrich über ihrem Produkt ist ebenfalls ein NAND. Das Ergebnis ist eine zweistufige NAND-NAND-Schaltung: Drei NAND-Gatter mit zwei Eingängen führen in ein NAND-Gatter mit drei Eingängen. Sie ist logisch identisch zur UND-ODER-Implementierung, verwendet aber nur einen Gattertyp, was Fertigung und Zellbibliotheken vereinfacht.

Einsatz in der Praxis

Die Summe-von-Produkten-Form ist in die Architektur moderner Rechner eingebettet.

1. Programmierbare Logik-Arrays (PLAs): Diese integrierten Schaltungen dienen zur Implementierung komplexer kombinatorischer Logik. Die interne Struktur eines PLA ist eine direkte physische Manifestation des SOP-Konzepts. Sie besteht aus einer programmierbaren „UND-Ebene“ (um Produktterme zu erzeugen) und einer programmierbaren „ODER-Ebene“ (um die Produkte zu summieren). Ingenieurinnen und Ingenieure definieren eine Funktion, indem sie festlegen, welche Verbindungen in diesen Ebenen hergestellt werden; damit bauen sie effektiv eine kundenspezifische SOP-Schaltung in Hardware.
2. Speicheradressdekodierung: Muss eine CPU aus einer bestimmten Speicherstelle lesen oder dorthin schreiben, legt sie eine Adresse auf den Adressbus. Dekodierschaltungen im Speichercontroller müssen erkennen, welcher Speicherchip und welche Zeile/Spalte aktiviert werden soll. Diese Logik wird oft mit SOP implementiert. Ein Signal zum Aktivieren eines bestimmten RAM-Blocks könnte beispielsweise Enable_Block_3 = A_{15} \cdot A_{14} \cdot \overline{A_{13}} lauten. Dieser Produktterm stellt sicher, dass der Block nur ausgewählt wird, wenn die höherwertigen Adressbits genau diesem Muster entsprechen. Die Logik für die gesamte Speicherkarte ist eine Summe solcher Produktterme.

Die Summe-von-Produkten-Form bietet einen verlässlichen, systematischen Weg von einer Idee zu einer Schaltung. Sie garantiert, dass jede Boolesche Funktion, wie komplex sie auch sein mag, mit einer standardmäßigen zweistufigen UND-ODER- (oder NAND-NAND-)Gatterstruktur ausgedrückt und aufgebaut werden kann.

Fahren Sie mit dem nächsten Beitrag dieser Serie fort: Produkt von Summen (POS) – dem Dual, das aus den 0en statt den 1en der Wahrheitstabelle hergeleitet wird. Oder springen Sie zu Karnaugh-Maps, um SOP visuell zu minimieren.