Primärimpliant

Ein Primimplikant ist eine Gruppe benachbarter Einsen (oder Nullen, je nach Konvention) auf einer Karnaugh-Tafel, die nicht in eine größere Gruppe aufgenommen werden kann und dabei gültig bleibt. Er stellt das kleinste bedeutsame Cluster von Eingangskombinationen dar, die denselben Ausgang liefern, wobei der Begriff in der standardmäßigen booleschen Vereinfachung häufig speziell für Gruppen von Einsen gilt.

Auf einer Karnaugh-Tafel werden Zellen in rechteckigen Blöcken der Größen 1, 2, 4, 8 oder 16 Zellen angeordnet, wobei jede Zelle einen Minterm oder Maxterm darstellt. Ein Primimplikant ist eine maximale Gruppe: Sie enthält so viele benachbarte Zellen wie möglich, ohne die Nachbarschaftsregeln der Tafel zu verletzen. Wenn man ihn mit einer anderen Gruppe zu einem größeren Rechteck zusammenfassen könnte, wäre er nicht prim. Die Ermittlung aller Primimplikanten ist der erste Schritt zur Reduzierung einer booleschen Funktion auf ihre einfachste Form.

Nicht jeder Primimplikant muss in der endgültigen vereinfachten Gleichung vorkommen. Ein wesentlicher Primimplikant ist einer, der mindestens einen Minterm abdeckt, den kein anderer Primimplikant abdeckt, was ihn in jeder minimalen Lösung zwingend erforderlich macht. Nicht wesentliche Primimplikanten können einbezogen werden oder nicht; die Wahl hängt davon ab, ob ihre Auswahl die Gesamtkosten in Gattern und Literalen im Vergleich zu alternativen Abdeckungen senkt. Diese Unterscheidung ist wichtig beim Schaltungsentwurf, wenn die Chipfläche oder die Anzahl der Gatter begrenzt ist.

Praktische Anwendung im Schaltungsentwurf

Eine typische 4-Variable-Karnaugh-Tafel könnte fünf oder sechs Primimplikanten aufdecken, aber die minimale Ausdrucksform nutzt nur drei oder vier davon. Ein Logik-Designer ermittelt zunächst alle Primimplikanten, markiert welche wesentlich sind, und nutzt dann eine Primimplikant-Tabelle oder Petricks Methode, um die kleinste Menge auszuwählen, die alle Minterme abdeckt. Bei Tafeln mit mehr als sechs Variablen werden manuelle Verfahren unpraktisch; CAD-Werkzeuge nutzen Consensus-Algorithmen oder Quine-McCluskey-Tabellenverfahren, um Primimplikanten automatisch zu finden.

Der Begriff 'prim' stammt aus der Zahlentheorie, wo eine Primzahl nicht in kleinere Faktoren zerlegt werden kann; ebenso kann ein Primimplikant nicht in eine größere Gruppe aufgenommen (zerlegt) werden. Das Verständnis von Primimplikanten ist wesentlich, um über die visuelle Tafelreduzierung hinaus zu systematischer, überprüfbarer Logik-Minimierung zu gelangen, besonders wenn Entwürfe von Hand überprüft werden müssen oder wenn werkzeuggenerierte Gleichungen validiert werden müssen.