Bitte sei nett. Ich habe eine heikle und wichtige Frage aus einem anderen Bereich der Technik, deren Antwort in der Elektrotechnik ziemlich bekannt sein könnte. Ich habe eine ähnliche Frage zu StackOverflow gestellt
Angenommen, ich habe eine Wahrheitstabelle mit 5 Eingängen und 1 Ausgang. Ich habe den Espresso-Algorithmus (z. B. Logic Friday) verwendet, um die Tabelle zu minimieren und eine effiziente VHDL zu schreiben. Alles funktioniert gut.
Anstatt die Wahrheitstabelle zu minimieren und NAND-Gattern zuzuordnen, möchte ich eine beliebige ternäre logische Funktion abbilden. Ich interessiere mich nicht für mehrwertige Logik, sondern für logische Funktionen mit 3 Eingangsvariablen. Es gibt 256 dieser Funktionen, und 3-in-NAND ist nur eine davon. Möglicherweise sind nicht alle dieser 256 Funktionen interessant: Einige reduzieren sich auf ihre 2 Geschwister mit Eingangsvariablen.
Frage : Wie können Sie einer dieser 3-in-Funktionen eine Wahrheitstabelle (z. B. mit 7 Eingängen) zuordnen? Ein Tool, das etwas Ähnliches tut, wäre großartig, aber eine Methode zur Vereinfachung auf beliebige ternäre Funktionen wäre am besten.
Hintergrund: Moderne CPUs können beliebige ternäre Logikoperationen mit 512-Bit-Registern (z. B. Befehl vpternlog ) ausführen. Aufgrund der Komplexität überlassen Compiler dies jedoch dem Programmierer, der keine Ahnung hat , wie dies optimiert werden soll.
quelle
Antworten:
Analyse
f ( a , b , c ) = a & ( ! b | c ) ,
Da die Codierung nur 8 Eingänge und nur 2 Binärergebnisse enthält, kann dies als 8-Bit-Zahl codiert werden, in diesem Fall 0b10110000 = 0xB0.
Optimierungen
Bei einer beliebigen n -ary-Funktion von Booleschen Werten müssen wir lediglich Binärfunktionen in ternäre Funktionen konvertieren. Wir können dies tun, weil wir wissen, dass wir jede Kombination von Funktionen berechnen können. Ausgehend von einem abstrakten Syntaxbaum von unären und binären Knoten würden wir zunächst unäre und binäre Funktionen auf ähnliche Weise wie oben beschrieben "codieren" darstellen.
Also, für unser f :
Mit rekursiver Logik können wir BIN und UNARY kombinieren in:
Was dann optimiert werden kann (Konvertierungsregeln folgen leicht aus der booleschen Logik):
Überwachung
Dies ist sehr ähnlich der Berechnung von FPGA-Nachschlagetabellen (LUTs). Ich bin mir ziemlich sicher, dass Sie viele Texte und Algorithmen für die Zuordnung von Logik zu LUTs finden können. Zum Beispiel: Flow-Map ( http://cadlab.cs.ucla.edu/~cong/papers/tcad94.pdf )
quelle
Auszug aus meiner eigenen Antwort .
Inhalt von BF_Q6.eqn:
In ABC laufe ich:
Möglicherweise müssen Sie
choice; if -K 3; ps
mehrere Male ausführen , um bessere Ergebnisse zu erzielen .Die resultierende BF_Q6.bench enthält die 3-LUTs für ein FPGA:
Dies kann (mechanisch) in das gesuchte C ++ umgeschrieben werden.
quelle