Bestimmen der Mindestanzahl von NAND / NOR-Gattern, die zum Realisieren eines Booleschen Ausdrucks erforderlich sind

9

Gibt es einen Algorithmus zur Bestimmung der Mindestanzahl von NAND- oder NOR-Gattern mit

  1. gegebene Anzahl von Eingängen
  2. Verfügbarkeit / Nichtverfügbarkeit von ergänzten Eingaben

erforderlich, um einen Booleschen Ausdruck zu realisieren? Wir können eine UND-ODER-Form als Hauptimplikanten über Karnaugh-Karten erhalten, die minimal ist (soweit ich weiß, erhält der Quine-McCluskey- Algorithmus sie deterministisch). Gibt es eine ähnliche Technik auch für NAND- oder NOR-Implementierungen? Zumindest sollte eine solche Technik die erforderliche Mindestanzahl von NAND / NOR-Gattern bestimmen, auch ohne das tatsächliche Diagramm zu finden?

Die Anwendung von De Morgans Gesetz auf die Hauptimplikanten scheint nicht deterministisch zu sein.

A ⊕ B = A'B + AB' = ((A'B)'(AB')')' [5 NAND gates]
A ⊕ B = (AB + A'B')' = ((ABAB+ABB') + (A'AB+A'B'))' = (AB(AB+B') + A'(AB+B'))' = ((AB+A')(AB+B'))' = (((AB)'A)'((AB)'B)')' [4 NAND gates by reusing (AB)']
Samik
quelle
Ist dies für eine zweistufige oder mehrstufige Implementierung?
Fizz
@RespawnedFluff Das Ziel der mehrstufigen Implementierung besteht darin, die Anzahl der Gates zu minimieren. Daher sollte die minimale NAND / NOR-Implementierung auch mehrstufig sein.
Samik
K-Map liefert kein minimales Ergebnis für die mehrstufige Optimierung.
Fizz

Antworten:

10

Sie können die minimale Anzahl von Gates in einem mehrstufigen Netzwerk nur finden, indem Sie ein ganzzahliges Programmierproblem lösen [oder Äquivalente, siehe unten]. Dieses Problem ist NP-vollständig, daher nur praktisch, um bis zu einem Dutzend Tore oder so zu lösen.

Es gibt Approximationsmethoden, die Ihnen nicht die Mindestanzahl geben, aber in Bezug auf den Zeitaufwand besser nachvollziehbar sind ... Dies ist ein großes Thema für sich, im Grunde das gesamte Gebiet der mehrstufigen Optimierung. Eine [kostenlose] Übersicht können Sie hier lesen .

Für kleine NAND-Netzwerke (bis zu 4 Variablen) wurde das Problem durch umfassende Aufzählung (oder gleichwertige Methoden) vollständig gelöst. Es gibt eine relativ neue [2009] Doktorarbeit von Elizabeth Ann Ernst, die die alten Ergebnisse zusammenfasst und erweitert. Ernst verwendet Branch-and-Bound, was die erschöpfende Methode in der Praxis verbessert, jedoch nicht asymptotisch. Sie merkt auch an, dass andere implizite Aufzählungsmethoden wie Integer-Programmierung oder CSP (Constraint-Zufriedenheit, gelöst über SAT) in der Praxis schlechter abschneiden.

Sie hat offensichtlich eine Software für ihre Methode geschrieben (genannt BESS), aber ich bin mir nicht sicher, ob sie irgendwo öffentlich verfügbar ist. Der vollständige Text ihrer Arbeit ist bei umich frei verfügbar . Und tatsächlich haben Sie den minimalen Ausdruck für xor mit 2 Eingängen gefunden (Ihren zweiten offensichtlich), den unten hervorgehobenen:

Geben Sie hier die Bildbeschreibung ein

Sie verglich auch die genauen Ergebnisse (für NANDs) mit denen des heuristischen Optimierers von ABC .

ABC konnte ein optimales Netzwerk für 340 von 4.043 Funktionen erstellen, bei denen das optimale Netzwerk bekannt ist. Für jene Funktionen, bei denen ABC kein optimales Netzwerk erzeugte, war es durchschnittlich 36% größer als das optimale Netzwerk [.]

Es gibt (offensichtlich) einige [größere] Netzwerke, für die BESS nicht fertig war, aber das Auffinden einer Obergrenze zuließ (an dem Punkt, an dem die Suche abgebrochen wurde). Für diese hat sich ABC recht gut geschlagen [gut in Bezug auf die gefundenen Grenzen], wie Sie aus der 2. Grafik unten sehen können.

Geben Sie hier die Bildbeschreibung ein

Fizz
quelle
Wenn Sie neugierig sind, habe ich ABC auf dem xor-Problem ausprobiert ... und es gibt 5 nand Gates, zumindest mit dem resyn2Skript. Es ist also nicht besser als Logic Friday (das misII verwendet).
Fizz
Es gibt Skripte und Datenbanken für ABC, die im Grunde genommen eine große Anzahl von Funktionen für vorberechnete optimale Implementierungen nachschlagen, z. B. arxiv.org/pdf/1108.3675.pdf. Ich habe diese nicht ausprobiert, aber selbst wenn sie funktioniert, war die harte Arbeit woanders gemacht.
Fizz
Ich gehe die von Ihnen bereitgestellten Materialien durch und sie sehen sehr interessant aus. Ich habe jedoch Schwierigkeiten, sie zu verstehen. Sobald ich sie richtig verstanden habe, werde ich wahrscheinlich das Kopfgeld vergeben. In der Zwischenzeit eine positive Bewertung abgeben.
Samik
1

Es gibt wahrscheinlich bessere Techniken da draußen, aber vor langer Zeit, als ich im dunklen Zeitalter war, fand ich, dass Karnaugh Maps gut funktioniert

R Drast
quelle
Würde es Ihnen etwas ausmachen, etwas Licht in diese "dunklen Zeitalter" zu bringen, wie Sie mit der aus Karnaugh-Karten erhaltenen AND-OR-Implementierung zur minimalen NAND / NOR-Implementierung gelangen können?
Samik
1

NAND gefolgt von NAND entspricht AND gefolgt von OR.

NOR gefolgt von NOR entspricht OR gefolgt von AND.

NAND gefolgt von NOR wäre gleichbedeutend mit AND gefolgt von AND, was nicht wirklich Sinn macht. NOR gefolgt von NAND wäre in ähnlicher Weise gleichbedeutend mit OR, gefolgt von OR.

Ich glaube nicht, dass es im Allgemeinen einen praktikablen Weg gibt, eine minimale Lösung für ein Problem mit einer großen Anzahl von Eingaben zu finden (offensichtlich kann man bei kleinen Eingangszahlen Brute Force anwenden). Quine-McClusky betrachtet nur zweistufige Lösungen (die minimale zweistufige Lösung ist oft nicht die minimale Gesamtlösung) und kann mit komplexen Wahrheitstabellen und einer großen Anzahl von Eingaben rechnerisch unmöglich werden.

Peter Green
quelle
Es gibt also keinen besseren Weg als das Verschieben von Blasen?
Samik
1

Der beste Algorithmus ist der Espresso- Algorithmus. Bis zu einem gewissen Grad ist dies in der FPGA-Synthese implementiert

Logic Friday ist eine Software, die Sie verwenden können. HINWEIS: Dadurch wird ein XOR auf 5 NAND-Gatter reduziert.

JonRB
quelle
Aber Espresso gibt auch die UND-ODER-Implementierung, nicht wahr?
Samik
1
Espresso ist nur in dem Sinne "am besten", dass es für große Eingaben (Formeln) machbar ist [im Gegensatz zu k-Maps], aber es gibt nicht in allen Fällen die beste / minimale Formel.
Fizz